A334622 A(n,k) is the sum of the k-th powers of the descent set statistics for permutations of [n]; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 6, 8, 1, 1, 2, 10, 24, 16, 1, 1, 2, 18, 88, 120, 32, 1, 1, 2, 34, 360, 1216, 720, 64, 1, 1, 2, 66, 1576, 14460, 24176, 5040, 128, 1, 1, 2, 130, 7224, 190216, 994680, 654424, 40320, 256, 1, 1, 2, 258, 34168, 2675100, 46479536, 109021500, 23136128, 362880, 512

Offset: 0

Author

Alois P. Heinz, Sep 09 2020

Keywords

• nonn
• tabl

Examples

			Square array A(n,k) begins:
   1,   1,     1,      1,        1,          1,            1, ...
   1,   1,     1,      1,        1,          1,            1, ...
   2,   2,     2,      2,        2,          2,            2, ...
   4,   6,    10,     18,       34,         66,          130, ...
   8,  24,    88,    360,     1576,       7224,        34168, ...
  16, 120,  1216,  14460,   190216,    2675100,     39333016, ...
  32, 720, 24176, 994680, 46479536, 2368873800, 128235838496, ...
  ...
		

Links

• Alois P. Heinz, Antidiagonals n = 0..25, flattened
• R. Ehrenborg and A. Happ, On the powers of the descent set statistic, arXiv:1709.00778 [math.CO], 2017.

Crossrefs

Columns k=0-4 give: A011782, A000142, A060350, A291902, A291903.

Rows n=0+1, 2-3 give: A000012, A007395(k+1), A052548(k+1).

Main diagonal gives A334623.

Cf. A060351, A335545.

Programs

Maple

b:= proc(u, o, t) option remember; expand(`if`(u+o=0, 1,
      add(b(u-j, o+j-1, t+1)*x^floor(2^(t-1)), j=1..u)+
      add(b(u+j-1, o-j, t+1), j=1..o)))
    end:
A:= (n, k)-> (p-> add(coeff(p, x, i)^k, i=0..degree(p)))(b(n, 0$2)):
seq(seq(A(n, d-n), n=0..d), d=0..10);

Mathematica

b[u_, o_, t_] := b[u, o, t] = Expand[If[u + o == 0, 1,
    Sum[b[u - j, o + j - 1, t + 1] x^Floor[2^(t - 1)], {j, 1, u}] +
    Sum[b[u + j - 1, o - j, t + 1], {j, 1, o}]]];
A[n_, k_] := Function[p, Sum[Coefficient[p, x, i]^k, {i, 0, Exponent[p, x]}]][b[n, 0, 0]];
Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Dec 20 2020, after Alois P. Heinz *)

Formula

A(n,k) = Sum_{j=0..ceiling(2^(n-1))-1} A060351(n,j)^k.