A008303 -id:A008303 - cp's OEIS frontend

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

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

Offset: 0

N. J. A. Sloane

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
From Petros Hadjicostas, Aug 09 2019: (Start)
In their book, David and Barton (1962) use the notation T_{N,v*}^* for this array, where N is the length of the permutation and v* is the so-called "number of runs up" in the permutation. In modern terminology, a "run up" in a permutation is an increasing run of length >= 2. See their discussion on p. 154 of their book and see p. 163 for the definition of T_{N,v*}^*.
They do not consider as "runs up" single elements b_i in a permutation b = (b_1, b_2, ..., b_n) even if they satisfy b_{i-1} > b_i > b_{i+1} (with b_{n-1} > b_n when i = n and b_1 > b_2 when i = 1). (The command Runs[b] for permutation b in Mathematica, using the package Combinatorica`, will generate not only the "runs up" of b but also the single elements in the permutation b that satisfy one of the above inequalities. For example, Runs[{3,2,1}] gives the set of runs {{3}, {2}, {1}}, none of which is a "run up".)
So, here n = N and k = v*. On p. 163 of their book they give the recurrence shown below in the FORMULA section from Charalambides' (2002) book: T(n+1, k) = (2*k + 1) * T(n,k) + (n - 2*k + 2) * T(n, k-1) for n >= 0 and 1 <= k <= floor(n/2) + 1. The values of T_{N,v*}^* = T(n, k) appear in Table 10.5 (p. 163) of their book.
Since the complement of a permutation (b_1, b_2, ..., b_n) is (n+1-b_1, n+1-b_2, ..., n+1-b_n), it is clear that the current array T(n, k) is also the number of permutations of [n] with k decreasing runs of length >= 2 (i.e., the number of permutations of [n] with k "runs down" according to David and Barton (1962)).
Note that the number of permutations of [n] with k runs of length >= 2 that are either increasing or decreasing (i.e., the number of permutations of [n] that contain k "runs up" and "runs down" in total) is given by array A059427. One half of array A059427 is given in Table 10.4 (p. 159) in David and Barton (1962)--see also array A008970.
A run that is either a "run up" or "run down" (i.e., an ascending or a descending run of length >= 2) is called "séquence" by André (19th century) and Comtet (1974). See the references for sequence A000708 or for array A059427. (Again, recall that David and Barton do not consider single numbers as either a "run up" or a "run down".)
Morley (1897) proved that in a permutation of [n], #("runs up") + #("runs down") + #(monotonic triplets of adjacent numbers in the permutation) = n - 1. (His definition of a run is highly non-standard!) See the example below.
The number Q(n,k) of circular permutations of [n] that contain k runs that are either "runs up" or "runs down" (that is, k ascending or descending runs of length >= 2) is given by array A008303. More precisely, Q(n+1, 2*(k+1)) = A008303(n, k) for n >= 1 and 0 <= k <= ceiling(n/2)-1. In addition, Q(n, s) = 0 when either s is odd, or n <= 1, or s > n. Also, Q_{n,2} = 2^(n-2) for n >= 2.
The numbers in array A008303 appear in Table 10.6 (p. 163) in David and Barton (1962).
(End)

			Triangle T(n,k) (with rows n >= 0 and columns k >= 0) starts as follows:
  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;
  ...
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)
From _Petros Hadjicostas_, Aug 09 2019: (Start)
Consider the permutations of [4]. We list the increasing runs of length at least 2 (= "runs up"), the decreasing runs of length at least 2 (= "runs down"), and the monotonic triplets of adjacent numbers in the permutation (which we abbreviate to MTAN for simplicity). The sum of the numbers of these three should be n-1 (see Morley (1897) but notice that his use of the word "run" is highly non-standard).
1234 -> "runs up" = {1234}, "runs down" = {}, MTAN = {123, 234}.
1243 -> "runs up" = {124}, "runs down" = {43}, MTAN = {124}.
1324 -> "runs up" = {13, 24}, "runs down" = {32}, MTAN = {}.
1342 -> "runs up" = {134}, "runs down" = {42}, MTAN = {134}.
1423 -> "runs up" = {14, 23}, "runs down" = {42}, MTAN = {}.
1432 -> "runs up" = {14}, "runs down" = {432}, MTAN = {432}.
2134 -> "runs up" = {134}, "runs down" = {21}, MTAN = {134}.
2143 -> "runs up" = {14}, "runs down" = {21, 43}, MTAN = {}.
2314 -> "runs up" = {23, 14}, "runs down" = {31}, MTAN = {}.
2341 -> "runs up" = {234}, "runs down" = {41}, MTAN = {234}.
2413 -> "runs up" = {24, 13}, "runs down" = {41}, MTAN = {}.
2431 -> "runs up" = {24}, "runs down" = {431}, MTAN = {431}.
3124 -> "runs up" = {124}, "runs down" = {31}, MTAN = {124}.
3142 -> "runs up" = {14}, "runs down" = {31, 42}, MTAN = {}.
3214 -> "runs up" = {14}, "runs down" = {321}, MTAN = {321}.
3241 -> "runs up" = {24}, "runs down" = {32, 41}, MTAN = {}.
3412 -> "runs up" = {34, 12}, "runs down" = {41}, MTAN = {}.
3421 -> "runs up" = {34}, "runs down" = {421}, MTAN = {421}.
4123 -> "runs up" = {123}, "runs down" = {41}, MTAN = {123}.
4132 -> "runs up" = {13}, "runs down" = {41, 32}, MTAN = {}.
4213 -> "runs up" = {13}, "runs down" = {421}, MTAN = {421}.
4231 -> "runs up" = {23}, "runs down" = {42, 31}, MTAN = {}.
4312 -> "runs up" = {12}, "runs down" = {431}, MTAN = {431}.
4321 -> "runs up" = {}, "runs down" = {4321}, MTAN = {432, 321}.
If we let k = number of increasing runs of length >= 2 (= number of "runs up") in a permutation of [4], then (from above) the possible values of k are 0, 1, 2, and we have T(n=4, k=0) = 1, T(n=4, k=1) = 18, and T(n=4, k=2) = 5.
If we let k = number of decreasing runs of length >= 2 (= number of "runs down") in a permutation of [4], then again the possible values of k are 0, 1, 2, and we have T(n=4, k=0) = 1, T(n=4, k=1) = 18, and T(n=4, k=2) = 5.
Finally, note that if b_i, b_{i+1}, b_{i+2} is an increasing triplet of adjacent numbers in permutation b, then n+1-b_i, n+1-b_{i+1}, n+1-b_{i+2} is a decreasing triplet of adjacent numbers in the complement of b, and vice versa. For example, 4213 is the complement of 1342. Their set of monotonic triplets of adjacent numbers are {421} and {134}, respectively, and we have 4 + 1 = 2 + 3 = 1 + 4 = 5.
(End)

Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002.
F. N. David and D. E. Barton, Combinatorial Chance, Charles Griffin, 1962; see Table 10.5, p. 163.
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 260.

Alois P. Heinz, Rows n = 0..170, flattened
David Callan, Shi-Mei Ma, and Toufik Mansour, Some Combinatorial Arrays Related to the Lotka-Volterra System, Electronic Journal of Combinatorics, Volume 22, Issue 2 (2015), Paper #P2.22.
Shaoshi Chen, Hanqian Fang, Sergey Kitaev, and Candice X.T. Zhang, Patterns in Multi-dimensional Permutations, arXiv:2411.02897 [math.CO], 2024. See p. 7.
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.
Ming-Jian Ding and Bao-Xuan Zhu, Some results related to Hurwitz stability of combinatorial polynomials, Advances in Applied Mathematics, Volume 152, (2024), 102591. See p. 13.
Qi Fang, Ya-Nan Feng, and Shi-Mei Ma, Alternating runs of permutations and the central factorial numbers, arXiv:2202.13978 [math.CO], 2022.
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.
Amy M. Fu and Frank Z. K. Li, Joint Distributions of Permutation Statistics and the Parabolic Cylinder Functions, arXiv:1809.07465 [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
Kathy Q. Ji, The (alpha, beta)-Eulerian Polynomials and Descent-Stirling Statistics on Permutations, arXiv:2310.01053 [math.CO], 2023. See pp. 9, 22.
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, Qi Fang, Toufik Mansour, and Yeong-Nan Yeh, Alternating Eulerian polynomials and left peak polynomials, arXiv:2104.09374 [math.CO], 2021.
Shi-Mei Ma, T. Mansour, and 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, Toufik Mansour, David G.L. Wang, and Yeong-Nan Yeh, Several variants of the Dumont differential system and permutation statistics, Science China Mathematics 60 (2018).
Shi-Mei Ma, Jun Ma, Jean Yeh, and Yeong-Nan Yeh, The 1/k-Eulerian polynomials of type B, arXiv:2001.07833 [math.CO], 2020.
Shi-Mei Ma and Yeong-Nan Yeh, The Peak Statistics on Simsun Permutations, Elect. J. Combin., 23 (2016), P2.14; arXiv preprint, arXiv:1601.06505 [math.CO], 2016.
F. Morley, A generating function for the number of permutations with an assigned number of sequences, Bull. Amer. Math. Soc. 4 (1897), 23-28.
L. W. Shapiro, W.-J. Woan, and S. Getu, Runs, slides and moments, SIAM J. Alg. Discrete Methods, 4 (1983), 459-466.
Wikipedia, Florence Nightingale David.
Bao-Xuan Zhu, Stieltjes moment properties and continued fractions from combinatorial triangles, arXiv:2007.14924 [math.CO], 2020, see p. 27.
Yan Zhuang, Monoid networks and counting permutations by runs, arXiv preprint arXiv:1505.02308 [math.CO], 2015.
Y. Zhuang, Counting permutations by runs, J. Comb. Theory Ser. A 142 (2016), pp. 147-176.

A160486 is a sub-triangle.
A000340, A000363, A000507 equal the second, third and fourth left hand columns.
Cf. A000708, A008303, A008970, A059427.
T(2n,n) gives A000364.

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); # edited by Johannes W. Meijer, May 15 2009
# 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

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

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 or p. 163 in the David and Barton book).
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)

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

Crossrefs added by Johannes W. Meijer, May 24 2009

A094503 Triangle read by rows: coefficients d(n,k) of Andre polynomials D(x,n) = Sum_{k>0} d(n,k)*x^k.

Original entry on oeis.org

1, 1, 1, 1, 1, 4, 1, 11, 4, 1, 26, 34, 1, 57, 180, 34, 1, 120, 768, 496, 1, 247, 2904, 4288, 496, 1, 502, 10194, 28768, 11056, 1, 1013, 34096, 166042, 141584, 11056, 1, 2036, 110392, 868744, 1372088, 349504, 1, 4083, 349500, 4247720, 11204160, 6213288

Offset: 1

Philippe Deléham, Jun 09 2004

a(n,k) is the number of increasing 0-1-2 trees on [n] with k leaves. An increasing 0-1-2 tree on [n] is an unordered tree on [n], rooted at 1, in which each vertex has <= 2 children and the labels increase along each path from the root. Example: a(4,2)=4 counts the trees with edges as follows, {1->2->3,1->4}, {1->2->4,1->3}, {1->2->4,2->3}, {1->3->4,1->2}. - David Callan, Oct 24 2004

			Triangle begins:
  1
  1
  1  1
  1  4
  1 11   4
  1 26  34
  1 57 180 34
  ...
From _Peter Bala_, Jun 26 2012: (Start)
Recurrence equation: T(6,3) = 3*T(5,3) + 2*T(5,2) = 3*4 + 2*11 = 34.
n = 4: the 5 weighted non-plane increasing 0-1-2 trees on 4 vertices are
.........................................................
..4......................................................
..|......................................................
..3............4............4.............3.......3...4..
..|.........../............/............./.........\./...
..2......2...3........3...2.........4...2........(t)2....
..|.......\./..........\./...........\./............|....
..1.....(t)1.........(t)1..........(t)1.............1....
.........................................................
Hence row polynomial R(4,t) = (1 + 4*t)*t.
(End)

Alois P. Heinz, Rows n = 1..200, flattened
Paul Barry, Three Études on a sequence transformation pipeline, arXiv:1803.06408 [math.CO], 2018.
F. Bergeron, Ph. Flajolet, and B. Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
David Callan, A note on downup permutations and increasing 0-1-2 trees
Chak-On Chow and Wai Chee Shiu, Counting Simsun Permutations by Descents, Ann. Comb. 15, 625-635 (2011). See p. 627 and comments section in A113897.
Ming-Jian Ding and Bao-Xuan Zhu, Some results related to Hurwitz stability of combinatorial polynomials, Advances in Applied Mathematics, Volume 152, (2024), 102591. See p. 35.
Filippo Disanto and Thomas Wiehe, Exact enumeration of cherries and pitchforks in ranked trees under the coalescent model, arXiv preprint arXiv:1112.1295 [math.CO], 2011-2012, see Y(x,z).
Filippo Disanto and Thomas Wiehe, Exact enumeration of cherries and pitchforks in ranked trees under the coalescent model, Math. Biosci. 242 (2013), no. 2, 195-200.
D. Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions. arXiv:math/0501052v2 [math.CA], 2005.
Dominique Foata and Guoniu Han, Arbres minimax et polynomes d'André .
D. Foata and Guo-Niu Han, Arbres minimax et polynomes d'André, Adv. in Appl. Math., 27 (2001), no.2-3, 367-389.
Guo-Niu Han and Shi-Mei Ma, Derivatives, Eulerian polynomials and the g-indexes of Young tableaux, arXiv:2006.14064 [math.CO], 2020.
Shi-Mei Ma, Enumeration of permutations by number of alternating runs, Discrete Math., 313 (2013), 1816-1822.
Shi-Mei Ma, Qi Fang, Toufik Mansour, and Yeong-Nan Yeh, Alternating Eulerian polynomials and left peak polynomials, arXiv:2104.09374, 2021
Shi-Mei Ma and Yeong-Nan Yeh, The Peak Statistics on Simsun Permutations, Elect. J. Combin., 23 (2016), P2.14; arXiv preprint, arXiv:1601.06505 [math.CO], 2016.
E. Norton, Symplectic Reflection Algebras in Positive Characteristic as Ore Extensions, arXiv preprint arXiv:1302.5411 [math.RA], 2013.

Cf. A000012, A000295, A008292, A101280, A113897.

A094503:=proc(n,k) options remember: if(n=1 and k=1) then RETURN(1) elif(1<=k and k<=floor((n+1)/2) and n>=1) then RETURN(k*A094503(n-1,k)+(n+2-2*k)*A094503(n-1,k-1)) else RETURN(0) fi: end; seq(seq(A094503(n,k),k=1..floor((n+1)/2)),n=1..14);

t[1, 1] = 1; t[n_, k_] /; Not[1 <= k <= (n+1)/2] = 0; t[n_, k_] := t[n, k] = k*t[n-1, k] + (n+2-2*k)*t[n-1, k-1]; Table[t[n, k], {n, 0, 13}, {k, 1, (n + 1)/2}] // Flatten (* Jean-François Alcover, Nov 22 2012, after Maple *)

def p(n) :
    s = var('s'); u = sqrt(s^2-2)
    egf = u*x-2*ln((exp(u*x)*(1-s/u)+s/u+1)/2)
    return factorial(n+2)*egf.series(x,n+4).coefficient(x,n+2)
def A094503_row(n) : return [p(n).coefficient(s,n-2*i) for i in (0..n//2)]
for n in (0..6): print(A094503_row(n)) # Peter Luschny, Jul 01 2012

D(1, n) = A000111(n), Euler or up/down numbers. D(1/2, n) = A000142(n)*(1/2)^n. D(1/4, n) = A080795(n)*(1/4)^n.
From Peter Bala, Jun 26 2012: (Start):
Recurrence equation: T(n,k) = k*T(n-1,k) + (n+2-2*k)*T(n-1,k-1) for n >= 1 and 1 <= k <= floor((n+1)/2).
Let r(t) = sqrt(1-2*t) and w(t) = (1-r(t))/(1+r(t)). The e.g.f. is F(t,z) = r(t)*(1 + w(t)*exp(r(t)*z))/(1 - w(t)*exp(r(t)*z)) = 1 + t*z + t*z^2/2! + (t+t^2)*z^3/3! + (t+4*t^2)*z^4/4! + ... (Foata and Han, 2001, section 7).
Note that (F(2*t,z) - 1)/(2*t) is the e.g.f. for A101280.
The modified e.g.f. A(t,z) := (F(t,z) - 1)/t = z + z^2/2! + (1+t)*z^3/3! + (1+4*t)*z^4/4! + ... satisfies the autonomous partial differential equation dA/dz = 1 + A + 1/2*t*A^2 with A(t,0) = 1. It follows that the inverse function A(t,z)^(-1) may be expressed as an integral: A(t,z)^(-1) = Integral_{x = 0..z} 1/(1+x+1/2*t*x^2) dx.
Applying [Dominici, Theorem 4.1] to invert the integral gives the following method for calculating the row polynomials R(n,t) of the table: let f(t,x) = 1+x+1/2*t*x^2 and let D be the operator f(t,x)*d/dx. Then R(n+1,t) = t*D^n(f(t,x)) evaluated at x = 0.
By Bergeron et al., Theorem 1, the shifted row polynomial 1/t*R(n,t) is the generating function for rooted non-plane increasing 0-1-2 trees on n vertices, where the vertices of outdegree 2 have weight t and all other vertices have weight 1. An example is given below.
1/(2*t)*(1+t)^(n+1)*R(n,2*t/(1+t)^2) = the n-th Eulerian polynomial of A008292. For example, n = 5 gives 1/(2*t)*(1+t)^6*R(5,2*t/(1+t)^2) = 1 + 26*t + 66*t^2 + 26*t^3 + t^4.
A000142(n) = 2^n*R(n,1/2); A080795(n) = 4^n*R(n,1/4);
A000670(n) = 3/4*3^n*R(n,4/9); A004123(n+1) = 5/6*5^n*R(n,12/25).
(End)
There is a second family of polynomials which also matches the data and is different from the André polynomials as defined by Foata and Han (2001), formula 3.5. Let u = sqrt(s^2-2) and F(s,x) = u*x-2*log((exp(u*x)*(1-s/u)+s/u+1)/2), then for n>=0 the sequence of polynomials p_{n}(s) = (n+2)!*[x^(n+2)]F(s,x) starts 1, s, s^2+1, s^3+4*s, s^4+11*s^2+4, s^5+26*s^3+34*s, s^6+57*s^4+180*s^2+34, ... and the nonzero coefficients of these polynomials in descending order coincide with the sequence a(n). p_{n}(0) is an aerated version of the reduced tangent numbers, p_{2*n}(0) = A002105(n+1) for n>=0. In contrast, the André polynomials vanish at t=0 except for n=0. - Peter Luschny, Jul 01 2012
T(n,k) = A008303(n,k)/2^(n-k). - Ammar Khatab, Aug 17 2024

A101280 Triangle T(n,k) (n >= 1, 0 <= k <= floor((n-1)/2)) read by rows, where T(n,k) = (k+1)T(n-1,k) + (2n-4k)T(n-1,k-1).

Original entry on oeis.org

1, 1, 1, 2, 1, 8, 1, 22, 16, 1, 52, 136, 1, 114, 720, 272, 1, 240, 3072, 3968, 1, 494, 11616, 34304, 7936, 1, 1004, 40776, 230144, 176896, 1, 2026, 136384, 1328336, 2265344, 353792, 1, 4072, 441568, 6949952, 21953408, 11184128, 1, 8166, 1398000, 33981760

Offset: 1

Don Knuth, Jan 28 2005

Row n has ceiling(n/2) terms.
The paper by Shapiro et al. explains why T(n,k) is the number of permutations of n elements having k peaks and with the further property that every rise (ascent) is immediately followed by a peak. [That is, the permutation p_1 ... p_n has the further property that (j > 1 and p_{j-1} < p_j) implies (j < n and p_j > p_{j+1}).] For example, the T(4,1)=8 permutations in the case n=4, k=1 are 1423, 2143, 2431, 3142, 3241, 3421, 4231, 4132.
A more elegant way to state this property: T(n,k) is the number of permutations of n objects with k descents such that every descent is a peak. The eight examples for n=4 and k=1 are now 1243, 1324, 1342, 1423, 2314, 2341, 2413, 3412.
The rows of this triangle are the gamma vectors of the n-dimensional (type A) permutohedra (Postnikov et al., p. 31). Cf. A055151 and A089627. - Peter Bala, Oct 28 2008

			Triangle begins:
  1;
  1,
  1,   2;
  1,   8,
  1,  22,  16;
  1,  52, 136,
  1, 114, 720, 272;
  ...
From _Peter Bala_, Jun 26 2012: (Start)
n = 4: the 9 weighted plane increasing 0-1-2 trees on 4 vertices are
..................................................................
..4...............................................................
..|...............................................................
..3..........4...4...............4...4...............3...3........
..|........./.....\............./.....\............./.....\.......
..2....2...3.......3...2...3...2.......2...3...4...2.......2...4..
..|.....\./.........\./.....\./.........\./.....\./.........\./...
..1...(t)1........(t)1....(t)1........(t)1....(t)1........(t)1....
..................................................................
..3...4...4...3...................................................
...\./.....\./....................................................
.(t)2....(t)2.....................................................
....|.......|.....................................................
....1.......1.....................................................
Hence R(4,t) = 1 + 8*t.
(End)

D. Foata and V. Strehl, "Euler numbers and variations of permutations", in Colloquio Internazionale sulle Teorie Combinatorie, Rome, September 1973, (Atti dei Convegni Lincei 17, Rome, 1976), 129.
Guoniu Han, Frédéric Jouhet, Jiang Zeng, Two new triangles of q-integers via q-Eulerian polynomials of type A and B, Ramanujan J (2013) 31:115-127, DOI 10.1007/s11139-012-9389-3
T. K. Petersen, Eulerian Numbers, Birkhauser, 2015, Chapter 4.

Paul Barry, On the f-Matrices of Pascal-like Triangles Defined by Riordan Arrays, arXiv:1805.02274 [math.CO], 2018.
François Bergeron, Philippe Flajolet and Bruno Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
Leonard Carlitz and Richard Scoville, Generalized Eulerian numbers: combinatorial applications, Journal für die reine und angewandte Mathematik 265 (1974), 111.
Colin Defant, Troupes, Cumulants, and Stack-Sorting, arXiv:2004.11367 [math.CO], 2020.
Diego Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions, arXiv:math/0501052 [math.CA], 2005.
Dominique Foata and Marcel-Paul Schützenberger, Théorie géometrique des polynômes eulériens, arXiv:math/0508232 [math.CO], 2005; Lecture Notes in Math. 138 (1970), 81-83.
Shi-Mei Ma, On gamma-vectors and the derivatives of the tangent and secant functions, arXiv:1304.6654 [math.CO], 2013.
Shi-Mei Ma, Jun Ma, and Yeong-Nan Yeh, On certain combinatorial expansions of descent polynomials and the change of grammars, arXiv:1802.02861 [math.CO], 2018.
Shi-Mei Ma, Jianfeng Wang, Guiying Yan, Jean Yeh, and Yeong-Nan Yeh, Symmetric decompositions and Euler-Stirling statistics on Stirling permutations, arXiv:2507.17667 [math.CO], 2025. See p. 5.
Shi-Mei Ma and Yeong-Nan Yeh, The alternating run polynomials of permutations, arXiv:1904.11437 [math.CO], 2019. See p. 4.
Alexander Postnikov, Victor Reiner, and Lauren Williams, Faces of generalized permutohedra, arXiv:math/0609184 [math.CO], 2006-2007. [_Peter Bala_, Oct 28 2008]
Louis W. Shapiro, Wen-Jin Woan, and Seyoum Getu, Runs, slides and moments, SIAM J. Alg. Discrete Methods, 4 (1983), 459-466.
Andrei K. Svinin, Somos-4 equation and related equations, arXiv:2307.05866 [math.CA], 2023. See p. 16.

The numbers 2^{n-1-k} T(n, k) form the array shown in A008303.
Cf. A055151, A089627. - Peter Bala, Oct 28 2008
Cf. A008292, A094503, A080635 (row sums).

T:=proc(n,k) if k<0 then 0 elif n=1 and k=0 then 1 elif k>floor((n-1)/2) then 0 else (k+1)*T(n-1,k)+(2*n-4*k)*T(n-1,k-1) fi end: for n from 1 to 13 do seq(T(n,k),k=0..floor((n-1)/2)) od; # yields sequence in triangular form # Emeric Deutsch, Aug 06 2005

t[, k?Negative] = 0; t[1, 0] = 1; t[n_, k_] /; k > (n-1)/2 = 0; t[n_, k_] := t[n, k] = (k+1)*t[n-1, k] + (2*n-4*k)*t[n-1, k-1]; Table[t[n, k], {n, 1, 13}, {k, 0, (n-1)/2}] // Flatten (* Jean-François Alcover, Nov 22 2012 *)

G.f.: Sum_{n>=1, k>=0} T(n, k) t^k z^n/n! = C(t)(2-C(t))/(exp^(-z sqrt(1-4t)) + 1 - C(t)) - C(t), where the sum on k is actually finite, running up to ceiling(n/2) - 1; here C(t) = (1 - sqrt(1-4t))/2t is the generating function for the Catalan numbers (A000108).
Sum_{k} Eulerian(n, k) x^k = Sum_{k} T(n, k) x^k (1+x)^(n-1-2k). E.g., 1 + 11x + 11x^2 + x^3 = (1+x)^3 + 8x(1+x).
From Peter Bala, Jun 26 2012: (Start)
T(n,k) = 2^k*A094503(n,k+1).
Let r(t) = sqrt(1 - 2*t) and w(t) = (1 - r(t))/(1 + r(t)). Define F(t,z) = r(t)*(1 + w(t)*exp(r(t)*z))/(1 - w(t)*exp(r(t)*z)) = 1 + t*z + t*z^2/2! + (t+t^2)*z^3/3! + (t+4*t^2)*z^4/4! + ...; F(t,z) is the e.g.f. for A094503. The e.g.f. for the present table is A(t,z) := (F(2*t,z) - 1)/(2*t) = z + z^2/2! + (1+2*t)*z^3/3! + (1+8*t)*z^4/4! + ....
The e.g.f. A(t,z) satisfies the autonomous partial differential equation dA/dz = 1 + A + t*A^2 with A(t,0) = 0. It follows that the inverse function A(t,z)^(-1) may be expressed as an integral: A(t,z)^(-1) = int {x = 0..z} 1/(1+x+t*x^2) dx.
Applying [Dominici, Theorem 4.1] to invert the integral gives the following method for calculating the row polynomials R(n,t) of the table: let f(t,x) = 1+x+t*x^2 and let D be the operator f(t,x)*d/dx. Then R(n+1,t) = D^n(f(t,x)) evaluated at x = 0.
By Bergeron et al., Theorem 1, the row polynomial R(n,t) is the generating function for rooted plane increasing 0-1-2 trees on n vertices, where the vertices of outdegree 2 have weight t and all other vertices have weight 1. An example is given below.
Row sums A080635.
(End)

More terms from Emeric Deutsch, Aug 06 2005

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A094503 Triangle read by rows: coefficients d(n,k) of Andre polynomials D(x,n) = Sum_{k>0} d(n,k)*x^k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

A101280 Triangle T(n,k) (n >= 1, 0 <= k <= floor((n-1)/2)) read by rows, where T(n,k) = (k+1)T(n-1,k) + (2n-4k)T(n-1,k-1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A179709 Number of permutations of 1..n having exactly 6 maxima.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A179710 Number of permutations of 1..n having exactly 7 maxima.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A303564 Number T(n,k) of derangements of [n] having exactly k peaks; triangle T(n,k), n>=0, 0<=k<=max(0,floor((n-1)/2)), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A179708 Number of permutations of 1..n having exactly 5 maxima.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions