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