A381426 A(n,k) is the sum over all ordered partitions of [n] of k^j for an ordered partition with j inversions; square array A(n,k), n>=0, k>=0, read by antidiagonals.
1, 1, 1, 1, 1, 2, 1, 1, 3, 4, 1, 1, 4, 13, 8, 1, 1, 5, 36, 75, 16, 1, 1, 6, 79, 696, 541, 32, 1, 1, 7, 148, 3851, 27808, 4683, 64, 1, 1, 8, 249, 14808, 567733, 2257888, 47293, 128, 1, 1, 9, 388, 44643, 5942608, 251790113, 369572160, 545835, 256, 1, 1, 10, 571, 113480, 40065301, 9546508128, 335313799327, 121459776768, 7087261, 512
Offset: 0
Examples
Square array A(n,k) begins: 1, 1, 1, 1, 1, 1, 1, ... 1, 1, 1, 1, 1, 1, 1, ... 2, 3, 4, 5, 6, 7, 8, ... 4, 13, 36, 79, 148, 249, 388, ... 8, 75, 696, 3851, 14808, 44643, 113480, ... 16, 541, 27808, 567733, 5942608, 40065301, 199246816, ... 32, 4683, 2257888, 251790113, 9546508128, 179833594207, 2099255895008, ...
Links
- Alois P. Heinz, Antidiagonals n = 0..55, flattened
- Wikipedia, Inversion
- Wikipedia, Partition of a set
Crossrefs
Programs
-
Maple
b:= proc(o, u, t, k) option remember; `if`(u+o=0, 1, `if`(t=1, b(u+o, 0$2, k), 0)+add(k^(u+j-1)*b(o-j, u+j-1, 1, k), j=1..o)) end: A:= (n, k)-> b(n, 0$2, k): seq(seq(A(n, d-n), n=0..d), d=0..10); -
Mathematica
b[o_, u_, t_, k_] := b[o, u, t, k] = If[u + o == 0, 1, If[t == 1, b[u + o, 0, 0, k], 0] + Sum[If[k == u + j - 1 == 0, 1, k^(u + j - 1)]*b[o - j, u + j - 1, 1, k], {j, 1, o}]]; A[n_, k_] := b[n, 0, 0, k]; Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Apr 19 2025, after Alois P. Heinz *)
Formula
A(n,k) = Sum_{j=0..binomial(n,2)} k^j * A381299(n,j).