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!)
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
1, 1, 1, 1, 1, 5, 1, 18, 5, 1, 58, 61, 1, 179, 479, 61, 1, 543, 3111, 1385, 1, 1636, 18270, 19028, 1385, 1, 4916, 101166, 206276, 50521, 1, 14757, 540242, 1949762, 1073517, 50521, 1, 44281, 2819266, 16889786, 17460701, 2702765, 1, 132854, 14494859 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,6

COMMENTS

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

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

REFERENCES

D. Callan, S.-M. Ma and T. Mansour, Some combinatorial arrays related to the Lotka-Volterra system, Elec. J. Combin, 22, 2015, #P2.22.

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

C.-O. Chow and S.-M. Ma, Counting signed permutations by their alternating runs, Discrete Mathematics, Volume 323, 28 May 2014, Pages 49-57.

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

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

Shi-Mei Ma, Enumeration of permutations by number of alternating runs, Discrete Math., 313 (2013), 1816-1822.

Shi-Mei Ma, Yeong-Nan Yeh, The Peak Statistics on Simsun Permutations, Elect. J. Combin., 23 (2016), P2.14

L. W. Shapiro, W.-J. Woan and S. Getu, Runs, slides and moments, SIAM J. Alg. Discrete Methods, 4 (1983), 459-466.

LINKS

Alois P. Heinz, Rows n = 0..170, flattened

David Callan, Shi-Mei Ma, Toufik Mansour, Some Combinatorial Arrays Related to the Lotka-Volterra System, Electronic Journal of Combinatorics, Volume 22, Issue 2 (2015), Paper #P2.22.

FindStat - Combinatorial Statistic Finder, The number of outer peaks of a permutation

D. S. Hollman and H. F. Schaefer III, Arbitrary order El'yashevich-Wilson B tensor formulas for the most frequently used internal coordinates in molecular vibrational analyses, The Journal of Chemical Physics, Vol. 137, 164103 (2012). - From N. J. A. Sloane, Jan 01 2013

Shi-Mei Ma, Derivative polynomials and permutations by numbers of interior peaks and left peaks, arXiv preprint arXiv:1106.5781 [math.CO], 2011.

Shi-Mei Ma, T. Mansour, D. Callan, Some combinatorial arrays related to the Lotka-Volterra system, arXiv preprint arXiv:1404.0731 [math.CO], 2014.

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 [math.CO], 2014.

Yan Zhuang, Monoid networks and counting permutations by runs, arXiv preprint arXiv:1505.02308 [math.CO], 2015.

FORMULA

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

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

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

From Peter Bala, Jan 23 2016: (Start)

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

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)

EXAMPLE

Triangle starts

1;

1;

1,   1;

1,   5;

1,  18,    5;

1,  58,   61;

1, 179,  479,   61;

1, 543, 3111, 1385,

...

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

From Peter Bala, Jan 23 2016: (Start)

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

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)

MAPLE

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

# second Maple program:

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

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

    end:

seq(seq(T(n, k), k=0..n/2), n=0..14); # Alois P. Heinz, Oct 16 2013

MATHEMATICA

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

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

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

CROSSREFS

A160486 is a sub-triangle.

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

Sequence in context: A121755 A104174 A050400 * A151335 A226605 A055584

Adjacent sequences:  A008968 A008969 A008970 * A008972 A008973 A008974

KEYWORD

tabf,nonn,easy

AUTHOR

N. J. A. Sloane.

EXTENSIONS

Edited by Emeric Deutsch and Ira M. Gessel, Aug 28 2004

Maple program edited by Johannes W. Meijer, May 15 2009

Crossrefs added by Johannes W. Meijer, May 24 2009

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.