login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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)). 1
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, 100, 70, 74, 59, 37, 30, 19, 15, 7, 5, 2, 1, 1, 720, 720, 360, 600, 420, 444, 474, 342, 240, 214, 160, 116, 89, 49, 36, 25, 15, 7, 5, 2, 1, 1, 5040, 5040, 2520, 4200, 2940, 3108, 3318 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

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

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

LINKS

Alois P. Heinz, Rows n = 0..50, flattened

P. H. Edelman, R. Simion and D. White, Partition statistics on permutations, Discrete Math. 99 (1992), 63-68.

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) = Product_{i=0..n-1} (i + t^i).

EXAMPLE

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.

Triangle starts:

   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;

MAPLE

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

# second Maple program:

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

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

seq(T(n), n=0..8);  # Alois P. Heinz, Dec 16 2016

MATHEMATICA

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

CROSSREFS

Cf. A000142, A001710, A067318.

Sequence in context: A114626 A221916 A124773 * A127452 A263755 A135879

Adjacent sequences:  A129174 A129175 A129176 * A129178 A129179 A129180

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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 24 16:24 EDT 2021. Contains 348233 sequences. (Running on oeis4.)