

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 LotkaVolterra 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 4957.
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. 4354).
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 260.
ShiMei Ma, Enumeration of permutations by number of alternating runs, Discrete Math., 313 (2013), 18161822.
ShiMei Ma, YeongNan 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), 459466.


LINKS

Alois P. Heinz, Rows n = 0..170, flattened
David Callan, ShiMei Ma, Toufik Mansour, Some Combinatorial Arrays Related to the LotkaVolterra 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'yashevichWilson 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
ShiMei Ma, Derivative polynomials and permutations by numbers of interior peaks and left peaks, arXiv preprint arXiv:1106.5781 [math.CO], 2011.
ShiMei Ma, T. Mansour, D. Callan, Some combinatorial arrays related to the LotkaVolterra 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(1t)/(sqrt(1t)*cosh(x*sqrt(1t))sinh(x*sqrt(1t))) (Ira M. Gessel).
T(n+1,k) = (2*k+1)*T(n,k) + (n2*k+2)*T(n,k1) (see p. 542 of the Charalambides reference).
G.f.: T(0)/(1x), 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)^(n2*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^(n2*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(1t)/(sqrt(1t)*cosh(x*sqrt(1t))sinh(x*sqrt(1t))): 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(n1, k) +(n+12*k)*T(n1, k1)))
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]] (* JeanFrançois Alcover, May 30 2011, after given formula *)


CROSSREFS

A160486 is a subtriangle.
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



