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