login
Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k up-down runs (1 <= k <= n).
7

%I #65 Aug 08 2023 14:47:02

%S 1,1,1,1,3,2,1,7,11,5,1,15,43,45,16,1,31,148,268,211,61,1,63,480,1344,

%T 1767,1113,272,1,127,1509,6171,12099,12477,6551,1385,1,255,4661,26955,

%U 74211,111645,94631,42585,7936,1,511,14246,114266,425976,878856,1070906,770246,303271,50521

%N Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k up-down runs (1 <= k <= n).

%C The up-down runs of a permutation p are the alternating runs of the permutation p endowed with a 0 in the front. For example, 75814632 has 6 up-down runs: 07, 75, 58, 81, 146, and 632.

%H Alois P. Heinz, <a href="/A186370/b186370.txt">Rows n = 1..141, flattened</a>

%H Ming-Jian Ding and Bao-Xuan Zhu, <a href="https://doi.org/10.1016/j.aam.2023.102591">Some results related to Hurwitz stability of combinatorial polynomials</a>, Advances in Applied Mathematics, Volume 152, (2024), 102591. See p. 13.

%H M. A. Eisenstein-Taylor, <a href="https://doi.org/10.1016/S0196-8858(02)00526-2">Polytopes, permutation shapes and bin packing</a>, Adv. Appl. Math., 30 (2003), 96-109.

%H Shi-Mei Ma, <a href="http://dx.doi.org/10.1016/j.disc.2013.05.010">Enumeration of permutations by number of alternating runs</a>, Discrete Math., 313 (2013), 1816-1822.

%H Shi-Mei Ma, T. Mansour and D. G. L. Wang, <a href="http://arxiv.org/abs/1403.0233">Combinatorics of Dumont differential system on the Jacobi elliptic functions</a>, arXiv preprint arXiv:1403.0233 [math.CO], 2014.

%H Shi-Mei Ma and Yeong-Nan Yeh, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p14">The Peak Statistics on Simsun Permutations</a>, Elect. J. Combin., 23 (2016), P2.14; <a href="https://arxiv.org/abs/1601.06505">arXiv preprint</a>, arXiv:1601.06505 [math.CO], 2016.

%H Thomas Selig, J. P. Smith, and E. Steingrimsson, <a href="https://arxiv.org/abs/1711.01622">EW-tableaux, Le-tableaux, tree-like tableaux and the Abelian sandpile model</a>, arXiv preprint arXiv:1711.01622 [math.CO], 2017.

%H Bao-Xuan Zhu, <a href="https://arxiv.org/abs/1609.01544">Stability of iterated polynomials and linear transformations preserving the strong q-log-convexity</a>, arXiv preprint arXiv:1609.01544 [math.CO], 2016.

%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 Yan 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 T(n,2) = 2^{n-1}-1 = A000225(n-1).

%F T(n,n) = A000111(n) (the Euler or up-down numbers).

%F Sum_{k=1..n} k*T(n,k) = A186371(n).

%F E.g.f.: G(t,z) = Sum_{n>=1} Sum_{k>=1} T(n,k) * t^k * z^n / n! = (w^2 + tw*sinh(zw))/[(1+t)(1-t*cosh(zw))]-1, where w=sqrt(1-t^2).

%F The e.g.f. G(t,z) satisfies the linear homogeneous partial differential equation (1-t^2*z)(dG/dz)-t(1-t^2)dG/dt = tG; G(0,z)=1.

%F Recurrence: T(n,k) = k*T(n-1,k) + T(n-1,k-1) + (n-k+1)*T(n-1,k-2); T(n,0) = T(0,k) = 0, T(1,1) = 1.

%e T(3,2) = 3 because we have 132, 231, and 321.

%e T(4,4) = 5 because we have 13254, 14253, 14352, 15243, and 15342 (the up-down permutations).

%e Triangle starts:

%e 1;

%e 1, 1;

%e 1, 3, 2;

%e 1, 7, 11, 5;

%e 1, 15, 43, 45, 16;

%p w := sqrt(1-t^2): G := (w^2+t*w*sinh(z*w))/((1+t)*(1-t*cosh(z*w)))-1: Gser := simplify(series(G, z = 0, 12)): for n to 10 do P[n] := sort(expand(factorial(n)*coeff(Gser, z, n))) end do: for n to 10 do seq(coeff(P[n], t, k), k = 1 .. n) end do; # yields sequence in triangular form

%p # second Maple program:

%p b:= proc(u, o) option remember; expand(`if`(u+o=0, 1,

%p add(b(o+j-1, u-j)*x, j=1..u)+

%p add(b(u+j-1, o-j), j=1..o)))

%p end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n, 0)):

%p seq(T(n), n=1..12); # _Alois P. Heinz_, Aug 29 2017, Apr 17 2018

%t b[u_, o_, t_] := b[u, o, t] = Expand[If[u + o == 0, 1, Sum[b[u - j, o + j - 1, 0]*x^t, {j, 1, u}] + Sum[b[u + j - 1, o - j, 1]*x^(1-t), {j, 1, o}]]];

%t T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 1, n}]][b[0, n, 0]];

%t Table[T[n], {n, 1, 12}] // Flatten (* _Jean-François Alcover_, Nov 06 2017, after _Alois P. Heinz_ *)

%o (Sage)

%o @CachedFunction

%o def A186370(n, k):

%o if n == 0 or k == 0: return 0

%o if n == 1 and k == 1: return 1

%o return k*A186370(n-1, k) + A186370(n-1, k-1) + (n-k+1)*A186370(n-1, k-2)

%o for n in (1..7): [A186370(n, k) for k in (1..n)] # _Peter Luschny_, Apr 18 2014

%Y Cf. A000225, A000111, A059427, A186371.

%Y Row sums give A000142.

%Y T(2n,n) gives A291677, T(2n+1,n+1) gives A303159, T(n,ceiling(n/2)) gives A303160.

%K nonn,tabl

%O 1,5

%A _Emeric Deutsch_ and _Ira M. Gessel_, Mar 01 2011