A129177 Triangle read by rows: T(n,k) is the number of permutations p of {1,2,...,n} such that w(p)=k (n >= 0; 0 <= k <= n*(n-1)/2) (see comments for definition of w(p)).

1, 1, 1, 1, 2, 2, 1, 1, 6, 6, 3, 5, 2, 1, 1, 24, 24, 12, 20, 14, 10, 7, 5, 2, 1, 1, 120, 120, 60, 100, 70, 74, 59, 37, 30, 19, 15, 7, 5, 2, 1, 1, 720, 720, 360, 600, 420, 444, 474, 342, 240, 214, 160, 116, 89, 49, 36, 25, 15, 7, 5, 2, 1, 1, 5040, 5040, 2520, 4200, 2940, 3108, 3318

Offset

0,5

Comments

w(p) is defined (by Edelman, Simion and White) in the following way: if p = (c[1])(c[2])... is expressed in standard cycle form (i.e., cycles ordered by increasing smallest elements with each cycle written with its smallest element in the first position), then w(p) = 0*|c[1]| + 1*|c[2]| + 2*|c[3]| + ..., where |c[j]| denotes the number of entries in the cycle c[j].

Row n has 1 + n*(n-1)/2 terms. Row sums are the factorials (A000142). T(n,0) = T(n,1) = (n-1)! for n >= 2. T(n,2) = (n-1)!/2 = A001710(n-1) for n >= 3. Sum_{k>=0} k*T(n,k) = A067318(n).

Links

Alois P. Heinz, Rows n = 0..50, flattened

P. H. Edelman, R. Simion and D. White, Partition statistics on permutations, Discrete Math. 99 (1992), 63-68.

M. Shattuck, Parity theorems for statistics on permutations and Catalan words, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 5, Paper A07, 2005.

Formula

Generating polynomial of row n is P[n](t) = Product_{i=0..n-1} (i + t^i).

Sum_{k=0..n*(n-1)/2} (k+1) * T(n,k) = A121586(n). - Alois P. Heinz, May 04 2023

Example

T(4,2)=3 because we have w(1423) = w((1)(243)) = 0*1 + 1*3 = 3, w(1342) = w((1)(234)) = 0*1 + 1*3=3 and w(2134) = w((12)(3)(4)) = 0*2 + 1*1 + 2*1 = 3.
Triangle starts:
   1;
   1;
   1,  1;
   2,  2,  1,  1;
   6,  6,  3,  5,  2,  1,  1;
  24, 24, 12, 20, 14, 10,  7,  5,  2,  1,  1;

Maple

for n from 0 to 8 do P[n]:=sort(expand(product(i+t^i, i=0..n-1))) od: for n from 0 to 8 do seq(coeff(P[n], t, j), j=0..n*(n-1)/2) od; # yields sequence in triangular form
# second Maple program:
p:= proc(n) option remember; `if`(n<0, 1, expand((n+t^n)*p(n-1))) end:
T:= n-> (h-> seq(coeff(h, t, i), i=0..degree(h)))(p(n-1)):
seq(T(n), n=0..8);  # Alois P. Heinz, Dec 16 2016

Mathematica

p[n_] := p[n] = If[n<0, 1, Expand[(n+t^n)*p[n-1]]]; T[n_] := Function[h, Table[Coefficient[h, t, i], {i, 0, Exponent[h, t]}]][p[n-1]]; Table[T[n], {n, 0, 8}] // Flatten (* Jean-François Alcover, Dec 22 2016, after Alois P. Heinz *)

Crossrefs

Cf. A000142, A001710, A067318, A121586.

Sequence in context: A114626 A221916 A124773 * A127452 A263755 A135879

Adjacent sequences: A129174 A129175 A129176 * A129178 A129179 A129180

Keyword

nonn,tabf

Author

Emeric Deutsch, Apr 11 2007

Extensions

One term for row n=0 prepended by Alois P. Heinz, Dec 16 2016

Status

approved