This site is supported by donations to The OEIS Foundation.



Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A008971 Triangle read by rows: T(n,k) is the number of permutations of [n] with k increasing runs of length at least 2. 4


%S 1,1,1,1,1,5,1,18,5,1,58,61,1,179,479,61,1,543,3111,1385,1,1636,18270,

%T 19028,1385,1,4916,101166,206276,50521,1,14757,540242,1949762,1073517,

%U 50521,1,44281,2819266,16889786,17460701,2702765,1,132854,14494859

%N Triangle read by rows: T(n,k) is the number of permutations of [n] with k increasing runs of length at least 2.

%C Row n has 1+floor(n/2) terms.

%C T(n,k) is also the number of permutations of [n] with k "exterior peaks" where we count peaks in the usual way, but add a peak at the beginning if the permutation begins with a descent, e.g. 213 has one exterior peak. T(3,1) = 5 since all permutations of [3] have an exterior peak except 123. This is also the definition for peaks of signed permutations, where we assume that a signed permutation always begins with a zero. - _Kyle Petersen_, Jan 14 2005

%D Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002.

%D F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 260.

%H Alois P. Heinz, <a href="/A008971/b008971.txt">Rows n = 0..170, flattened</a>

%H David Callan, Shi-Mei Ma, Toufik Mansour, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p22/">Some Combinatorial Arrays Related to the Lotka-Volterra System</a>, Electronic Journal of Combinatorics, Volume 22, Issue 2 (2015), Paper #P2.22.

%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 FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000035/">The number of outer peaks of a permutation</a>

%H Amy M. Fu, <a href="https://arxiv.org/abs/1801.04397">A Context-free Grammar for Peaks and Double Descents of Permutations</a>, arXiv:1801.04397 [math.CO], 2018.

%H D. S. Hollman and H. F. Schaefer III, <a href="http://dx.doi.org/10.1063/1.4759170">Arbitrary order El'yashevich-Wilson B tensor formulas for the most frequently used internal coordinates in molecular vibrational analyses</a>, The Journal of Chemical Physics, Vol. 137, 164103 (2012). - From _N. J. A. Sloane_, Jan 01 2013

%H Shi-Mei Ma, <a href="http://arxiv.org/abs/1106.5781">Derivative polynomials and permutations by numbers of interior peaks and left peaks</a>, arXiv preprint arXiv:1106.5781 [math.CO], 2011.

%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 Shi-Mei Ma, T. Mansour, D. Callan, <a href="http://arxiv.org/abs/1404.0731">Some combinatorial arrays related to the Lotka-Volterra system</a>, arXiv preprint arXiv:1404.0731 [math.CO], 2014.

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

%H Shi-Mei Ma, Toufik Mansour, David G.L. Wang, Yeong-Nan Yeh, <a href="https://www.math.sinica.edu.tw/www/file_upload/mayeh/2018SCM-2016-0688.pdf">Several variants of the Dumont differential system and permutation statistics</a>, Science China Mathematics 60 (2018).

%H Shi-Mei Ma, Yeong-Nan Yeh, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p14">The Peak Statistics on Simsun Permutations</a>, Elect. J. Combin., 23 (2016), P2.14; <a href="https://arxiv.org/abs/1601.06505">arXiv preprint</a>, arXiv:1601.06505 [math.CO], 2016.

%H L. W. Shapiro, W.-J. Woan and S. Getu, <a href="http://dx.doi.org/10.1137/0604046">Runs, slides and moments</a>, SIAM J. Alg. Discrete Methods, 4 (1983), 459-466.

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

%F E.g.f.: G(t,x) = sum(T(n,k) t^k x^n/n!, 0<=k<=floor(n/2), n>=0) = sqrt(1-t)/(sqrt(1-t)*cosh(x*sqrt(1-t))-sinh(x*sqrt(1-t))) (_Ira M. Gessel_).

%F T(n+1,k) = (2*k+1)*T(n,k) + (n-2*k+2)*T(n,k-1) (see p. 542 of the Charalambides reference).

%F G.f.: T(0)/(1-x), where T(k) = 1 - y*x^2*(k+1)^2/(y*x^2*(k+1)^2 - (1 -x -2*x*k)*(1 -3*x -2*x*k)/T(k+1) ); (continued fraction). - _Sergei N. Gladkovskii_, Nov 08 2013

%F From _Peter Bala_, Jan 23 2016: (Start)

%F cos(x)^(n+1)*(d/dx)^n(1/cos(x)) = Sum_{k = 0..floor(n/2)} T(n,k)*sin(x)^(n-2*k).

%F Equivalently, let D be the differential operator sqrt(1 - x^2)*d/dx. Then sqrt(1 - x^2)^(n+1)*D^n(1/sqrt(1 - x^2)) = Sum_{k = 0..floor(n/2)} T(n,k)*x^(n-2*k). (End)

%e Triangle starts

%e 1;

%e 1;

%e 1, 1;

%e 1, 5;

%e 1, 18, 5;

%e 1, 58, 61;

%e 1, 179, 479, 61;

%e 1, 543, 3111, 1385,

%e ...

%e Example: T(3,1) = 5 because all permutations of [3] with the exception of 321 have one increasing run of length at least 2.

%e From _Peter Bala_, Jan 23 2016: (Start)

%e Row 6: cos(x)^7*(d/dx)^6(1/cos(x)) = sin(x)^6 + 179*sin(x)^4 + 479*sin(x)^2 + 61.

%e Equivalently, (sqrt(1 - x^2))^7*D^6(1/sqrt(1 - x^2)) = x^6 + 179*x^4 + 479*x^2 + 61, where D = sqrt(1 - x^2)*d/dx. (End)

%p G:=sqrt(1-t)/(sqrt(1-t)*cosh(x*sqrt(1-t))-sinh(x*sqrt(1-t))): Gser:=simplify(series(G,x=0,15)): for n from 0 to 14 do P[n]:=sort(expand(n!*coeff(Gser,x,n))) od: seq(seq(coeff(t*P[n],t^k),k=1..1+floor(n/2)),n=0..14);

%p # second Maple program:

%p T:= proc(n, k) option remember; `if`(k=0, 1, `if`(k>iquo(n, 2), 0,

%p (2*k+1)*T(n-1, k) +(n+1-2*k)*T(n-1, k-1)))

%p end:

%p seq(seq(T(n, k), k=0..n/2), n=0..14); # _Alois P. Heinz_, Oct 16 2013

%t t[n_, 0] = 1; t[n_, k_] /; k > Floor[n/2] = 0;

%t t[n_ , k_ ] /; k <= Floor[n/2] := t[n, k] = (2 k + 1) t[n - 1, k] + (n - 2 k + 1) t[n - 1, k - 1];

%t Flatten[Table[t[n, k], {n, 0, 12}, {k, 0, Floor[n/2]}]][[1 ;; 45]] (* _Jean-Fran├žois Alcover_, May 30 2011, after given formula *)

%Y A160486 is a sub-triangle.

%Y A000340, A000363, A000507 equal the second, third and fourth left hand columns.

%K tabf,nonn,easy

%O 0,6

%A _N. J. A. Sloane_.

%E Edited by _Emeric Deutsch_ and _Ira M. Gessel_, Aug 28 2004

%E Maple program edited by _Johannes W. Meijer_, May 15 2009

%E Crossrefs added by _Johannes W. Meijer_, May 24 2009

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 10 23:33 EST 2018. Contains 318049 sequences. (Running on oeis4.)