A162975 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k doubledescents (0 <= k <= n-2). We say that i is a doubledescent (also called a double fall) of a permutation p if p(i) > p(i+1) > p(i+2).

1, 1, 2, 5, 1, 17, 6, 1, 70, 41, 8, 1, 349, 274, 86, 10, 1, 2017, 2040, 803, 167, 12, 1, 13358, 16346, 8221, 2064, 316, 14, 1, 99377, 143571, 86214, 28143, 4961, 597, 16, 1, 822041, 1365354, 966114, 374166, 88482, 11486, 1138, 18, 1

Offset

0,3

Comments

Row n (n>=2) contains n-1 entries.

Sum of entries in row n is n! = A000142(n).

Sum_{k=0..n-2} k*T(n,k) = A005990(n-1).

The first Maple program yields (by straightforward counting) the generating polynomial of a specified row n.

References

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, New York, 1983.

Links

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

S. Elizalde and M. Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-123.

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

Yan Zhuang, Monoid networks and counting permutations by runs, arXiv preprint arXiv:1505.02308 [math.CO], 2015.

Y. Zhuang, Counting permutations by runs, J. Comb. Theory Ser. A 142 (2016), pp. 147-176.

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^3/(1 - y*x - y*x^2). See Flajolet and Sedgewick reference in Links section. - Geoffrey Critzer, Dec 12 2012

Example

T(5,2) = 8 because we have 15432, 25431, 35421, 43215, 45321, 53214, 54213, and 54312.
Triangle starts:
    1;
    1;
    2;
    5,   1;
   17,   6,   1;
   70,  41,   8,   1;
  349, 274,  86,  10,   1;

Maple

n := 7: dds := proc (p) local ct, j: ct := 0: for j from 3 to nops(p) do if p[j] < p[j-1] and p[j-1] < p[j-2] then ct := ct+1 else end if end do: ct end proc: with(combinat): P := permute(n): f[n] := sort(add(t^dds(P[i]), i = 1 .. factorial(n)));
# second Maple program:
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)*`if`(t=2, 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..15);  # Alois P. Heinz, Oct 25 2013

Mathematica

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

Crossrefs

Columns k=0..10 give A049774, A274997, A230621, A279292, A279293, A279294, A279295, A279296, A279297, A279298, A279299.

Cf. A000142, A005990, A162976, A242783, A242784.

Sequence in context: A106852 A352010 A350016 * A350015 A187244 A120294

Adjacent sequences: A162972 A162973 A162974 * A162976 A162977 A162978

Keyword

nonn,tabf

Author

Emeric Deutsch, Jul 26 2009

Status

approved