A215561 Number A(n,k) of permutations of k indistinguishable copies of 1..n with every partial sum <= the same partial sum averaged over all permutations; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 1, 1, 1, 5, 30, 7, 1, 1, 1, 14, 420, 403, 35, 1, 1, 1, 42, 6930, 40350, 18720, 139, 1, 1, 1, 132, 126126, 5223915, 19369350, 746192, 1001, 1, 1, 1, 429, 2450448, 783353872, 27032968200, 9212531290, 71892912, 5701, 1

Offset: 0

Author

Alois P. Heinz, Aug 16 2012

Keywords

• nonn
• tabl

Comments

"Late-growing permutations" were first defined by R. H. Hardin in A147681 and 18 related sequences. David Scambler observed that the set of orthogonal sequences includes A000108 and A007004, and he asked for the other orthogonal sequences, see link below.

"Early-growing permutations" with every partial sum >= the same partial sum averaged over all permutations define the same sequences.

Conjecture: Row r > 1 is asymptotic to c(r) * r^(r*n) / (Pi^((r-1)/2) * n^((r+1)/2)), where c(r) are a constants. - Vaclav Kotesovec, Sep 07 2016

Examples

			A(2,2) = 2: (1,1,2,2), (1,2,1,2).
A(2,3) = 5: (1,1,1,2,2,2), (1,1,2,1,2,2), (1,1,2,2,1,2), (1,2,1,1,2,2), (1,2,1,2,1,2).
A(3,1) = 3: (1,2,3), (1,3,2), (2,1,3).
a(4,1) = 7: (1,2,3,4), (1,2,4,3), (1,3,2,4), (1,4,2,3), (2,1,3,4), (2,1,4,3), (2,3,1,4).
Square array A(n,k) begins:
  1,   1,     1,        1,           1,              1, ...
  1,   1,     1,        1,           1,              1, ...
  1,   1,     2,        5,          14,             42, ...
  1,   3,    30,      420,        6930,         126126, ...
  1,   7,   403,    40350,     5223915,      783353872, ...
  1,  35, 18720, 19369350, 27032968200, 44776592395920, ...
		

Links

• Alois P. Heinz, Antidiagonals n = 0..14, flattened
• David Scambler et al., A147681 Late-growing permutations and follow-up messages on the SeqFan list, Aug 10 2012

Crossrefs

Columns k=0-19 give: A000012, A147681, A147682, A147684, A147686, A147687, A147692, A147694, A147695, A147697, A147698, A147700, A147705, A147707, A147712, A147713, A147714, A147715, A147717, A147769.

Rows n=0+1, 2-7 give: A000012, A000108, A007004, A215562, A215570, A215571, A215593.

Programs

Maple

b:= proc(l) option remember; local m, n, g;
      m, n:= nops(l), add(i, i=l);
      g:= add(i*l[i], i=1..m)-(m+1)/2*(n-1);
     `if`(n<2, 1, add(`if`(l[i]>0 and i<=g,
        b(subsop(i=l[i]-1, l)), 0), i=1..m))
    end:
A:= (n, k)-> b([k$n]):
seq(seq(A(n, d-n), n=0..d), d=0..10);

Mathematica

b[l_] := b[l] = Module[{m, n, g}, {m, n} = {Length[l], Total[l]}; g = Sum[i*l[[i]], {i, 1, m}] - (m+1)/2*(n-1); If[n < 2, 1, Sum[If[l[[i]] > 0 && i <= g, b[ReplacePart[l, i -> l[[i]] - 1]], 0], {i, 1, m}]]]; a[n_, k_] := b[Array[k&, n]]; Table [Table [a[n, d-n], {n, 0, d}], {d, 0, 9}] // Flatten (* Jean-François Alcover, Dec 06 2013, translated from Maple *)