cp's OEIS Frontend

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

%I A129178 #23 Jun 01 2021 11:57:40
%S A129178 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,
%T A129178 10,2,64,160,288,432,564,658,680,638,542,416,284,172,90,38,12,2,128,
%U A129178 384,800,1376,2072,2824,3526,4058,4344,4346,4066,3562,2912,2218,1566,1016,598
%N 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).
%C A129178 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.
%C A129178 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).
%C A129178 It appears that Sum_{k>=0} k*T(n,k) = A126673(n).
%D A129178 L. Carlitz, Generalized Stirling numbers, Combinatorial Analysis Notes, Duke University, 1968, 1-7.
%H A129178 Alois P. Heinz, <a href="/A129178/b129178.txt">Rows n = 0..50, flattened</a>
%H A129178 Toufik Mansour, Mark Shattuck, <a href="http://doi.org/10.1007/s13370-012-0106-6">A q-analog of the hyperharmonic numbers</a>, Afrika Matematika 25.1 (2014): 147-160.
%H A129178 M. Shattuck, <a href="https://www.emis.de/journals/INTEGERS/papers/f7/f7.Abstract.html">Parity theorems for statistics on permutations and Catalan words</a>, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 5, Paper A07, 2005.
%F A129178 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.
%e A129178 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.
%e A129178 Triangle starts:
%e A129178    1;
%e A129178    1;
%e A129178    2;
%e A129178    4,   2;
%e A129178    8,   8,   6,   2;
%e A129178   16,  24,  28,  26,  16,   8,   2;
%e A129178   32,  64,  96, 120, 126, 110,  82,  52,  26,  10,  2;
%e A129178   ...
%p A129178 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
%t A129178 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 *)
%Y A129178 Cf. A000142, A011782, A000079, A036289, A121552, A126673.
%K A129178 nonn,tabf
%O A129178 0,3
%A A129178 _Emeric Deutsch_, Apr 11 2007
%E A129178 One term for row n=0 prepended by _Alois P. Heinz_, Dec 16 2016