cp's OEIS Frontend

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

%I A162975 #48 Sep 05 2021 05:43:12
%S A162975 1,1,2,5,1,17,6,1,70,41,8,1,349,274,86,10,1,2017,2040,803,167,12,1,
%T A162975 13358,16346,8221,2064,316,14,1,99377,143571,86214,28143,4961,597,16,
%U A162975 1,822041,1365354,966114,374166,88482,11486,1138,18,1
%N 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).
%C A162975 Row n (n>=2) contains n-1 entries.
%C A162975 Sum of entries in row n is n! = A000142(n).
%C A162975 Sum_{k=0..n-2} k*T(n,k) = A005990(n-1).
%C A162975 The first Maple program yields (by straightforward counting) the generating polynomial of a specified row n.
%D A162975 I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, New York, 1983.
%H A162975 Alois P. Heinz, <a href="/A162975/b162975.txt">Rows n = 0..142, flattened</a>
%H A162975 S. Elizalde and M. Noy, <a href="http://dx.doi.org/10.1016/S0196-8858(02)00527-4">Consecutive patterns in permutations</a>, Adv. Appl. Math. 30 (2003), 110-123.
%H A162975 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 210
%H A162975 Yan Zhuang, <a href="http://arxiv.org/abs/1505.02308">Monoid networks and counting permutations by runs</a>, arXiv preprint arXiv:1505.02308 [math.CO], 2015.
%H A162975 Y. Zhuang, <a href="https://doi.org/10.1016/j.jcta.2016.04.002">Counting permutations by runs</a>, J. Comb. Theory Ser. A 142 (2016), pp. 147-176.
%F A162975 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
%e A162975 T(5,2) = 8 because we have 15432, 25431, 35421, 43215, 45321, 53214, 54213, and 54312.
%e A162975 Triangle starts:
%e A162975     1;
%e A162975     1;
%e A162975     2;
%e A162975     5,   1;
%e A162975    17,   6,   1;
%e A162975    70,  41,   8,   1;
%e A162975   349, 274,  86,  10,   1;
%p A162975 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)));
%p A162975 # second Maple program:
%p A162975 b:= proc(u, o, t) option remember; `if`(u+o=0, 1, expand(
%p A162975       add(b(u-j, o+j-1, 1), j=1..u)+
%p A162975       add(b(u+j-1, o-j, 2)*`if`(t=2, x, 1), j=1..o)))
%p A162975     end:
%p A162975 T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0, 1)):
%p A162975 seq(T(n), n=0..15);  # _Alois P. Heinz_, Oct 25 2013
%t A162975 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 *)
%Y A162975 Columns k=0..10 give A049774, A274997, A230621, A279292, A279293, A279294, A279295, A279296, A279297, A279298, A279299.
%Y A162975 Cf. A000142, A005990, A162976, A242783, A242784.
%K A162975 nonn,tabf
%O A162975 0,3
%A A162975 _Emeric Deutsch_, Jul 26 2009