login
A129178
Triangle read by rows: T(n,k) is the number of permutations p of {1,2,...,n} such that invc(p)=k (n >= 0; 0 <= k <= (n-1)(n-2)/2) (see comment for invc definition).
5
1, 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
OFFSET
0,3
COMMENTS
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.
Row n has 1+(n-1)*(n-2)/2 - delta_{0,n} 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>=0} k*T(n,k) = A126673(n).
REFERENCES
L. Carlitz, Generalized Stirling numbers, Combinatorial Analysis Notes, Duke University, 1968, 1-7.
LINKS
Toufik Mansour, Mark Shattuck, A q-analog of the hyperharmonic numbers, Afrika Matematika 25.1 (2014): 147-160.
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;
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 0 to 9 do P[n]:=sort(expand(simplify(product(s(j), j=0..n-2)))) od: for n from 0 to 9 do seq(coeff(P[n], t, j), j=0..degree(P[n])) od; # yields sequence in triangular form
MATHEMATICA
nMax = 9; s[j_] := 2 + Sum[t^i, {i, 1, j}]; P[0] = P[1] = 1; P[2] = 2; For[ n = 3, n <= nMax, n++, P[n] = Sort[Expand[Simplify[Product[s[j], {j, 0, n-2}]]]]]; Table[Coefficient[P[n], t, j], {n, 0, nMax}, {j, 0, Exponent[ P[n], t]}] // Flatten (* Jean-François Alcover, Jan 24 2017, adapted from Maple *)
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