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

Author

Emeric Deutsch, Apr 11 2007

Keywords

• nonn
• tabf

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).

Examples

			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;
		

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.

Crossrefs

Cf. A000142, A001710, A067318, A121586.

Programs

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 *)

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

Extensions

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