A059427 Triangle read by rows: T(n,k) is the number of permutations of [n] with k alternating runs (n>=2, k>=1).

2, 2, 4, 2, 12, 10, 2, 28, 58, 32, 2, 60, 236, 300, 122, 2, 124, 836, 1852, 1682, 544, 2, 252, 2766, 9576, 14622, 10332, 2770, 2, 508, 8814, 45096, 103326, 119964, 69298, 15872, 2, 1020, 27472, 201060, 650892, 1106820, 1034992, 505500, 101042, 2, 2044

Offset: 2

Author

N. J. A. Sloane, Jan 31 2001

Keywords

• tabl
• nonn
• easy
• nice

Comments

The permutation 732569148 has 4 alternating runs: 732, 2569, 91 and 148.

Examples

			T(3,2) = 4 because each of the permutations 132, 312, 213, 231 has two alternating runs: (13, 32), (31, 12), (21, 13), (23, 31); each of 123 and 321 has 1 alternating run.
Triangle (with rows n >= 2 and columns k >= 1) begins as follows:
  2;
  2,   4;
  2,  12,  10;
  2,  28,  58,   32;
  2,  60, 236,  300,  122;
  2, 124, 836, 1852, 1682, 544;
  ...
		

References

• L. Comtet, Advanced Combinatorics, Reidel, Dordrecht, Holland, 1974, p. 261, #13.
• F. N. David and D. E. Barton, Combinatorial Chance, Hafner, NY, 1962, pp. 157-162.
• F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 262, Table 7.2.1 doubled.
• D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1973, Vol. 3, pp. 46 and 587-8.

Links

• T. D. Noe, Rows n = 2..50 of triangle, flattened
• Désiré André, Sur les permutations alternées, J. Math. Pur. Appl., 7 (1881), 167-184.
• Désiré André, Étude sur les maxima, minima et séquences des permutations, Ann. Sci. Ecole Norm. Sup., 3, no. 1 (1884), 121-135.
• Désiré André, Mémoire sur les permutations quasi-alternées, Journal de mathématiques pures et appliquées 5e série, tome 1 (1895), 315-350.
• Désiré André, Mémoire sur les séquences des permutations circulaires, Bulletin de la S. M. F., tome 23 (1895), pp. 122-184.
• M. Bona and R. Ehrenborg, A combinatorial proof of the log-concavity of the numbers of permutations with k runs, J. Comb. Theory, Ser. A, 90, 293-303, 2003.
• E. Rodney Canfield and Herbert S. Wilf, Counting permutations by their runs up and down, arXiv:math/0609704 [math.CO], 2006.
• E. R. Canfield and H. S. Wilf, Counting permutations by their alternating runs, J. Combin. Theory Ser. A 115 (2008), 213-225.
• L. Carlitz, Enumeration of permutations by sequences, Fib. Quart., 16 (1978), 259-268.
• L. Carlitz, The number of permutations with a given number of sequences, Fib. Quart., 18 (1980), 347-352.
• 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.
• Qi Fang, Ya-Nan Feng, and Shi-Mei Ma, Alternating runs of permutations and the central factorial numbers, arXiv:2202.13978 [math.CO], 2022.
• Ira M. Gessel and Yan Zhuang, Counting permutations by alternating descents , arXiv:1408.1886 [math.CO], 2014.
• Shi-Mei Ma, An explicit formula for the number of permutations with a given number of alternating runs, arXiv preprint arXiv:1110.6779 [math.CO], 2011 [Version 1 references the OEIS and sequence A059427; this reference was deleted in Version 2]
• Shi-Mei Ma, Enumeration of permutations by number of alternating runs, arXiv:1110.5014 [math.CO], 2011-2012.
• 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-2018.
• S.-M. Ma and T. Mansour, The 1/k-Eulerian polynomials and k-Stirling permutations, arXiv preprint arXiv:1409.6525 [math.CO], 2014.
• Shi-Mei Ma and Hai-Na Wang, Enumeration of a dual set of Stirling permutations by their alternating runs, arXiv:1506.08716 [math.CO], 2015.
• R. P. Stanley, Longest alternating subsequences of permutations, arXiv:math/0511419 [math.CO], 2005.
• R. P. Stanley, Longest alternating subsequences of permutations, Michigan Math. J. 57 (2008), 675-687.
• Yan Zhuang, Monoid networks and counting permutations by runs, arXiv preprint arXiv:1505.02308 [math.CO], 2015-2016.
• Y. Zhuang, Counting permutations by runs, J. Comb. Theory Ser. A 142 (2016), pp. 147-176.

Crossrefs

Diagonals give A001250, A001758. Column k = 2 is A028399.

Cf. A008303 (circular version of this array), A008970.

T(2n,n) gives 2*A360426.

Programs

Maple

P := proc(n,k) if n<2 or k<1 or k>=n then 0 elif n=2 and k=1 then 2 else k*P(n-1,k)+2*P(n-1,k-1)+(n-k)*P(n-1,k-2) fi end: p:=(n,k)->P(n+1,k): matrix(9,9,p);

Mathematica

t[n_, k_] := t[n, k] = k*t[n-1, k] + 2*t[n-1, k-1] + (n-k)*t[n-1, k-2];
t[2, 1] = 2; t[n_, k_] /; n < 2 || k < 1 || k >= n = 0;
Flatten[Table[t[n, k], {n,2,11}, {k, 1, n-1}]][[1 ;; 47]]
(* Jean-François Alcover, Jun 16 2011, after recurrence *)

Formula

P(n, k) = 0 if n < 2 or k < 1 or k >= n; P(2, 1) = 2; P(n, k) = k*P(n-1, k) + 2*P(n-1, k-1) + (n-k)*P(n-1, k-2) [André]. - Emeric Deutsch, Feb 21 2004

The row generating polynomials P[n] satisfy P[n] = t*[(1 - t^2) * dP[n-1]/dt + (2 + (n-2) * t) * P[n-1]] and P[2] = 2*t.

T(n, n-1) = 2*A000111(n) = A001250(n-1).

T(n, k) = k*T(n-1, k) + 2*T(n-1, k-1) + (n-k)*T(n-1, k-2), where we set T(2, 1) = 2 and T(n, k) = 0 if n < 2 or k < 1 or k >= n.

E.g.f.: Sum_{n, k >= 0} T(n, k) * x^n * t^k/n! = 2*(1 - t^2 + t * sqrt(1-t^2) * sinh(x * sqrt(1 - t^2)))/((1 + t)^2*(1-t*cosh(x * sqrt(1 - t^2)))) - 2(1 + t*x)/(1 + t).

T(n, k) = 2*A008970(n, k).

Extensions

Edited by Emeric Deutsch and Ira M. Gessel, Dec 06 2004

André reference from Philippe Deléham, Jul 26 2006