|
%I #20 Sep 05 2021 05:44:11
%S 1,1,1,1,3,2,1,9,11,3,1,39,48,28,4,1,189,297,166,62,5,1,1107,1902,
%T 1419,476,129,6,1,7281,14391,11637,5507,1235,261,7,1,54351,118044,
%U 111438,56400,19096,3020,522,8,1,448821,1078245,1119312,673128,239146,61986
%N Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k double descents and initial descents (n>=0; 0<=k<=max(0,n-1)) [we say that i is a doubledescent of a permutation p if p(i) > p(i+1) > p(i+2); we say that a permutation p has an initial descent if p(1) > p(2)].
%C Sum of entries in row n is n! = A000142(n).
%C T(n,0) = A080635(n).
%D I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983 (p. 195).
%H Alois P. Heinz, <a href="/A162976/b162976.txt">Rows n = 0..141, flattened</a>
%H Yan Zhuang, <a href="http://arxiv.org/abs/1505.02308">Monoid networks and counting permutations by runs</a>, arXiv preprint, 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.: G(t,z) = [exp(bz)-exp(az)]/[b*exp(az)-a*exp(bz)], where a+b=1+t and ab=1.
%e T(4,2) = 3 because each of the permutations 4312, 4213, and 3214 has one doubledescent and one initial descent.
%e Triangle starts:
%e : 1;
%e : 1;
%e : 1, 1;
%e : 3, 2, 1;
%e : 9, 11, 3, 1;
%e : 39, 48, 28, 4, 1;
%e : 189, 297, 166, 62, 5, 1;
%p eq := s^2-(t+1)*s+1 = 0: sol := solve(eq, s): a := sol[1]: b := sol[2]: G := (exp(b*z)-exp(a*z))/(b*exp(a*z)-a*exp(b*z)): Gser := simplify(series(G, z = 0, 15)): P[0]:=1: for n to 11 do P[n] := sort(expand(factorial(n)*coeff(Gser, z, n))) end do: for n from 0 to 11 do seq(coeff(P[n], t, j), j = 0 .. max(0,n-1)) end do;
%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(0, n, 1)):
%p seq(T(n), n=0..15); # _Alois P. Heinz_, Dec 09 2016
%t b[u_, o_, t_] := b[u, o, t] = If[u+o == 0, 1, Expand[Sum[b[u-j, o+j-1, 1], {j, 1, u}] + Sum[b[u + j - 1, o - j, 2]*If[t == 2, x, 1], {j, 1, o}]]]; T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}] ][b[0, n, 1]]; Table[T[n], {n, 0, 15}] // Flatten (* _Jean-François Alcover_, Dec 22 2016, after _Alois P. Heinz_ *)
%Y Cf. A000142, A080635, A162975.
%K nonn,tabf
%O 0,5
%A _Emeric Deutsch_, Jul 26 2009
%E One term for row n=0 prepended by _Alois P. Heinz_, Dec 09 2016
|
