This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A008971 #168 Jan 08 2025 09:38:26
%S A008971 1,1,1,1,1,5,1,18,5,1,58,61,1,179,479,61,1,543,3111,1385,1,1636,18270,
%T A008971 19028,1385,1,4916,101166,206276,50521,1,14757,540242,1949762,1073517,
%U A008971 50521,1,44281,2819266,16889786,17460701,2702765,1,132854,14494859
%N A008971 Triangle read by rows: T(n,k) is the number of permutations of [n] with k increasing runs of length at least 2.
%C A008971 Row n has 1+floor(n/2) terms.
%C A008971 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
%C A008971 From _Petros Hadjicostas_, Aug 09 2019: (Start)
%C A008971 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*}^*.
%C A008971 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".)
%C A008971 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.
%C A008971 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)).
%C A008971 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.
%C A008971 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".)
%C A008971 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.
%C A008971 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.
%C A008971 The numbers in array A008303 appear in Table 10.6 (p. 163) in David and Barton (1962).
%C A008971 (End)
%D A008971 Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002.
%D A008971 F. N. David and D. E. Barton, Combinatorial Chance, Charles Griffin, 1962; see Table 10.5, p. 163.
%D A008971 F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 260.
%H A008971 Alois P. Heinz, <a href="/A008971/b008971.txt">Rows n = 0..170, flattened</a>
%H A008971 David Callan, Shi-Mei Ma, and Toufik Mansour, <a href="https://doi.org/10.37236/4413">Some Combinatorial Arrays Related to the Lotka-Volterra System</a>, Electronic Journal of Combinatorics, Volume 22, Issue 2 (2015), Paper #P2.22.
%H A008971 Shaoshi Chen, Hanqian Fang, Sergey Kitaev, and Candice X.T. Zhang, <a href="https://arxiv.org/abs/2411.02897">Patterns in Multi-dimensional Permutations</a>, arXiv:2411.02897 [math.CO], 2024. See p. 7.
%H A008971 C.-O. Chow and S.-M. Ma, <a href="http://dx.doi.org/10.1016/j.disc.2014.01.015">Counting signed permutations by their alternating runs</a>, Discrete Mathematics, Volume 323, 28 May 2014, Pages 49-57.
%H A008971 C.-O. Chow, S.-M. Ma, T. Mansour, and M. Shattuck, <a href="http://ami.ektf.hu/uploads/papers/finalpdf/AMI_43_from43to54.pdf">Counting permutations by cyclic peaks and valleys</a>, Annales Mathematicae et Informaticae, (2014), Vol. 43, pp. 43-54.
%H A008971 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 A008971 Qi Fang, Ya-Nan Feng, and Shi-Mei Ma, <a href="https://arxiv.org/abs/2202.13978">Alternating runs of permutations and the central factorial numbers</a>, arXiv:2202.13978 [math.CO], 2022.
%H A008971 FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000035/">The number of outer peaks of a permutation</a>
%H A008971 Amy M. Fu, <a href="https://arxiv.org/abs/1801.04397">A Context-free Grammar for Peaks and Double Descents of Permutations</a>, arXiv:1801.04397 [math.CO], 2018.
%H A008971 Amy M. Fu and Frank Z. K. Li, <a href="https://arxiv.org/abs/1809.07465">Joint Distributions of Permutation Statistics and the Parabolic Cylinder Functions</a>, arXiv:1809.07465 [math.CO], 2018.
%H A008971 D. S. Hollman and H. F. Schaefer III, <a href="http://dx.doi.org/10.1063/1.4759170">Arbitrary order El'yashevich-Wilson B tensor formulas for the most frequently used internal coordinates in molecular vibrational analyses</a>, The Journal of Chemical Physics, Vol. 137, 164103 (2012). - From _N. J. A. Sloane_, Jan 01 2013
%H A008971 Kathy Q. Ji, <a href="https://arxiv.org/abs/2310.01053">The (alpha, beta)-Eulerian Polynomials and Descent-Stirling Statistics on Permutations</a>, arXiv:2310.01053 [math.CO], 2023. See pp. 9, 22.
%H A008971 Shi-Mei Ma, <a href="http://arxiv.org/abs/1106.5781">Derivative polynomials and permutations by numbers of interior peaks and left peaks</a>, arXiv preprint arXiv:1106.5781 [math.CO], 2011.
%H A008971 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 A008971 Shi-Mei Ma, Qi Fang, Toufik Mansour, and Yeong-Nan Yeh, <a href="https://arxiv.org/abs/2104.09374">Alternating Eulerian polynomials and left peak polynomials</a>, arXiv:2104.09374 [math.CO], 2021.
%H A008971 Shi-Mei Ma, T. Mansour, and D. Callan, <a href="http://arxiv.org/abs/1404.0731">Some combinatorial arrays related to the Lotka-Volterra system</a>, arXiv preprint arXiv:1404.0731 [math.CO], 2014.
%H A008971 S.-M. 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 A008971 Shi-Mei Ma, Toufik Mansour, David G.L. Wang, and Yeong-Nan Yeh, <a href="https://www.math.sinica.edu.tw/www/file_upload/mayeh/2018SCM-2016-0688.pdf">Several variants of the Dumont differential system and permutation statistics</a>, Science China Mathematics 60 (2018).
%H A008971 Shi-Mei Ma, Jun Ma, Jean Yeh, and Yeong-Nan Yeh, <a href="https://arxiv.org/abs/2001.07833">The 1/k-Eulerian polynomials of type B</a>, arXiv:2001.07833 [math.CO], 2020.
%H A008971 Shi-Mei Ma and Yeong-Nan Yeh, <a href="https://doi.org/10.37236/5908">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 A008971 F. Morley, <a href="http://dx.doi.org/10.1090/S0002-9904-1897-00451-7">A generating function for the number of permutations with an assigned number of sequences</a>, Bull. Amer. Math. Soc. 4 (1897), 23-28.
%H A008971 L. W. Shapiro, W.-J. Woan, and S. Getu, <a href="http://dx.doi.org/10.1137/0604046">Runs, slides and moments</a>, SIAM J. Alg. Discrete Methods, 4 (1983), 459-466.
%H A008971 Wikipedia, <a href="https://en.wikipedia.org/wiki/Florence_Nightingale_David">Florence Nightingale David</a>.
%H A008971 Bao-Xuan Zhu, <a href="https://arxiv.org/abs/2007.14924">Stieltjes moment properties and continued fractions from combinatorial triangles</a>, arXiv:2007.14924 [math.CO], 2020, see p. 27.
%H A008971 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 A008971 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 A008971 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_).
%F A008971 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).
%F A008971 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
%F A008971 From _Peter Bala_, Jan 23 2016: (Start)
%F A008971 cos(x)^(n+1)*(d/dx)^n(1/cos(x)) = Sum_{k = 0..floor(n/2)} T(n,k)*sin(x)^(n-2*k).
%F A008971 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)
%e A008971 Triangle T(n,k) (with rows n >= 0 and columns k >= 0) starts as follows:
%e A008971 1;
%e A008971 1;
%e A008971 1, 1;
%e A008971 1, 5;
%e A008971 1, 18, 5;
%e A008971 1, 58, 61;
%e A008971 1, 179, 479, 61;
%e A008971 1, 543, 3111, 1385;
%e A008971 1, 1636, 18270, 19028, 1385;
%e A008971 1, 4916, 101166, 206276, 50521;
%e A008971 ...
%e A008971 Example: T(3,1) = 5 because all permutations of [3] with the exception of 321 have one increasing run of length at least 2.
%e A008971 From _Peter Bala_, Jan 23 2016: (Start)
%e A008971 Row 6: cos(x)^7*(d/dx)^6(1/cos(x)) = sin(x)^6 + 179*sin(x)^4 + 479*sin(x)^2 + 61.
%e A008971 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)
%e A008971 From _Petros Hadjicostas_, Aug 09 2019: (Start)
%e A008971 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).
%e A008971 1234 -> "runs up" = {1234}, "runs down" = {}, MTAN = {123, 234}.
%e A008971 1243 -> "runs up" = {124}, "runs down" = {43}, MTAN = {124}.
%e A008971 1324 -> "runs up" = {13, 24}, "runs down" = {32}, MTAN = {}.
%e A008971 1342 -> "runs up" = {134}, "runs down" = {42}, MTAN = {134}.
%e A008971 1423 -> "runs up" = {14, 23}, "runs down" = {42}, MTAN = {}.
%e A008971 1432 -> "runs up" = {14}, "runs down" = {432}, MTAN = {432}.
%e A008971 2134 -> "runs up" = {134}, "runs down" = {21}, MTAN = {134}.
%e A008971 2143 -> "runs up" = {14}, "runs down" = {21, 43}, MTAN = {}.
%e A008971 2314 -> "runs up" = {23, 14}, "runs down" = {31}, MTAN = {}.
%e A008971 2341 -> "runs up" = {234}, "runs down" = {41}, MTAN = {234}.
%e A008971 2413 -> "runs up" = {24, 13}, "runs down" = {41}, MTAN = {}.
%e A008971 2431 -> "runs up" = {24}, "runs down" = {431}, MTAN = {431}.
%e A008971 3124 -> "runs up" = {124}, "runs down" = {31}, MTAN = {124}.
%e A008971 3142 -> "runs up" = {14}, "runs down" = {31, 42}, MTAN = {}.
%e A008971 3214 -> "runs up" = {14}, "runs down" = {321}, MTAN = {321}.
%e A008971 3241 -> "runs up" = {24}, "runs down" = {32, 41}, MTAN = {}.
%e A008971 3412 -> "runs up" = {34, 12}, "runs down" = {41}, MTAN = {}.
%e A008971 3421 -> "runs up" = {34}, "runs down" = {421}, MTAN = {421}.
%e A008971 4123 -> "runs up" = {123}, "runs down" = {41}, MTAN = {123}.
%e A008971 4132 -> "runs up" = {13}, "runs down" = {41, 32}, MTAN = {}.
%e A008971 4213 -> "runs up" = {13}, "runs down" = {421}, MTAN = {421}.
%e A008971 4231 -> "runs up" = {23}, "runs down" = {42, 31}, MTAN = {}.
%e A008971 4312 -> "runs up" = {12}, "runs down" = {431}, MTAN = {431}.
%e A008971 4321 -> "runs up" = {}, "runs down" = {4321}, MTAN = {432, 321}.
%e A008971 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.
%e A008971 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.
%e A008971 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.
%e A008971 (End)
%p A008971 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
%p A008971 # second Maple program:
%p A008971 T:= proc(n, k) option remember; `if`(k=0, 1, `if`(k>iquo(n, 2), 0,
%p A008971 (2*k+1)*T(n-1, k) +(n+1-2*k)*T(n-1, k-1)))
%p A008971 end:
%p A008971 seq(seq(T(n, k), k=0..n/2), n=0..14); # _Alois P. Heinz_, Oct 16 2013
%t A008971 t[n_, 0] = 1; t[n_, k_] /; k > Floor[n/2] = 0;
%t A008971 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];
%t A008971 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 *)
%Y A008971 A160486 is a sub-triangle.
%Y A008971 A000340, A000363, A000507 equal the second, third and fourth left hand columns.
%Y A008971 Cf. A000708, A008303, A008970, A059427.
%Y A008971 T(2n,n) gives A000364.
%K A008971 tabf,nonn,easy
%O A008971 0,6
%A A008971 _N. J. A. Sloane_
%E A008971 Edited by _Emeric Deutsch_ and _Ira M. Gessel_, Aug 28 2004
%E A008971 Crossrefs added by _Johannes W. Meijer_, May 24 2009