A291677 -id:A291677 - cp's OEIS frontend

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

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

Offset: 1

Emeric Deutsch and Ira M. Gessel, Mar 01 2011

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.

			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;

Alois P. Heinz, Rows n = 1..141, flattened
Ming-Jian Ding and Bao-Xuan Zhu, Some results related to Hurwitz stability of combinatorial polynomials, Advances in Applied Mathematics, Volume 152, (2024), 102591. See p. 13.
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.
Shi-Mei 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 and 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, and 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.
Yan Zhuang, Counting permutations by runs, J. Comb. Theory Ser. A 142 (2016), pp. 147-176.

Cf. A000225, A000111, A059427, A186371.
Row sums give A000142.
T(2n,n) gives A291677, T(2n+1,n+1) gives A303159, T(n,ceiling(n/2)) gives A303160.

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

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

@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

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.

A303160 Number of permutations p of [n] such that 0p has exactly ceiling(n/2) alternating runs.

Original entry on oeis.org

1, 1, 1, 3, 7, 43, 148, 1344, 6171, 74211, 425976, 6384708, 43979902, 789649750, 6346283560, 132789007200, 1219725741715, 29145283614115, 301190499710320, 8092186932120060, 92921064554444490, 2772830282722806978, 35025128774218944648, 1149343084932146388144

Offset: 0

Alois P. Heinz, Apr 19 2018

nonn

			a(2) = 1: 12.
a(3) = 3: 132, 231, 321.
a(4) = 7: 1243, 1342, 1432, 2341, 2431, 3421, 4321.

Alois P. Heinz, Table of n, a(n) for n = 0..456

Bisections give: A291677 (even part), A303159 (odd part).

Cf. A186370.

b:= proc(n, k) option remember; `if`(k=0,
      `if`(n=0, 1, 0), `if`(k<0 or k>n, 0,
       k*b(n-1, k)+b(n-1, k-1)+(n-k+1)*b(n-1, k-2)))
    end:
a:= n-> b(n, ceil(n/2)):
seq(a(n), n=0..25);

b[n_, k_] := b[n, k] = If[k == 0,
     If[n == 0, 1, 0], If[k < 0 || k > n, 0,
     k*b[n-1, k] + b[n-1, k-1] + (n-k+1)*b[n-1, k-2]]];
a[n_] := b[n, Ceiling[n/2]];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Aug 31 2021, after Alois P. Heinz *)

a(n) = A186370(n,ceiling(n/2)).

A360426 Number of permutations of [2n] having exactly n alternating up/down runs where the first run is not a down run.

Original entry on oeis.org

1, 1, 6, 118, 4788, 325446, 33264396, 4766383420, 911323052520, 224136553339270, 68929638550210620, 25914939202996628148, 11693626371194331008088, 6236691723226152102621084, 3881046492003600271067466744, 2786922888404654795314066258488, 2287283298159853722760705106305488

Offset: 0

Alois P. Heinz, Feb 08 2023

nonn

Number of permutations of [2n] such that the differences have n runs with the same signs where the first run does not have negative signs.

			a(0) = 1: (), the empty permutation.
a(1) = 1: 12.
a(2) = 6: 1243, 1342, 1432, 2341, 2431, 3421.
a(3) = 118: 123546, 123645, 124356, ..., 564123, 564213, 564312.

Alois P. Heinz, Table of n, a(n) for n = 0..228

Cf. A000111, A008970, A059427.

b:= proc(n, k) option remember; `if`(n<2, 0, `if`(k=1, 1,
      k*b(n-1, k) + 2*b(n-1, k-1) + (n-k)*b(n-1, k-2)))
    end:
a:= n-> `if`(n=0, 1, b(2*n, n)):
seq(a(n), n=0..17);

a(n) = A008970(2n,n) = (1/2) * A059427(2n,n) for n>=1.

a(n) ~ c * d^n * n!^2 / n, where d = 3.421054620671187024940215794079585351303138828348... (same as for A291677 and A303159) and c = 0.23613698601500409294656476488227001191406... - Vaclav Kotesovec, Feb 18 2023

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

A303160 Number of permutations p of [n] such that 0p has exactly ceiling(n/2) alternating runs.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A360426 Number of permutations of [2n] having exactly n alternating up/down runs where the first run is not a down run.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula