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

%I #85 Feb 09 2023 09:51:26

%S 2,2,4,2,12,10,2,28,58,32,2,60,236,300,122,2,124,836,1852,1682,544,2,

%T 252,2766,9576,14622,10332,2770,2,508,8814,45096,103326,119964,69298,

%U 15872,2,1020,27472,201060,650892,1106820,1034992,505500,101042,2,2044

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

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

%D L. Comtet, Advanced Combinatorics, Reidel, Dordrecht, Holland, 1974, p. 261, #13.

%D F. N. David and D. E. Barton, Combinatorial Chance, Hafner, NY, 1962, pp. 157-162.

%D 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 D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1973, Vol. 3, pp. 46 and 587-8.

%H T. D. Noe, <a href="/A059427/b059427.txt">Rows n = 2..50 of triangle, flattened</a>

%H Désiré André, <a href="http://sites.mathdoc.fr/JMPA/PDF/JMPA_1881_3_7_A10_0.pdf">Sur les permutations alternées</a>, J. Math. Pur. Appl., 7 (1881), 167-184.

%H Désiré André, <a href="http://www.numdam.org/numdam-bin/item?id=ASENS_1884_3_1__121_0">Étude sur les maxima, minima et séquences des permutations</a>, Ann. Sci. Ecole Norm. Sup., 3, no. 1 (1884), 121-135.

%H Désiré André, <a href="http://sites.mathdoc.fr/JMPA/PDF/JMPA_1895_5_1_A7_0.pdf">Mémoire sur les permutations quasi-alternées</a>, Journal de mathématiques pures et appliquées 5e série, tome 1 (1895), 315-350.

%H Désiré André, <a href="https://doi.org/10.24033/bsmf.519">Mémoire sur les séquences des permutations circulaires</a>, Bulletin de la S. M. F., tome 23 (1895), pp. 122-184.

%H M. Bona and R. Ehrenborg, <a href="http://dx.doi.org/10.1006/jcta.1999.3040">A combinatorial proof of the log-concavity of the numbers of permutations with k runs</a>, J. Comb. Theory, Ser. A, 90, 293-303, 2003.

%H E. Rodney Canfield and Herbert S. Wilf, <a href="https://arxiv.org/abs/math/0609704">Counting permutations by their runs up and down</a>, arXiv:math/0609704 [math.CO], 2006.

%H E. R. Canfield and H. S. Wilf, <a href="http://dx.doi.org/10.1016/j.jcta.2007.05.006">Counting permutations by their alternating runs</a>, J. Combin. Theory Ser. A 115 (2008), 213-225.

%H L. Carlitz, <a href="http://www.fq.math.ca/Scanned/16-3/carlitz6.pdf">Enumeration of permutations by sequences</a>, Fib. Quart., 16 (1978), 259-268.

%H L. Carlitz, <a href="http://www.fq.math.ca/Scanned/18-4/carlitz.pdf">The number of permutations with a given number of sequences</a>, Fib. Quart., 18 (1980), 347-352.

%H 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 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 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 Ira M. Gessel and Yan Zhuang, <a href="http://arxiv.org/abs/1408.1886">Counting permutations by alternating descents </a>, arXiv:1408.1886 [math.CO], 2014.

%H Shi-Mei Ma, <a href="http://arxiv.org/abs/1110.6779">An explicit formula for the number of permutations with a given number of alternating runs</a>, arXiv preprint arXiv:1110.6779 [math.CO], 2011 [Version 1 references the OEIS and sequence A059427; this reference was deleted in Version 2]

%H Shi-Mei Ma, <a href="http://arxiv.org/abs/1110.5014">Enumeration of permutations by number of alternating runs</a>, arXiv:1110.5014 [math.CO], 2011-2012.

%H 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 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-2018.

%H S.-M. Ma and T. Mansour, <a href="http://arxiv.org/abs/1409.6525">The 1/k-Eulerian polynomials and k-Stirling permutations</a>, arXiv preprint arXiv:1409.6525 [math.CO], 2014.

%H Shi-Mei Ma and Hai-Na Wang, <a href="http://arxiv.org/abs/1506.08716">Enumeration of a dual set of Stirling permutations by their alternating runs</a>, arXiv:1506.08716 [math.CO], 2015.

%H R. P. Stanley, <a href="https://arxiv.org/abs/math/0511419">Longest alternating subsequences of permutations</a>, arXiv:math/0511419 [math.CO], 2005.

%H R. P. Stanley, <a href="http://dx.doi.org/10.1307/mmj/1220879431">Longest alternating subsequences of permutations</a>, Michigan Math. J. 57 (2008), 675-687.

%H 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-2016.

%H 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 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

%F 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.

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

%F 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.

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

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

%e 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.

%e Triangle (with rows n >= 2 and columns k >= 1) begins as follows:

%e 2;

%e 2, 4;

%e 2, 12, 10;

%e 2, 28, 58, 32;

%e 2, 60, 236, 300, 122;

%e 2, 124, 836, 1852, 1682, 544;

%e ...

%p 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);

%t 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 t[2, 1] = 2; t[n_, k_] /; n < 2 || k < 1 || k >= n = 0;

%t Flatten[Table[t[n, k], {n,2,11}, {k, 1, n-1}]][[1 ;; 47]]

%t (* _Jean-François Alcover_, Jun 16 2011, after recurrence *)

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

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

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

%K tabl,nonn,easy,nice

%O 2,1

%A _N. J. A. Sloane_, Jan 31 2001

%E Edited by _Emeric Deutsch_ and _Ira M. Gessel_, Dec 06 2004

%E André reference from _Philippe Deléham_, Jul 26 2006