A008971 Triangle read by rows: T(n,k) is the number of permutations of [n] with k increasing runs of length at least 2.

1, 1, 1, 1, 1, 5, 1, 18, 5, 1, 58, 61, 1, 179, 479, 61, 1, 543, 3111, 1385, 1, 1636, 18270, 19028, 1385, 1, 4916, 101166, 206276, 50521, 1, 14757, 540242, 1949762, 1073517, 50521, 1, 44281, 2819266, 16889786, 17460701, 2702765, 1, 132854, 14494859

Offset: 0

Author

N. J. A. Sloane

Keywords

• tabf
• nonn
• easy

Comments

Row n has 1+floor(n/2) terms.

T(n,k) is also the number of permutations of [n] with k "exterior peaks" where we count peaks in the usual way, but add a peak at the beginning if the permutation begins with a descent, e.g. 213 has one exterior peak. T(3,1) = 5 since all permutations of [3] have an exterior peak except 123. This is also the definition for peaks of signed permutations, where we assume that a signed permutation always begins with a zero. - Kyle Petersen, Jan 14 2005

From Petros Hadjicostas, Aug 09 2019: (Start)

In their book, David and Barton (1962) use the notation T_{N,v*}^* for this array, where N is the length of the permutation and v* is the so-called "number of runs up" in the permutation. In modern terminology, a "run up" in a permutation is an increasing run of length >= 2. See their discussion on p. 154 of their book and see p. 163 for the definition of T_{N,v*}^*.

They do not consider as "runs up" single elements b_i in a permutation b = (b_1, b_2, ..., b_n) even if they satisfy b_{i-1} > b_i > b_{i+1} (with b_{n-1} > b_n when i = n and b_1 > b_2 when i = 1). (The command Runs[b] for permutation b in Mathematica, using the package Combinatorica`, will generate not only the "runs up" of b but also the single elements in the permutation b that satisfy one of the above inequalities. For example, Runs[{3,2,1}] gives the set of runs {{3}, {2}, {1}}, none of which is a "run up".)

So, here n = N and k = v*. On p. 163 of their book they give the recurrence shown below in the FORMULA section from Charalambides' (2002) book: T(n+1, k) = (2*k + 1) * T(n,k) + (n - 2*k + 2) * T(n, k-1) for n >= 0 and 1 <= k <= floor(n/2) + 1. The values of T_{N,v*}^* = T(n, k) appear in Table 10.5 (p. 163) of their book.

Since the complement of a permutation (b_1, b_2, ..., b_n) is (n+1-b_1, n+1-b_2, ..., n+1-b_n), it is clear that the current array T(n, k) is also the number of permutations of [n] with k decreasing runs of length >= 2 (i.e., the number of permutations of [n] with k "runs down" according to David and Barton (1962)).

Note that the number of permutations of [n] with k runs of length >= 2 that are either increasing or decreasing (i.e., the number of permutations of [n] that contain k "runs up" and "runs down" in total) is given by array A059427. One half of array A059427 is given in Table 10.4 (p. 159) in David and Barton (1962)--see also array A008970.

A run that is either a "run up" or "run down" (i.e., an ascending or a descending run of length >= 2) is called "séquence" by André (19th century) and Comtet (1974). See the references for sequence A000708 or for array A059427. (Again, recall that David and Barton do not consider single numbers as either a "run up" or a "run down".)

Morley (1897) proved that in a permutation of [n], #("runs up") + #("runs down") + #(monotonic triplets of adjacent numbers in the permutation) = n - 1. (His definition of a run is highly non-standard!) See the example below.

The number Q(n,k) of circular permutations of [n] that contain k runs that are either "runs up" or "runs down" (that is, k ascending or descending runs of length >= 2) is given by array A008303. More precisely, Q(n+1, 2*(k+1)) = A008303(n, k) for n >= 1 and 0 <= k <= ceiling(n/2)-1. In addition, Q(n, s) = 0 when either s is odd, or n <= 1, or s > n. Also, Q_{n,2} = 2^(n-2) for n >= 2.

The numbers in array A008303 appear in Table 10.6 (p. 163) in David and Barton (1962).

(End)

Examples

			Triangle T(n,k) (with rows n >= 0 and columns k >= 0) starts as follows:
  1;
  1;
  1,   1;
  1,   5;
  1,  18,       5;
  1,  58,      61;
  1, 179,     479,     61;
  1, 543,    3111,   1385;
  1, 1636,  18270,  19028,  1385;
  1, 4916, 101166, 206276, 50521;
  ...
Example: T(3,1) = 5 because all permutations of [3] with the exception of 321 have one increasing run of length at least 2.
From _Peter Bala_, Jan 23 2016: (Start)
Row 6: cos(x)^7*(d/dx)^6(1/cos(x)) = sin(x)^6 + 179*sin(x)^4 + 479*sin(x)^2 + 61.
Equivalently, (sqrt(1 - x^2))^7*D^6(1/sqrt(1 - x^2)) = x^6 + 179*x^4 + 479*x^2 + 61, where D = sqrt(1 - x^2)*d/dx. (End)
From _Petros Hadjicostas_, Aug 09 2019: (Start)
Consider the permutations of [4]. We list the increasing runs of length at least 2 (= "runs up"), the decreasing runs of length at least 2 (= "runs down"), and the monotonic triplets of adjacent numbers in the permutation (which we abbreviate to MTAN for simplicity). The sum of the numbers of these three should be n-1 (see Morley (1897) but notice that his use of the word "run" is highly non-standard).
1234 -> "runs up" = {1234}, "runs down" = {}, MTAN = {123, 234}.
1243 -> "runs up" = {124}, "runs down" = {43}, MTAN = {124}.
1324 -> "runs up" = {13, 24}, "runs down" = {32}, MTAN = {}.
1342 -> "runs up" = {134}, "runs down" = {42}, MTAN = {134}.
1423 -> "runs up" = {14, 23}, "runs down" = {42}, MTAN = {}.
1432 -> "runs up" = {14}, "runs down" = {432}, MTAN = {432}.
2134 -> "runs up" = {134}, "runs down" = {21}, MTAN = {134}.
2143 -> "runs up" = {14}, "runs down" = {21, 43}, MTAN = {}.
2314 -> "runs up" = {23, 14}, "runs down" = {31}, MTAN = {}.
2341 -> "runs up" = {234}, "runs down" = {41}, MTAN = {234}.
2413 -> "runs up" = {24, 13}, "runs down" = {41}, MTAN = {}.
2431 -> "runs up" = {24}, "runs down" = {431}, MTAN = {431}.
3124 -> "runs up" = {124}, "runs down" = {31}, MTAN = {124}.
3142 -> "runs up" = {14}, "runs down" = {31, 42}, MTAN = {}.
3214 -> "runs up" = {14}, "runs down" = {321}, MTAN = {321}.
3241 -> "runs up" = {24}, "runs down" = {32, 41}, MTAN = {}.
3412 -> "runs up" = {34, 12}, "runs down" = {41}, MTAN = {}.
3421 -> "runs up" = {34}, "runs down" = {421}, MTAN = {421}.
4123 -> "runs up" = {123}, "runs down" = {41}, MTAN = {123}.
4132 -> "runs up" = {13}, "runs down" = {41, 32}, MTAN = {}.
4213 -> "runs up" = {13}, "runs down" = {421}, MTAN = {421}.
4231 -> "runs up" = {23}, "runs down" = {42, 31}, MTAN = {}.
4312 -> "runs up" = {12}, "runs down" = {431}, MTAN = {431}.
4321 -> "runs up" = {}, "runs down" = {4321}, MTAN = {432, 321}.
If we let k = number of increasing runs of length >= 2 (= number of "runs up") in a permutation of [4], then (from above) the possible values of k are 0, 1, 2, and we have T(n=4, k=0) = 1, T(n=4, k=1) = 18, and T(n=4, k=2) = 5.
If we let k = number of decreasing runs of length >= 2 (= number of "runs down") in a permutation of [4], then again the possible values of k are 0, 1, 2, and we have T(n=4, k=0) = 1, T(n=4, k=1) = 18, and T(n=4, k=2) = 5.
Finally, note that if b_i, b_{i+1}, b_{i+2} is an increasing triplet of adjacent numbers in permutation b, then n+1-b_i, n+1-b_{i+1}, n+1-b_{i+2} is a decreasing triplet of adjacent numbers in the complement of b, and vice versa. For example, 4213 is the complement of 1342. Their set of monotonic triplets of adjacent numbers are {421} and {134}, respectively, and we have 4 + 1 = 2 + 3 = 1 + 4 = 5.
(End)
		

References

• Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002.
• F. N. David and D. E. Barton, Combinatorial Chance, Charles Griffin, 1962; see Table 10.5, p. 163.
• F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 260.

Links

• Alois P. Heinz, Rows n = 0..170, flattened
• David Callan, Shi-Mei Ma, and Toufik Mansour, Some Combinatorial Arrays Related to the Lotka-Volterra System, Electronic Journal of Combinatorics, Volume 22, Issue 2 (2015), Paper #P2.22.
• Shaoshi Chen, Hanqian Fang, Sergey Kitaev, and Candice X.T. Zhang, Patterns in Multi-dimensional Permutations, arXiv:2411.02897 [math.CO], 2024. See p. 7.
• C.-O. Chow and S.-M. Ma, Counting signed permutations by their alternating runs, Discrete Mathematics, Volume 323, 28 May 2014, Pages 49-57.
• C.-O. Chow, S.-M. Ma, T. Mansour, and M. Shattuck, Counting permutations by cyclic peaks and valleys, Annales Mathematicae et Informaticae, (2014), Vol. 43, pp. 43-54.
• 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.
• Qi Fang, Ya-Nan Feng, and Shi-Mei Ma, Alternating runs of permutations and the central factorial numbers, arXiv:2202.13978 [math.CO], 2022.
• FindStat - Combinatorial Statistic Finder, The number of outer peaks of a permutation
• Amy M. Fu, A Context-free Grammar for Peaks and Double Descents of Permutations, arXiv:1801.04397 [math.CO], 2018.
• Amy M. Fu and Frank Z. K. Li, Joint Distributions of Permutation Statistics and the Parabolic Cylinder Functions, arXiv:1809.07465 [math.CO], 2018.
• D. S. Hollman and H. F. Schaefer III, Arbitrary order El'yashevich-Wilson B tensor formulas for the most frequently used internal coordinates in molecular vibrational analyses, The Journal of Chemical Physics, Vol. 137, 164103 (2012). - From _N. J. A. Sloane_, Jan 01 2013
• Kathy Q. Ji, The (alpha, beta)-Eulerian Polynomials and Descent-Stirling Statistics on Permutations, arXiv:2310.01053 [math.CO], 2023. See pp. 9, 22.
• Shi-Mei Ma, Derivative polynomials and permutations by numbers of interior peaks and left peaks, arXiv preprint arXiv:1106.5781 [math.CO], 2011.
• Shi-Mei Ma, Enumeration of permutations by number of alternating runs, Discrete Math., 313 (2013), 1816-1822.
• Shi-Mei Ma, Qi Fang, Toufik Mansour, and Yeong-Nan Yeh, Alternating Eulerian polynomials and left peak polynomials, arXiv:2104.09374 [math.CO], 2021.
• Shi-Mei Ma, T. Mansour, and D. Callan, Some combinatorial arrays related to the Lotka-Volterra system, arXiv preprint arXiv:1404.0731 [math.CO], 2014.
• 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, Toufik Mansour, David G.L. Wang, and Yeong-Nan Yeh, Several variants of the Dumont differential system and permutation statistics, Science China Mathematics 60 (2018).
• Shi-Mei Ma, Jun Ma, Jean Yeh, and Yeong-Nan Yeh, The 1/k-Eulerian polynomials of type B, arXiv:2001.07833 [math.CO], 2020.
• 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.
• F. Morley, A generating function for the number of permutations with an assigned number of sequences, Bull. Amer. Math. Soc. 4 (1897), 23-28.
• L. W. Shapiro, W.-J. Woan, and S. Getu, Runs, slides and moments, SIAM J. Alg. Discrete Methods, 4 (1983), 459-466.
• Wikipedia, Florence Nightingale David.
• Bao-Xuan Zhu, Stieltjes moment properties and continued fractions from combinatorial triangles, arXiv:2007.14924 [math.CO], 2020, see p. 27.
• Yan Zhuang, Monoid networks and counting permutations by runs, arXiv preprint arXiv:1505.02308 [math.CO], 2015.
• Y. Zhuang, Counting permutations by runs, J. Comb. Theory Ser. A 142 (2016), pp. 147-176.

Crossrefs

A160486 is a sub-triangle.

A000340, A000363, A000507 equal the second, third and fourth left hand columns.

Cf. A000708, A008303, A008970, A059427.

T(2n,n) gives A000364.

Programs

Maple

G:=sqrt(1-t)/(sqrt(1-t)*cosh(x*sqrt(1-t))-sinh(x*sqrt(1-t))): Gser:=simplify(series(G,x=0,15)): for n from 0 to 14 do P[n]:=sort(expand(n!*coeff(Gser,x,n))) od: seq(seq(coeff(t*P[n],t^k),k=1..1+floor(n/2)),n=0..14); # edited by Johannes W. Meijer, May 15 2009
# second Maple program:
T:= proc(n, k) option remember; `if`(k=0, 1, `if`(k>iquo(n, 2), 0,
      (2*k+1)*T(n-1, k) +(n+1-2*k)*T(n-1, k-1)))
    end:
seq(seq(T(n, k), k=0..n/2), n=0..14); # Alois P. Heinz, Oct 16 2013

Mathematica

t[n_, 0] = 1; t[n_, k_] /; k > Floor[n/2] = 0;
t[n_ , k_ ] /; k <= Floor[n/2] := t[n, k] = (2 k + 1) t[n - 1, k] + (n - 2 k + 1) t[n - 1, k - 1];
Flatten[Table[t[n, k], {n, 0, 12}, {k, 0, Floor[n/2]}]][[1 ;; 45]] (* Jean-François Alcover, May 30 2011, after given formula *)

Formula

E.g.f.: G(t,x) = sum(T(n,k) t^k x^n/n!, 0<=k<=floor(n/2), n>=0) = sqrt(1-t)/(sqrt(1-t)*cosh(x*sqrt(1-t))-sinh(x*sqrt(1-t))) (Ira M. Gessel).

T(n+1,k) = (2*k+1)*T(n,k) + (n-2*k+2)*T(n,k-1) (see p. 542 of the Charalambides reference or p. 163 in the David and Barton book).

G.f.: T(0)/(1-x), where T(k) = 1 - y*x^2*(k+1)^2/(y*x^2*(k+1)^2 - (1 -x -2*x*k)*(1 -3*x -2*x*k)/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Nov 08 2013

From Peter Bala, Jan 23 2016: (Start)

cos(x)^(n+1)*(d/dx)^n(1/cos(x)) = Sum_{k = 0..floor(n/2)} T(n,k)*sin(x)^(n-2*k).

Equivalently, let D be the differential operator sqrt(1 - x^2)*d/dx. Then sqrt(1 - x^2)^(n+1)*D^n(1/sqrt(1 - x^2)) = Sum_{k = 0..floor(n/2)} T(n,k)*x^(n-2*k). (End)

Extensions

Edited by Emeric Deutsch and Ira M. Gessel, Aug 28 2004

Crossrefs added by Johannes W. Meijer, May 24 2009