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!)
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). 18
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 (list; graph; refs; listen; history; text; internal format)
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.

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: A121579 A214733 A106852 * A187244 A120294 A186766

Adjacent sequences:  A162972 A162973 A162974 * A162976 A162977 A162978

KEYWORD

nonn,tabf

AUTHOR

Emeric Deutsch, Jul 26 2009

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 July 26 01:20 EDT 2021. Contains 346294 sequences. (Running on oeis4.)