Partitions Based On Permutations

Tue Dec 4 21:40:34 CET 2007

Whoops, never mind. 55 is just the sum of the
squares of the first 5 positive integers.
And 56 is just sum{k=1 to 6} k*(7-k).

Maybe there is something interesting for other
n's (with multiple solutions).

Thanks, sorry,
Leroy Quet

--- Leroy Quet <q1qq2qqq3qqqq at yahoo.com> wrote:

> First, thanks to Joshua Zucker for doing the
> work.
> 
> It occurs to me that maybe (unless for some
> reason the solution is obvious) figuring out by
> hand the one representation for n=55 or the one
> for n=56 might make a good puzzle for those on
> Seq.fan.
> :)
> (Maybe this would be too easy, since we know
> for
> one thing that the permutation
> (m(1),m(2),...m(j)) is its own inverse
> permutation. Maybe figuring out a
> representation
> for other n's would be a better puzzle.)
> 
> Thanks,
> Leroy Quet
> 
> 
> --- Joshua Zucker <joshua.zucker at gmail.com>
> wrote:
> 
> > 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
> > 
> >...
> 
> 
> 
> 
>      
>
____________________________________________________________________________________
> Be a better sports nut!  Let your teams follow
> you 
> with Yahoo Mobile. Try it now. 
>
http://mobile.yahoo.com/sports;_ylt=At9_qDKvtAbMuh1G1SQtBI7ntAcJ
> 
> 

      ____________________________________________________________________________________
Looking for last minute shopping deals?  
Find them fast with Yahoo! Search.  http://tools.search.yahoo.com/newsearch/category.php?category=shopping

"Joshua Zucker" <joshua.zucker at gmail.com> wrote:
: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) [...]

If I correctly understand what you are doing, more efficient would be
to count all sums for a given j and allocate to the appropriate n; after
each j is complete, you know you have a(n) fully determined up to
min(sum(P(j+1)). (You may already be doing this, if I misunderstood
what you wrote.)

It is also possible to iterate over permutations swapping just one pair
of elements at a time, which would make it much faster to calculate the
this, as suggested by Knuth and explained in
<http://www.perlmonks.org/?node_id=481736>; I'm not sure if there is
a way to choose pairs with less work.

With this approach, j=9 takes 1.49s on my machine (which prints the same
Rewriting in C would probably give a 100-1000x speedup, but each chunk
is still going to take time proportional to j! to produce the next
j(j+1)/2 results.

Hugo
---
#!/usr/bin/perl -w
use strict;
my($j, $lim, @seen) = (0, 0);
while (1) {
}

}

"Joshua Zucker" <joshua.zucker at gmail.com> wrote:
: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) [...]

If I correctly understand what you are doing, more efficient would be
to count all sums for a given j and allocate to the appropriate n; after
each j is complete, you know you have a(n) fully determined up to
min(sum(P(j+1)). (You may already be doing this, if I misunderstood
what you wrote.)

It is also possible to iterate over permutations swapping just one pair
of elements at a time, which would make it much faster to calculate the
this, as suggested by Knuth and explained in
<http://www.perlmonks.org/?node_id=481736>.

With this approach, j=9 takes 1.49s on my machine (which prints the same
Rewriting in C would probably give a 100-1000x speedup, but each chunk
is still going to take time proportional to j! to produce the next
j(j+1)/2 results.

Hugo
---
#!/usr/bin/perl -w
use strict;
my($j, $lim, @seen) = (0, 0);
while (1) {
}

}