Partitions Based On Permutations

[hv at crypt.org]

sums; the sample perl code below uses the Cantor expansion to achieve
series as you reported); j=10 takes 14.68s, and j=11 takes 161.21s.
  all_perms(++$j);
  my $newlim = $j * ($j + 1) * ($j + 2) / 6;
  print join(' ', map $seen[$_] || 0, $lim .. $newlim - 1), "\n";
  $lim = $newlim;
sub all_perms {
  my $j = shift;
  my @arr = (1 .. $j);
  my $sum = 0;
  $sum += $_ * $_ for 1 .. $j;
  my $n = 0;
  while (1) {
    # count each sum seen
    ++$seen[$sum];
    ++$n;
    my($i, $p, $d) = (2, $n);
    # find next element to swap from Cantor expansion of the counter $n
    $p /= $i++ until $d = $p % $i;
    last if $i > $j;
    # Knuth's trick
    my($swap1, $swap2) = (($i % 2) ? 0 : $d - 1), $i - 1);
    # swap the elements, and adjust the sum
    @arr[$swap1, $swap2] = @arr[$swap2, $swap1];
    $sum += ($swap1 - $swap2) * ($arr[$swap1] - $arr[$swap2]);
  }
Return-Path: <hv at zen.crypt.org>
X-Ids: 166
Message-Id: <200712050223.lB52Nrx5025268 at zen.crypt.org>
To: "Joshua Zucker" <joshua.zucker at gmail.com>
cc: seqfan at ext.jussieu.fr
Subject: Re: Partitions Based On Permutations
From: hv at crypt.org
In-Reply-To: <721e81490712041157i3103070eh870ba8146b0b5264 at mail.gmail.com>
Date: Wed, 05 Dec 2007 02:23:53 +0000
Sender: hv at zen.crypt.org
X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-3.0 (shiva.jussieu.fr [134.157.0.166]); Wed, 05 Dec 2007 04:24:23 +0100 (CET)
X-Virus-Scanned: ClamAV 0.88.7/5002/Wed Dec  5 01:58:59 2007 on shiva.jussieu.fr
X-Virus-Status: Clean
X-Miltered: at shiva.jussieu.fr with ID 475619E6.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!
sums; the sample perl code below uses the Cantor expansion to achieve
series as you reported); j=10 takes 14.68s, and j=11 takes 161.21s.
  all_perms(++$j);
  my $newlim = $j * ($j + 1) * ($j + 2) / 6;
  print join(' ', map $seen[$_] || 0, $lim .. $newlim - 1), "\n";
  $lim = $newlim;
sub all_perms {
  my $j = shift;
  my @arr = (1 .. $j);
  my $sum = 0;
  $sum += $_ * $_ for 1 .. $j;
  my $n = 0;
  while (1) {
    # count each sum seen
    ++$seen[$sum];
    ++$n;
    my($i, $p, $d) = (2, $n);
    # find next element to swap from Cantor expansion of the counter $n
    $p /= $i++ until $d = $p % $i;
    last if $i > $j;
    # Knuth's trick
    my($swap1, $swap2) = (($i % 2) ? 0 : $d - 1), $i - 1);
    # swap the elements, and adjust the sum
    @arr[$swap1, $swap2] = @arr[$swap2, $swap1];
    $sum += ($swap1 - $swap2) * ($arr[$swap1] - $arr[$swap2]);
  }
Return-Path: <maxale at gmail.com>
X-Ids: 164
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=gamma;
        h=domainkey-signature:received:received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references;
        bh=I25jOV6jA+RkvAsY+LDhZHiECXJVMXPCwaYHYwEDntc=;
        b=aX5n9FyAvfaW6H2S02gaf2lwGzmQXJbqrwJsVtvmUYhixGDdpCX6TukpyvH7pT6YqzLYT6nryEKxPkkuR86QYXubcdPqDDtj9tmRB+/sLT1Hno4lmAf7Ne8KfD+1Obcn1I4YA/0L2DXWoLnRDq0QURVhw2UrkXBolTVTz9oL4pU=
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=gamma;
        h=received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references;
        b=WBmHFtEhMRIGojkt+oO139OFFbiYf7QEsDWafufduF1gKL19FdAVryRmv2V2somwfX0QNpbP9csLisSTCczJSl3qc7alIF3X+Dgbvndvh84sQWTe7HY5NAmqPGKyt+45zEs0St7bhdEJhypXK/oV1y2fxyOOlQSby8gSiMk3S2c=
Message-ID: <d3dac270712042334g1a41fccfj135e640c5f6509dc at mail.gmail.com>
Date: Tue, 4 Dec 2007 23:34:26 -0800
From: "Max Alekseyev" <maxale at gmail.com>
To: "Leroy Quet" <q1qq2qqq3qqqq at yahoo.com>
Subject: Re: Partitions Based On Permutations
Cc: seqfan at ext.jussieu.fr, qq-quet at mindspring.com
In-Reply-To: <231114.40692.qm at web45616.mail.sp1.yahoo.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
References: <231114.40692.qm at web45616.mail.sp1.yahoo.com>
X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-3.0 (shiva.jussieu.fr [134.157.0.164]); Wed, 05 Dec 2007 08:34:37 +0100 (CET)
X-Virus-Scanned: ClamAV 0.88.7/5005/Wed Dec  5 05:50:53 2007 on shiva.jussieu.fr
X-Virus-Status: Clean
X-j-chkmail-Score: MSGID : 4756548D.003 on shiva.jussieu.fr : j-chkmail score : X : 0/50 1 0.492 -> 1
X-Miltered: at shiva.jussieu.fr with ID 4756548D.003 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!

On Dec 4, 2007 10:31 AM, Leroy Quet <q1qq2qqq3qqqq at yahoo.com> wrote:
> I just submitted this sequence:
>
> %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.

[...]

> Does every integer greater than some integer
> (such as, say, 20) have such a representation?
>
> It seems very likely that the answer is yes. For
> a given j, the least  possible n is j^3/6 + j^2/2
> + j/3. The greatest possible n is j^3/3 + j^2/2
> +j/6 (the sum of the first j squares).

btw, these bounds are A000292(j) and A000330(j).

> The difference between these extremes, plus 1, is
> j^3/6 - j/6 + 1, if I did my math right.

and this is A050407(j+2)

> But the number of permutations for a given j is
> j!, obviously.

It is interesting to look at the number of representations of numbers
in the interval [A000292(j),A000330(j)] in the form
1*m(1) + 2*m(2) + 3*m(3) + ...+j*m(j),
where m is a permutation of order j. Note that the number of
representations is symmetric in this interval as n and
(A000292(j)+A000330(j))-n = A006002(j)-n have the same number of
representations:

j=1: 1
j=2: 1, 1
j=3: 1, 2, 0, 2, 1
j=4: 1, 3, 1, 4, 2, 2, 2, 4, 1, 3, 1
j=5: 1, 4, 3, 6, 7, 6, 4, 10, 6, 10, 6, 10, 6, 10, 4, 6, 7, 6, 3, 4, 1
j=6: 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, 24, 14, 12, 16, 9, 6, 5, 1
j=7: 1, 6, 10, 14, 29, 26, 35, 46, 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, 147, 134, 123, 106, 129, 90, 78, 90, 84,
70, 74, 54, 55, 46, 35, 26, 29, 14, 10, 6, 1
j=8: 1, 7, 15, 22, 47, 54, 70, 94, 129, 124, 178, 183, 237, 238, 276,
264, 379, 349, 380, 400, 517, 394, 542, 492, 640, 557, 666, 595, 776,
684, 786, 718, 922, 745, 917, 781, 982, 826, 950, 844, 1066, 845, 936,
845, 1066, 844, 950, 826, 982, 781, 917, 745, 922, 718, 786, 684, 776,
595, 666, 557, 640, 492, 542, 394, 517, 400, 380, 349, 379, 264, 276,
238, 237, 183, 178, 124, 129, 94, 70, 54, 47, 22, 15, 7, 1

It turns out that for j>=4, no number in the interval
[A000292(j),A000330(j)] has zero number of representations. If so,
your question:

> %C A000001 Does every integer greater than some positive integer N have at least one such representation?

trivially has an affirmative answer.

The maximum number of representations for j=1..11 is:
1, 1, 2, 4, 10, 42, 184, 1066, 6697, 50066, 442248
is not in OEIS.

The numbers with the maximum number of representations are:

j=1: 1
j=2: 4, 5
j=3: 11, 13
j=4: 23, 27
j=5: 42, 44, 46, 48
j=6: 72, 75
j=7: 112
j=8: 160, 164
j=9: 221, 229
j=10: 300, 305
j=11: 395, 397

For j>=6, such number n seems to be uniquely defined up to a
counterpart (i.e., A006002(j)-n).
For j=7, it is exactly the middle of the interval
[A000292(7),A000330(7)] with equality n=A006002(7)-n=A006002(7)/2.
What other j have A006002(j)/2 as the most represented number?

Regards,
Max