A220183 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k triple descents (n>=0,0<=k<=n-3). We say that i is a triple descent of a permutation p if p(i) > p(i+1) > p(i+2) > p(i+3).

1, 1, 2, 6, 23, 1, 111, 8, 1, 642, 67, 10, 1, 4326, 602, 99, 12, 1, 33333, 5742, 1093, 137, 14, 1, 288901, 59504, 12425, 1852, 181, 16, 1, 2782082, 666834, 151635, 24970, 3029, 231, 18, 1, 29471046, 8054684, 1981499, 355906, 48455, 4902, 287, 20, 1

Offset

0,3

Comments

Row sums = n!.

T(n,0) = A117158.

Links

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

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 210

Formula

E.g.f.: 1/(1 - x - Sum_{k,n} I(n,k)(y - 1)^k*x^n/n!) where I(n,k) is the coefficient of y^k*x^n in the ordinary generating function expansion of y x^4/(1 - y*x - y*x^2 - y*x^3) See Flajolet and Sedgewick reference in Links section.

Example

:     1;
:     1;
:     2;
:     6;
:    23,    1;
:   111,    8,    1;
:   642,   67,   10,   1;
:  4326,  602,   99,  12,  1;
: 33333, 5742, 1093, 137, 14, 1;
T(5,1) = 8 because we have: (4,5,3,2,1), (3,5,4,2,1), (2,5,4,3,1), (5,4,3,1,2), (1,5,4,3,2), (5,4,2,1,3), (5,3,2,1,4), (4,3,2,1,5).

Maple

b:= proc(u, o, t) option remember; `if`(u+o=0, 1, expand(
      add(b(u-j, o+j-1, 1), j=1..u)+
      add(b(u+j-1, o-j, [2, 3, 3][t])*`if`(t=3, x, 1), j=1..o)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0, 1)):
seq(T(n), n=0..14);  # Alois P. Heinz, Oct 29 2013

Mathematica

nn=10; u=y-1; a=Apply[Plus, Table[Normal[Series[y x^4/(1-y x - y x^2-y x^3), {x, 0, nn}]][[n]]/(n+3)!, {n, 1, nn-3}]]/.y->u; Range[0, nn]! CoefficientList[Series[1/(1-x-a), {x, 0, nn}], {x, y}]//Grid

Crossrefs

Cf. A162975, A242783, A242784.

Sequence in context: A350273 A264319 A264173 * A177252 A168270 A222761

Adjacent sequences: A220180 A220181 A220182 * A220184 A220185 A220186

Keyword

nonn,tabf

Author

Geoffrey Critzer, Dec 12 2012

Status

approved