login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A059427 Triangle read by rows: T(n,k) is the number of permutations of [n] with k alternating runs (n>=2, k>=1). The permutation 732569148 has 4 alternating runs: 732, 2569, 91 and 148. 6
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

2,1

REFERENCES

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.

Chow, C. O., Ma, S. M., Mansour, T., & Shattuck, M. (2014). Counting permutations by cyclic peaks and valleys, Annales Mathematicae et Informaticae (Vol. 43, pp. 43-54).

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. André, Etude sur les maxima, minima et sequences des permutations, Ann. Sci. Ecole Norm. Sup., 3, no. 1 (1884), 121-135.

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.

Ira M. Gessel, Yan Zhuang, Counting permutations by alternating descents , 2014.

Shi-Mei Ma, An explicit formula for the number of permutations with a given number of alternating runs, arXiv preprint arXiv:1110.6779, 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, 2014.

S.-M. Ma, T. Mansour, The 1/k-Eulerian polynomials and k-Stirling permutations, arXiv preprint arXiv:1409.6525, 2014.

Shi-Mei Ma, 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, 2015.

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]], P[2]=2t.

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

EXAMPLE

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 begins:

2;

2,4;

2,12,10;

2,28,58,32;

2,60,236,300,122;

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

CROSSREFS

Diagonals give A001250, A001758, A028399.

Cf. A008970.

Sequence in context: A229756 A227450 A010026 * A137777 A126984 A159749

Adjacent sequences:  A059424 A059425 A059426 * A059428 A059429 A059430

KEYWORD

tabl,nonn,easy,nice

AUTHOR

N. J. A. Sloane, Jan 31 2001

EXTENSIONS

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

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 12 06:05 EST 2017. Contains 295937 sequences.