2,1

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.

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

P(n, k)=0 if n<2 or k<1 or k>=n; P(2, 1)=2; P(n, k)=kP(n-1, k)+2P(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)=kT(n-1, k)+2T(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+tx)/(1+t).

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

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;

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

Diagonals give A001250, A001758, A028399.

Cf. A008970.

Sequence in context: A064482 A067228 A010026 this_sequence A126984 A102416 A129243

Adjacent sequences: A059424 A059425 A059426 this_sequence A059428 A059429 A059430

tabl,nonn,easy,nice

njas, Jan 31 2001

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