|
| |
|
|
A008971
|
|
Triangle read by rows: T(n,k) is the number of permutations of [n] with k increasing runs of length at least 2. Triangle starts 1; 1; 1,1; 1,5; 1,18,5; 1,58,61; Row n has 1+floor(n/2) terms.
|
|
3
| |
|
|
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; 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. - T. Kyle Petersen (tkpeters(AT)brandeis.edu), 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.
Shi-Mei Ma, Derivative polynomials and permutations by numbers of interior peaks and left peaks, Arxiv preprint arXiv:1106.5781, 2011
L. W. Shapiro, W.-J. Woan and S. Getu, Runs, slides and moments, SIAM J. Alg. Discrete Methods, 4 (1983), 459-466.
|
|
|
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 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).
|
|
|
EXAMPLE
| Triangle starts
1;
1;
1,1;
1,5;
1,18,5;
1,58,61;
Example: T(3,1)=5 because all permutations of [3] with the exception of 321 have one increasing run of length at least 2.
|
|
|
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);
|
|
|
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]] (* From Jean-François Alcover, May 30 2011, after given formula *)
|
|
|
CROSSREFS
| Contribution from Johannes W. Meijer (meijgia(AT)hotmail.com), May 24 2009: (Start)
A160486 is a sub-triangle.
A000340, A000363, A000507 equal the second, third and fourth left hand columns.
(End)
Sequence in context: A121755 A104174 A050400 * A151335 A055584 A193861
Adjacent sequences: A008968 A008969 A008970 * A008972 A008973 A008974
|
|
|
KEYWORD
| tabf,nonn
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| Edited by Emeric Deutsch (deutsch(AT)duke.poly.edu) and Ira Gessel (gessel(AT)brandeis.edu), Aug 28 2004
Maple program edited by Johannes W. Meijer (meijgia(AT)hotmail.com), May 15 2009
|
| |
|
|
