%I A059427
%S A059427 2,2,4,2,12,10,2,28,58,32,2,60,236,300,122,2,124,836,1852,1682,544,2,
%T A059427 252,2766,9576,14622,10332,2770,2,508,8814,45096,103326,119964,69298,
%U A059427 15872,2,1020,27472,201060,650892,1106820,1034992,505500,101042,2,2044
%N 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.
%D A059427 D. Andre, Etude sur les maxima, minima et sequences des permutations, 
               Ann. Sci. Ecole Norm. Sup., 3, no. 1 (1884), 121-135.
%D A059427 M. Bona, Combinatorics of Permutations, Chapman & Hall/CRC, Boca Raton, 
               FL, 2004, pp. 24-30.
%D A059427 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.
%D A059427 L. Carlitz, Enumeration of permutations by sequences, Fib. Quart., 16 
               (1978), 259-268.
%D A059427 L. Carlitz, The number of permutations with a given number of sequences, 
               Fib. Quart., 18 (1980), 347-352.
%D A059427 L. Comtet, Advanced Combinatorics, Reidel, Dordrecht, Holland, 1974, 
               p. 261, #13.
%D A059427 F. N. David and D. E. Barton, Combinatorial Chance, Hafner, NY, 1962, 
               pp. 157-162.
%D A059427 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 A059427 D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, 
               MA, 1973, Vol. 3, pp. 46 and 587-8.
%H A059427 T. D. Noe, <a href="b059427.txt">Rows n=2..50 of triangle, flattened</
               a>
%H A059427 E. Rodney Canfield and Herbert S. Wilf, <a href="http://arXiv.org/abs/
               math.CO/0609704">Counting permutations by their runs up and down</
               a>
%H A059427 R. P. Stanley, <a href="http://arXiv.org/abs/math.CO/0511419">Longest 
               alternating subsequences of permutations</a>
%F A059427 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
%F A059427 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.
%F A059427 T(n, n-1) = 2*A000111(n) = A001250(n-1).
%F A059427 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.
%F A059427 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).
%F A059427 T(n, k)=2 A008970(n, k).
%e A059427 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 A059427 Triangle begins:
%e A059427 2;
%e A059427 2,4;
%e A059427 2,12,10;
%e A059427 2,28,58,32;
%e A059427 2,60,236,300,122;
%p A059427 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);
%Y A059427 Diagonals give A001250, A001758, A028399.
%Y A059427 Cf. A008970.
%Y A059427 Sequence in context: A064482 A067228 A010026 this_sequence A126984 A159749 
               A102416
%Y A059427 Adjacent sequences: A059424 A059425 A059426 this_sequence A059428 A059429 
               A059430
%K A059427 tabl,nonn,easy,nice
%O A059427 2,1
%A A059427 N. J. A. Sloane (njas(AT)research.att.com), Jan 31 2001
%E A059427 More terms from Larry Reeves (larryr(AT)acm.org), Feb 01 2001
%E A059427 Edited by Emeric Deutsch (deutsch(AT)duke.poly.edu) and Ira Gessel (gessel(AT)brandeis.edu), 
               Dec 06 2004
%E A059427 Andre reference from Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Jul 26 
               2006