Partitions Based On Permutations

[Joshua Zucker]

On Dec 4, 2007 10:31 AM, Leroy Quet <q1qq2qqq3qqqq at yahoo.com> wrote:
> %I A000001
> %S A000001
> 1,0,0,1,1,0,0,0,0,1,2,0,2,1,0,0,0,0,0,1,3
> %N A000001 a(n) = the total number of
> permutations (m(1),m(2),m(3)...m(j)) of
> (1,2,3,...,j) where n = 1*m(1) + 2*m(2) + 3*m(3)
> + ...+j*m(j), where j is over all positive
> integers.

With PURE brute force (checking all permutations for each j such that
1*j + 2*(j-1) + ... + j*1 is less than n), in about 10 seconds my
program gives the following first 164 terms:
1 0 0 1 1 0 0 0 0 1 2 0 2 1 0 0 0 0 0 1 3 1 4 2 2 2 4 1 3 1 0 0 0 0 1
4 3 6 7 6 4 10 6 10 6 10 6 10 4 6 7 6 3 4 1 1 5 6 9 16 12 14 24 20 21
23 28 24 34 20 32 42 29 29 42 32 20 34 24 28 23 21 20 25 20 22 30 38
32 40 47 55 54 74 70 84 90 78 90 129 106 123 134 147 98 168 130 175
144 168 144 184 144 168 144 175 130 168 98 148 141 138 128 176 144 148
184 213 194 252 237 292 284 311 290 408 363 390 406 518 394 542 492
640 557 666 595 776 684 786 718 922 745 917 781 982 826 950 844 1066
845 936 845 1066

So it sure looks like the last bunch of 0s are the ones there, with
a(34) being the last of all.  It's easy to prove that 34 has no such
representation, even without the brute force of the program: 1*5 + 2*4
+ 3*3 + 4*2 + 5*1 is 35, so any representation of 34 must have 4 or
fewer terms, but 1*1 + 2*2 + 3*3 + 4*4  is only 30, so we get that run
of 0s from 31 through 34.  But I haven't written down a careful proof
that everything greater than 34 is makeable.  The plausibility
argument is pretty convincing, when combined with the numerical data.

Anyone who wants to see all 1066 representations of, say, 164, I'm
happy to send along the data on that as well; it's easy enough to make
the program generate it.

The program's running time per computation grows as (cube root of n)!,
I think, so in the long run that factorial will be killer; but cube
root of n isn't too painful. I could squeeze out a few dozen more
terms with a couple seconds of CPU time apiece.  Eventually, though,
I'll need a smarter algorithm than "try all the permutations" - for
instance, after choosing each element of the permutation, look at a
lower and upper bound for what's left, and prune the tree that way
(e.g. if you pair j with j, perhaps the sum is guaranteed to be too
big now, so now you have just saved 1/j of the total running time ...)

--Joshua Zucker