login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

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

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

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.

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

C.-O. Chow, S.-M. Ma, T. Mansour, and M. Shattuck, Counting permutations by cyclic peaks and valleys, Annales Mathematicae et Informaticae, (2014), Vol. 43, pp. 43-54.

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

Amy M. Fu, A Context-free Grammar for Peaks and Double Descents of Permutations, arXiv:1801.04397 [math.CO], 2018.

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, Enumeration of permutations by number of alternating runs, Discrete Math., 313 (2013), 1816-1822.

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.

Shi-Mei Ma, Yeong-Nan Yeh, The Peak Statistics on Simsun Permutations, Elect. J. Combin., 23 (2016), P2.14; arXiv preprint, arXiv:1601.06505 [math.CO], 2016.

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

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 A297174 A226605

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 August 17 06:56 EDT 2018. Contains 313810 sequences. (Running on oeis4.)