The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A186370 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
 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, 1767, 1113, 272, 1, 127, 1509, 6171, 12099, 12477, 6551, 1385, 1, 255, 4661, 26955, 74211, 111645, 94631, 42585, 7936, 1, 511, 14246, 114266, 425976, 878856, 1070906, 770246, 303271, 50521 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 1,5 COMMENTS 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. LINKS Alois P. Heinz, Rows n = 1..141, flattened M. A. Eisenstein-Taylor, Polytopes, permutation shapes and bin packing, Adv. Appl. Math., 30 (2003), 96-109. Shi-Mei Ma, Enumeration of permutations by number of alternating runs, Discrete Math., 313 (2013), 1816-1822. S.-M. Ma, T. Mansour and D. G. L. Wang, Combinatorics of Dumont differential system on the Jacobi elliptic functions, arXiv preprint arXiv:1403.0233 [math.CO], 2014. Shi-Mei Ma, Yeong-Nan Yeh, The Peak Statistics on Simsun Permutations, Elect. J. Combin., 23 (2016), P2.14; arXiv preprint, arXiv:1601.06505 [math.CO], 2016. Thomas Selig, J. P. Smith, E. Steingrimsson, EW-tableaux, Le-tableaux, tree-like tableaux and the Abelian sandpile model, arXiv preprint arXiv:1711.01622 [math.CO], 2017. Bao-Xuan Zhu, Stability of iterated polynomials and linear transformations preserving the strong q-log-convexity, arXiv preprint arXiv:1609.01544 [math.CO], 2016. Yan Zhuang, Monoid networks and counting permutations by runs, arXiv preprint, arXiv:1505.02308 [math.CO], 2015. FORMULA T(n,2) = 2^{n-1}-1 = A000225(n-1). T(n,n) = A000111(n) (the Euler or up-down numbers). Sum_{k=1..n} k*T(n,k) = A186371(n). 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). 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. 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. EXAMPLE T(3,2) = 3 because we have 132, 231, and 321. T(4,4) = 5 because we have 13254, 14253, 14352, 15243, and 15342 (the up-down permutations). Triangle starts: 1; 1,  1; 1,  3,  2; 1,  7, 11,  5; 1, 15, 43, 45, 16; MAPLE 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 # second Maple program: b:= proc(u, o) option remember; expand(`if`(u+o=0, 1,        add(b(o+j-1, u-j)*x, j=1..u)+        add(b(u+j-1, o-j),   j=1..o)))     end: T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n, 0)): seq(T(n), n=1..12);  # Alois P. Heinz, Aug 29 2017, Apr 17 2018 MATHEMATICA 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[n_] := Function[p, Table[Coefficient[p, x, i], {i, 1, n}]][b[0, n, 0]]; Table[T[n], {n, 1, 12}] // Flatten (* Jean-François Alcover, Nov 06 2017, after Alois P. Heinz *) PROG (Sage) @CachedFunction def A186370(n, k):     if n == 0 or  k == 0: return 0     if n == 1 and k == 1: return 1     return k*A186370(n-1, k) + A186370(n-1, k-1) + (n-k+1)*A186370(n-1, k-2) for n in (1..7): [A186370(n, k) for k in (1..n)] # Peter Luschny, Apr 18 2014 CROSSREFS Cf. A000225, A000111, A059427, A186371. T(2n,n) gives A291677, T(2n+1,n+1) gives A303159, T(n,ceiling(n/2)) gives A303160. Sequence in context: A056151 A134436 A306226 * A163626 A028246 A082038 Adjacent sequences:  A186367 A186368 A186369 * A186371 A186372 A186373 KEYWORD nonn,tabl AUTHOR Emeric Deutsch and Ira M. Gessel, Mar 01 2011 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.

Last modified May 6 15:28 EDT 2021. Contains 343586 sequences. (Running on oeis4.)