|
Search: id:A129178
|
|
|
| A129178 |
|
Triangle read by rows: T(n,k) is the number of permutations p of {1,2,...,n} such that invc(p)=k (n>=1; 0<=k<=(n-1)(n-2)/2); invc(p) is defined (by Carlitz) in the following way: express p 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 remove the parentheses and count the inversions in the obtained word. |
|
+0
5
|
|
| 1, 2, 4, 2, 8, 8, 6, 2, 16, 24, 28, 26, 16, 8, 2, 32, 64, 96, 120, 126, 110, 82, 52, 26, 10, 2, 64, 160, 288, 432, 564, 658, 680, 638, 542, 416, 284, 172, 90, 38, 12, 2, 128, 384, 800, 1376, 2072, 2824, 3526, 4058, 4344, 4346, 4066, 3562, 2912, 2218, 1566, 1016, 598
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
Row n has 1+(n-1)(n-2)/2 terms. Row sums are the factorials (A000142). T(n,0)=2^(n-1)=A011782(n)=A000079(n-1). T(n,1)=(n-2)*2^(n-2)=A036289(n-2) for n>=2. T(n,k)=A121552(n,n+k).
It appears that Sum(k*T(n,k),k>=0)=A126673(n).
|
|
REFERENCES
|
L. Carlitz, Generalized Stirling numbers, Combinatorial Analysis Notes, Duke University, 1968, 1-7.
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)=2(2+t)(2+t+t^2)...(2+t+t^2+...+t^(n-2)) for n>=3, P[1](t)=1, P[2](t)=2.
|
|
EXAMPLE
|
T(3,0)=4, T(3,1)=2 because we have 123=(1)(2)(3), 132=(1)(23), 213=(12)(3), 231=(123) with the resulting word (namely 123) having 0 inversions and 312=(132) and (321)=(13)(2) with the resulting word (namely 132) having 1 inversion.
Triangle starts:
1;
2;
4,2;
8,8,6,2;
16,24,28,26,16,8,2;
32,64,96,120,126,110,82,52,26,10,2;
|
|
MAPLE
|
s:=j->2+sum(t^i, i=1..j): for n from 1 to 9 do P[n]:=sort(expand(simplify(product(s(j), j=0..n-2)))) od: for n from 1 to 9 do seq(coeff(P[n], t, j), j=0..(n-1)*(n-2)/2) od; # yields sequence in triangular form
|
|
CROSSREFS
|
Cf. A000142, A011782, A000079, A036289, A121552, A126673.
Sequence in context: A095728 A163897 A113477 this_sequence A152874 A065286 A068217
Adjacent sequences: A129175 A129176 A129177 this_sequence A129179 A129180 A129181
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Apr 11 2007
|
|
|
Search completed in 0.002 seconds
|
