login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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)). 2

%I #21 May 04 2023 19:23:57

%S 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 100,70,74,59,37,30,19,15,7,5,2,1,1,720,720,360,600,420,444,474,342,

%U 240,214,160,116,89,49,36,25,15,7,5,2,1,1,5040,5040,2520,4200,2940,3108,3318

%N 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 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 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 Alois P. Heinz, <a href="/A129177/b129177.txt">Rows n = 0..50, flattened</a>

%H 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 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 Generating polynomial of row n is P[n](t) = Product_{i=0..n-1} (i + t^i).

%F Sum_{k=0..n*(n-1)/2} (k+1) * T(n,k) = A121586(n). - _Alois P. Heinz_, May 04 2023

%e 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 Triangle starts:

%e 1;

%e 1;

%e 1, 1;

%e 2, 2, 1, 1;

%e 6, 6, 3, 5, 2, 1, 1;

%e 24, 24, 12, 20, 14, 10, 7, 5, 2, 1, 1;

%p 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 # second Maple program:

%p p:= proc(n) option remember; `if`(n<0, 1, expand((n+t^n)*p(n-1))) end:

%p T:= n-> (h-> seq(coeff(h,t,i), i=0..degree(h)))(p(n-1)):

%p seq(T(n), n=0..8); # _Alois P. Heinz_, Dec 16 2016

%t 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 Cf. A000142, A001710, A067318, A121586.

%K nonn,tabf

%O 0,5

%A _Emeric Deutsch_, Apr 11 2007

%E One term for row n=0 prepended by _Alois P. Heinz_, Dec 16 2016

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 03:51 EDT 2024. Contains 371264 sequences. (Running on oeis4.)