|
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 2,1
|
|
|
REFERENCES
| D. Andre, Etude sur les maxima, minima et sequences des permutations, Ann. Sci. Ecole Norm. Sup., 3, no. 1 (1884), 121-135.
M. Bona, Combinatorics of Permutations, Chapman & Hall/CRC, Boca Raton, FL, 2004, pp. 24-30.
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.
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.
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.
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]
|
|
|
LINKS
| T. D. Noe, Rows n=2..50 of triangle, flattened
E. Rodney Canfield and Herbert S. Wilf, Counting permutations by their runs up and down
R. P. Stanley, Longest alternating subsequences of permutations
|
|
|
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) [Andre]. - Emeric Deutsch (deutsch(AT)duke.poly.edu), 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]]
(* From Jean-François Alcover, Jun 16 2011, after recurrence *)
|
|
|
CROSSREFS
| Diagonals give A001250, A001758, A028399.
Cf. A008970.
Sequence in context: A064482 A067228 A010026 * A137777 A126984 A159749
Adjacent sequences: A059424 A059425 A059426 * A059428 A059429 A059430
|
|
|
KEYWORD
| tabl,nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com), Jan 31 2001
|
|
|
EXTENSIONS
| More terms from Larry Reeves (larryr(AT)acm.org), Feb 01 2001
Edited by Emeric Deutsch (deutsch(AT)duke.poly.edu) and Ira Gessel (gessel(AT)brandeis.edu), Dec 06 2004
Andre reference from Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Jul 26 2006
|
| |
|
|
