

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*(n1)/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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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*(n1)/2 terms. Row sums are the factorials (A000142). T(n,0) = T(n,1) = (n1)! for n >= 2. T(n,2) = (n1)!/2 = A001710(n1) for n >= 3. Sum_{k>=0} k*T(n,k) = A067318(n).


LINKS



FORMULA

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


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


MATHEMATICA

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


CROSSREFS



KEYWORD

nonn,tabf


AUTHOR



EXTENSIONS



STATUS

approved



