cp's OEIS Frontend

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

%I A129177 #21 May 04 2023 19:23:57
%S A129177 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,
%T A129177 100,70,74,59,37,30,19,15,7,5,2,1,1,720,720,360,600,420,444,474,342,
%U A129177 240,214,160,116,89,49,36,25,15,7,5,2,1,1,5040,5040,2520,4200,2940,3108,3318
%N 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)).
%C A129177 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].
%C A129177 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).
%H A129177 Alois P. Heinz, <a href="/A129177/b129177.txt">Rows n = 0..50, flattened</a>
%H A129177 P. H. Edelman, R. Simion and D. White, <a href="https://doi.org/10.1016/0012-365X(92)90366-N">Partition statistics on permutations</a>, Discrete Math. 99 (1992), 63-68.
%H A129177 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 A129177 Generating polynomial of row n is P[n](t) = Product_{i=0..n-1} (i + t^i).
%F A129177 Sum_{k=0..n*(n-1)/2} (k+1) * T(n,k) = A121586(n). - _Alois P. Heinz_, May 04 2023
%e A129177 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.
%e A129177 Triangle starts:
%e A129177    1;
%e A129177    1;
%e A129177    1,  1;
%e A129177    2,  2,  1,  1;
%e A129177    6,  6,  3,  5,  2,  1,  1;
%e A129177   24, 24, 12, 20, 14, 10,  7,  5,  2,  1,  1;
%p A129177 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
%p A129177 # second Maple program:
%p A129177 p:= proc(n) option remember; `if`(n<0, 1, expand((n+t^n)*p(n-1))) end:
%p A129177 T:= n-> (h-> seq(coeff(h,t,i), i=0..degree(h)))(p(n-1)):
%p A129177 seq(T(n), n=0..8);  # _Alois P. Heinz_, Dec 16 2016
%t A129177 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_ *)
%Y A129177 Cf. A000142, A001710, A067318, A121586.
%K A129177 nonn,tabf
%O A129177 0,5
%A A129177 _Emeric Deutsch_, Apr 11 2007
%E A129177 One term for row n=0 prepended by _Alois P. Heinz_, Dec 16 2016