A002538 -id:A002538 - cp's OEIS frontend

A001286 Lah numbers: a(n) = (n-1)*n!/2.

1, 6, 36, 240, 1800, 15120, 141120, 1451520, 16329600, 199584000, 2634508800, 37362124800, 566658892800, 9153720576000, 156920924160000, 2845499424768000, 54420176498688000, 1094805903679488000, 23112569077678080000, 510909421717094400000

Offset: 2

N. J. A. Sloane

Number of surjections from {1,...,n} to {1,...,n-1}. - Benoit Cloitre, Dec 05 2003
First Eulerian transform of 0,1,2,3,4,... . - Ross La Haye, Mar 05 2005
With offset 0 : determinant of the n X n matrix m(i,j)=(i+j+1)!/i!/j!. - Benoit Cloitre, Apr 11 2005
These numbers arise when expressing n(n+1)(n+2)...(n+k)[n+(n+1)+(n+2)+...+(n+k)] as sums of squares: n(n+1)[n+(n+1)] = 6(1+4+9+16+ ... + n^2), n(n+1)(n+2)(n+(n+1)+(n+2)) = 36(1+(1+4)+(1+4+9)+...+(1+4+9+16+ ... + n^2)), n(n+1)(n+2)(n+3)(n+(n+1)+(n+2)+(n+3)) = 240(...), ... . - Alexander R. Povolotsky, Oct 16 2006
a(n) is the number of edges in the Hasse diagram for the weak Bruhat order on the symmetric group S_n. For permutations p,q in S_n, q covers p in the weak Bruhat order if p,q differ by an adjacent transposition and q has one more inversion than p. Thus 23514 covers 23154 due to the transposition that interchanges the third and fourth entries. Cf. A002538 for the strong Bruhat order. - David Callan, Nov 29 2007
a(n) is also the number of excedances in all permutations of {1,2,...,n} (an excedance of a permutation p is a value j such p(j)>j). Proof: j is exceeded (n-1)! times by each of the numbers j+1, j+2, ..., n; now, Sum_{j=1..n} (n-j)(n-1)! = n!(n-1)/2. Example: a(3)=6 because the number of excedances of the permutations 123, 132, 312, 213, 231, 321 are 0, 1, 1, 1, 2, 1, respectively. - Emeric Deutsch, Dec 15 2008
(-1)^(n+1)*a(n) is the determinant of the n X n matrix whose (i,j)-th element is 0 for i = j, is j-1 for j>i, and j for j < i. - Michel Lagneau, May 04 2010
Row sums of the triangle in A030298. - Reinhard Zumkeller, Mar 29 2012
a(n) is the total number of ascents (descents) over all n-permutations. a(n) = Sum_{k=1..n} A008292(n,k)*k. - Geoffrey Critzer, Jan 06 2013
For m>=4, a(m-2) is the number of Hamiltonian cycles in a simple graph with m vertices which is complete, except for one edge. Proof: think of distinct round-table seatings of m persons such that persons "1" and "2" may not be neighbors; the count is (m-3)(m-2)!/2. See also A001710. - Stanislav Sykora, Jun 17 2014
Popularity of left (right) children in treeshelves. Treeshelves are ordered binary (0-1-2) increasing trees where every child is connected to its parent by a left or a right link. Popularity is the sum of a certain statistic (number of left children, in this case) over all objects of size n. See A278677, A278678 or A278679 for more definitions and examples. See A008292 for the distribution of the left (right) children in treeshelves. - Sergey Kirgizov, Dec 24 2016

			G.f. = x^2 + 6*x^3 + 36*x^4 + 240*x^5 + 1800*x^6 + 15120*x^7 + 141120*x^8 + ...
a(10) = (1+2+3+4+5+6+7+8+9)*(1*2*3*4*5*6*7*8*9) = 16329600. - _Reinhard Zumkeller_, May 15 2010

A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 90, ex. 4.
Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 156.
A. P. Prudnikov, Yu. A. Brychkov and O.I. Marichev, "Integrals and Series", Volume 1: "Elementary Functions", Chapter 4: "Finite Sums", New York, Gordon and Breach Science Publishers, 1986-1992.
John Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 44.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 2..100
Yasmin Aguillon et al., On Parking Functions and The Tower of Hanoi, arXiv:2206.00541 [math.CO], 2022.
Jean-Luc Baril, Sergey Kirgizov, and Vincent Vajnovszki, Patterns in treeshelves, arXiv:1611.07793 [cs.DM], 2016.
Kyle Celano, Jennifer Elder, Kimberly P. Hadaway, Pamela E. Harris, Jeremy L. Martin, Amanda Priestley, and Gabe Udell, Statistics on L-interval parking functions, arXiv:2507.07243 [math.CO], 2025. See p. 7.
Eldar Fischer, Johann A. Makowsky, and Vsevolod Rakita, MC-finiteness of restricted set partition functions, arXiv:2302.08265 [math.CO], 2023.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 399.
Jennifer Elder, Pamela E. Harris, Jan Kretschmann, and J. Carlos Martínez Mori, Boolean intervals in the weak order of S_n, arXiv:2306.14734 [math.CO], 2023.
Lucas Chaves Meyles, Pamela E. Harris, Richter Jordaan, Gordon Rojas Kirby, Sam Sehayek, and Ethan Spingarn, Unit-Interval Parking Functions and the Permutohedron, arXiv:2305.15554 [math.CO], 2023.
Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets
Sandi Klavžar, Uroš Milutinović and Ciril Petr, Hanoi graphs and some classical numbers, Expo. Math. 23 (2005), no. 4, 371-378.
Siegfried Lehr, Jeffrey Shallit, and John Tromp, On the vector space of the automatic reals, Theoret. Comput. Sci. 163 (1996), no. 1-2, 193-210.
P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257-260.
P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257-260. [Annotated scanned copy]
Eric Weisstein's World of Mathematics, Bruhat Graph.
Eric Weisstein's World of Mathematics, Edge Count.
Eric Weisstein's World of Mathematics, Permutation Ascent.

Cf. A001710, A052609, A062119, A075181, A060638, A060608, A060570, A060612, A135218, A019538, A053495, A051683, A213168, A278677, A278678, A278679, A008292.
A002868 is an essentially identical sequence.
Column 2 of |A008297|.
Third column (m=2) of triangle |A111596(n, m)|: matrix product of |S1|.S2 Stirling number matrices.
Cf. also A000110, A000111.
Cf. A001113, A001620, A091725, A099285.

a001286 n = sum[1..n-1] * product [1..n-1]
-- Reinhard Zumkeller, Aug 01 2011

[(n-1)*Factorial(n)/2: n in [2..25]]; // Vincenzo Librandi, Sep 09 2016

seq(sum(mul(j,j=3..n), k=2..n), n=2..21); # Zerinvary Lajos, Jun 01 2007

Table[Sum[n!, {i, 2, n}]/2, {n, 2, 20}] (* Zerinvary Lajos, Jul 12 2009 *)
nn=20;With[{a=Accumulate[Range[nn]],t=Range[nn]!},Times@@@Thread[{a,t}]] (* Harvey P. Dale, Jan 26 2013 *)
Table[(n - 1) n! / 2, {n, 2, 30}] (* Vincenzo Librandi, Sep 09 2016 *)

A001286(n):=(n-1)*n!/2$
makelist(A001286(n),n,1,30); /* Martin Ettl, Nov 03 2012 */

a(n)=(n-1)*n!/2 \\ Charles R Greathouse IV, Nov 20 2012

from _future_ import division
A001286_list = [1]
for n in range(2,100):
    A001286_list.append(A001286_list[-1]*n*(n+1)//(n-1)) # Chai Wah Wu, Apr 11 2018

[(n-1)*factorial(n)/2 for n in range(2, 21)] # Zerinvary Lajos, May 16 2009

a(n) = Sum_{i=0..n-1} (-1)^(n-i-1) * i^n * binomial(n-1,i). - Yong Kong (ykong(AT)curagen.com), Dec 26 2000 [corrected by Amiram Eldar, May 02 2022]
E.g.f.: x^2/[2(1-x)^2]. - Ralf Stephan, Apr 02 2004
a(n+1) = (-1)^(n+1)*det(M_n) where M_n is the n X n matrix M_(i,j)=max(i*(i+1)/2,j*(j+1)/2). - Benoit Cloitre, Apr 03 2004
Row sums of table A051683. - Alford Arnold, Sep 29 2006
5th binomial transform of A135218: (1, 1, 1, 25, 25, 745, 3145, ...). - Gary W. Adamson, Nov 23 2007
If we define f(n,i,x) = Sum_{k=i..n} Sum_{j=i..k} binomial(k,j)*Stirling1(n,k)*Stirling2(j,i)*x^(k-j) then a(n)=(-1)^n*f(n,2,-2), (n>=2). - Milan Janjic, Mar 01 2009
a(n) = A000217(n-1)*A000142(n-1). - Reinhard Zumkeller, May 15 2010
a(n) = (n+1)!*Sum_{k=1..n-1} 1/(k^2+3*k+2). - Gary Detlefs, Sep 14 2011
Sum_{n>=2} 1/a(n) = 2*(2 - exp(1) - gamma + Ei(1)) = 1.19924064599..., where gamma = A001620 and Ei(1) = A091725. - Ilya Gutkovskiy, Nov 24 2016
a(n+1) = a(n)*n*(n+1)/(n-1). - Chai Wah Wu, Apr 11 2018
Sum_{n>=2} (-1)^n/a(n) = 2*(gamma - Ei(-1)) - 2/e, where e = A001113 and Ei(-1) = -A099285. - Amiram Eldar, May 02 2022

A008517 Second-order Eulerian triangle T(n,k), 1 <= k <= n.

Original entry on oeis.org

1, 1, 2, 1, 8, 6, 1, 22, 58, 24, 1, 52, 328, 444, 120, 1, 114, 1452, 4400, 3708, 720, 1, 240, 5610, 32120, 58140, 33984, 5040, 1, 494, 19950, 195800, 644020, 785304, 341136, 40320, 1, 1004, 67260, 1062500, 5765500, 12440064, 11026296, 3733920, 362880

Offset: 1

N. J. A. Sloane

Second-order Eulerian numbers <> = T(n,k+1) count the permutations of the multiset {1,1,2,2,...,n,n} with k ascents with the restriction that for all m, all integers between the two copies of m are less than m. In particular, the two 1s are always next to each other.
When seen as coefficients of polynomials with descending exponents, evaluations are in A000311 (x=2) and A001662 (x=-1).
The row reversed triangle is A112007. There one can find comments on the o.g.f.s for the diagonals of the unsigned Stirling1 triangle |A008275|.
Stirling2(n,n-k) = Sum_{m=0..k-1} T(k,m+1)*binomial(n+k-1+m, 2*k), k>=1. See the Graham et al. reference p. 271 eq. (6.43).
This triangle is the coefficient triangle of the numerator polynomials appearing in the o.g.f. for the k-th diagonal (k >= 1) of the Stirling2 triangle A048993.
The o.g.f. for column k satisfies the recurrence G(k,x) = x*(2*x*(d/dx)G(k-1,x) + (2-k)*G(k-1,x))/(1-k*x), k >= 2, with G(1,x) = 1/(1-x). - Wolfdieter Lang, Oct 14 2005
This triangle is in some sense generated by the differential equation y' = 1 - 2/(1+x+y). (This is the differential equation satisfied by the function defined implicitly as x+y=exp(x-y).) If we take y = a(0) + a(1)x + a(2)x^2 + a(3)x^3 + ... and assume a(0)=c then all the a's may be calculated formally in terms of c and we have a(1) = (c-1)/(c+1) and, for n > 1, a(n) = 2^n/n! (1+c)^(1-2n)( T(n,1)c - T(n,2)c^2 + T(n,3)c^3 - ... + (-1)^(n-1) T(n,n)c^n ). - Moshe Shmuel Newman, Aug 08 2007
From the recurrence relation, the generating function F(x,y) := 1 + Sum_{n>=1, 1<=k<=n} [T(n,k)x^n/n!*y^k] satisfies the partial differential equation F = (1/y-2x)F_x + (y-1)F_y, with (non-elementary) solution F(x,y) = (1-y)/(1-Phi(w)) where w = y*exp(x(y-1)^2-y) and Phi(x) is defined by Phi(x) = x*exp(Phi(x)). By Lagrange inversion (see Wilf's book "generatingfunctionology", page 168, Example 1), Phi(x) = Sum_{n>=1} n^(n-1)*x^n/n!. Thus Phi(x) can alternatively be described as the e.g.f. for rooted labeled trees on n vertices A000169. - David Callan, Jul 25 2008
A method for solving PDEs such as the one above for F(x,y) is described in the Klazar reference (see pages 207-208). In his case, the auxiliary ODE dy/dx = b(x,y)/a(x,y) is exact; in this case it is not exact but has an integrating factor depending on y alone, namely y-1. The e.g.f. for the row sums A001147 is 1/sqrt(1-2*x) and the demonstration that F(x,1) = 1/sqrt(1-2*x) is interesting: two applications of l'Hopital's rule to lim_{y->1}F(x,y) yield F(x,1) = 1/(1-2x)*1/F(x,1). So l'Hopital's rule doesn't directly yield F(x,1) but rather an equation to be solved for F(x,1)!. - David Callan, Jul 25 2008
From Tom Copeland, Oct 12 2008; May 19 2010: (Start)
Let P(0,t)= 0, P(1,t)= 1, P(2,t)= t, P(3,t)= t + 2 t^2, P(4,t)= t + 8 t^2 + 6 t^3, ... be the row polynomials of the present array, then
exp(x*P(.,t)) = ( u + Tree(t*exp(u)) ) / (1-t) = WD(x*(1-t), t/(1-t)) / (1-t)
where u = x*(1-t)^2 - t, Tree(x) is the e.g.f. of A000169 and WD(x,t) is the e.g.f. for A134991, relating the Ward and 2-Eulerian polynomials by a simple transformation.
Note also apparently P(4,t) / (1-t)^3 = Ward Poly(4, t/(1-t)) = essentially an e.g.f. for A093500.
The compositional inverse of f(x,t) = exp(P(.,t)*x) about x=0 is
g(x,t) = ( x - (t/(1-t)^2)*(exp(x*(1-t))-x*(1-t)-1) )
= x - t*x^2/2! - t*(1-t)*x^3/3! - t*(1-t)^2*x^4/4! - t*(1-t)^3*x^5/5! - ... .
Can apply A134685 to these coefficients to generate f(x,t). (End)
Triangle A163936 is similar to the one given above except for an extra right hand column [1, 0, 0, 0, ... ] and that its row order is reversed. - Johannes W. Meijer, Oct 16 2009
From Tom Copeland, Sep 04 2011: (Start)
Let h(x,t) = 1/(1-(t/(1-t))*(exp(x*(1-t))-1)), an e.g.f. in x for row polynomials in t of A008292, then the n-th row polynomial in t of the table A008517 is given by ((h(x,t)*D_x)^(n+1))x with the derivative evaluated at x=0.
Also, df(x,t)/dx = h(f(x,t),t) where f(x,t) is an e.g.f. in x of the row polynomials in t of A008517, i.e., exp(x*P(.,t)) in Copeland's 2008 comment. (End)
The rows are the h-vectors of A134991. - Tom Copeland, Oct 03 2011
Hilbert series of the pre-WDVV ring, thus h-vectors of the Whitehouse simplicial complex (cf. Readdy, Table 1). - Tom Copeland, Sep 20 2014
Arises in Buckholtz's analysis of the error term in the series for exp(nz). - N. J. A. Sloane, Jul 05 2016

			Triangle begins:
  1;
  1,   2;
  1,   8,   6;
  1,  22,  58,  24;
  1,  52, 328, 444, 120; ...
Row 3: There are three plane increasing 0-1-2-3 trees on 3 vertices. The number of colors are shown to the right of a vertex.
.
    1o (2*t+1)         1o t*(t+2)      1o t*(t+2)
     |                 / \             / \
     |                /   \           /   \
    2o (2*t+1)      2o    3o        3o    2o
     |
     |
    3o
.
The total number of trees is (2*t+1)^2 + t*(t+2) + t*(t+2) = 1 + 8*t + 6*t^2.

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, 2nd ed. Addison-Wesley, Reading, MA, 1994, p. 270. [with offsets [0,0]: see A201637]

Vincenzo Librandi, Rows n = 1..50, flattened
Peter Bala, Diagonals of triangles with generating function exp(t*F(x)).
J. Fernando Barbero G., Jesús Salas, and Eduardo J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. I. General Structure, arXiv:1307.2010 [math.CO], 2013.
J. F. Barbero G., J. Salas and E. J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. II. Applications, arXiv preprint arXiv:1307.5624 [math.CO], 2013.
J. Fernando Barbero G., Jesús Salas, and Eduardo J. S. Villaseñor, Generalized Stirling permutations and forests: Higher-order Eulerian and Ward numbers, Electronic Journal of Combinatorics 22(3) (2015), #P3.37.
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.
J. D. Buckholtz, Concerning an approximation of Copson, Proc. Amer. Math. Soc., 14 (1963), 564-568.
Naiomi T. Cameron and Kendra Killpatrick, Statistics on Linear Chord Diagrams, arXiv:1902.09021 [math.CO], 2019.
L. Carlitz, The coefficients in an asymptotic expansion, Proc. Amer. Math. Soc. 16 (1965) 248-252.
L. Carlitz, Some numbers related to the Stirling numbers of the first and second kind, Univ. Beograd Publ. Elektrotehn. Fak. Ser. Mat. Fiz., Numbers 544-576 (1976): 49-55. [Annotated scanned copy. The triangle is A008517.]
T. Copeland, Generators, Inversion, and Matrix, Binomial, and Integral Transforms
R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey and D. E. Knuth, On the Lambert W Function, Advances in Computational Mathematics, Vol. 5 (1996), pp. 329-359, formula (3.6), alternative link.
Ming-Jian Ding and Jiang Zeng, Proof of an explicit formula for a series from Ramanujan's Notebooks via tree functions, arXiv:2307.00566 [math.CO], 2023.
D. Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions. arXiv:math/0501052v2 [math.CA], 2005.
Sen-Peng Eu, Tung-Shan Fu, and Yeh-Jong Pan, A refined sign-balance of simsun permutations, Eur. J. Comb. 36 (2014) 97-109
W. Gautschi, Exponential integral ... for large values of n, Jrn. of Rsch. of the National Bureau of Standards, Vol. 62, No. 3, March 1959, Rsch. paper 2941. - _Tom Copeland_, Jan 02 2016
I. Gessel and R. P. Stanley, Stirling polynomials, J. Combin. Theory, A 24 (1978), 24-33.
J. Ginsburg, Note on Stirling's Numbers, Amer. Math. Monthly 35 (1928), no. 2, 77-80. - _David Callan_, Aug 27 2009
Jim Haglund and Mirko Visontai, Stable multivariate Eulerian polynomials and generalized Stirling permutations, European Journal of Combinatorics, Volume 33, Issue 4, May 2012, pp. 477-487.
M. Klazar, Twelve countings with rooted plane trees, European Journal of Combinatorics 18 (1997), 195-210; Addendum, 18 (1997), 739-740.
Dmitry V. Kruchinin and Vladimir V. Kruchinin, A generating function for the Euler numbers of the second kind and its application, arXiv:1802.09003 [math.CO], 2018.
Paul Levande, Two New Interpretations of the Fishburn Numbers and their Refined Generating Functions, arXiv:1006.3013 [math.CO], 2010.
Feihu Liu, Guoce Xin, and Chen Zhang, Ehrhart Polynomials of Order Polytopes: Interpreting Combinatorial Sequences on the OEIS, arXiv:2412.18744 [math.CO], 2024. See p. 29.
Peter Luschny, Second-order Eulerian numbers, A companion to A340556, Feb 2021.
Shi-Mei Ma, Some combinatorial sequences associated with context-free grammars, arXiv:1208.3104v2 [math.CO], 2012. - From _N. J. A. Sloane_, Aug 21 2012
S.-M. Ma, T. Mansour, and M. Schork. Normal ordering problem and the extensions of the Stirling grammar, arXiv preprint arXiv:1308.0169 [math.CO], 2013.
S.-M. Ma, T. Mansour, The 1/k-Eulerian polynomials and k-Stirling permutations, arXiv preprint arXiv:1409.6525 [math.CO], 2014.
O. J. Munch, Om potensproduktsummer [Norwegian, English summary], Nordisk Matematisk Tidskrift, 7 (1959), 5-19. [Annotated scanned copy]
O. J. Munch, Om potensproduktsummer [ Norwegian, English summary ], Nordisk Matematisk Tidskrift, 7 (1959), 5-19.
Andrew Elvey Price and Alan D. Sokal, Phylogenetic trees, augmented perfect matchings, and a Thron-type continued fraction (T-fraction) for the Ward polynomials, arXiv:2001.01468 [math.CO], 2020.
M. A. Readdy, The pre-WDVV ring of physics and its topology, preprint 2002, The Ramanujan Journal, October 2005, Volume 10, Issue 2, pp 269-281.
Grzegorz Rzadkowski and M Urlinska, A Generalization of the Eulerian Numbers, arXiv preprint arXiv:1612.06635, 2016
C. D. Savage and G. Viswanathan, The 1/k-Eulerian polynomials, Elec. J. of Comb., Vol. 19, Issue 1, #P9 (2012). - From _N. J. A. Sloane_, Feb 06 2013
M. D. Schmidt, Generalized j-Factorial Functions, Polynomials, and Applications , J. Int. Seq. 13 (2010), 10.6.7, Section 5.1.
Umesh Shankar, Log-concavity of rows of triangular arrays satisfying a certain super-recurrence, arXiv:2508.12467 [math.CO], 2025. See p. 4.
L. M. Smiley, Completion of a rational function sequence of Carlitz, arXiv:0006106 [math.CO], 2000.
M. Z. Spivey, On Solutions to a General Combinatorial Recurrence, J. Int. Seq. 14 (2011) # 11.9.7.
Eric Weisstein's World of Mathematics, Second-Order Eulerian Triangle
Wikipedia, Eulerian numbers of the second kind

Columns include A005803, A004301, A006260.
Right-hand columns include A000142, A002538, A002539.
Row sums are A001147.
For a (0,0) based version as used in 'Concrete Mathematics' and by Maple see A201637. For a (0,0) based version which has this triangle as a subtriangle see A340556.

with(combinat): A008517 := proc(n, m) local k: add((-1)^(n+k)* binomial(2*n+1, k)* stirling1(2*n-m-k+1, n-m-k+1), k=0..n-m) end: seq(seq(A008517(n, m), m=1..n), n=1..8);
# Johannes W. Meijer, Oct 16 2009, revised Nov 22 2012
A008517 := proc(n,k) option remember; `if`(n=1,`if`(k=0,1,0), A008517(n-1,k)* (k+1) + A008517(n-1,k-1)*(2*n-k-1)) end: seq(print(seq(A008517(n,k), k=0..n-1)), n=1..9);
# Peter Luschny, Apr 20 2011

a[n_, m_] = Sum[(-1)^(n + k)*Binomial[2 n + 1, k]*StirlingS1[2n-m-k+1, n-m-k+1], {k, 0, n-m}]; Flatten[Table[a[n, m], {n, 1, 9}, {m, 1, n}]][[1 ;; 44]] (* Jean-François Alcover, May 18 2011, after Johannes W. Meijer *)

{T(n, k) = my(z); if( n<1, 0, z = 1 + O(x); for( k=1, n, z = 1 + intformal( z^2 * (z+y-1))); n! * polcoeff( polcoeff(z, n),k))}; /* Michael Somos, Oct 13 2002 */

{T(n,k)=polcoeff((1-x)^(2*n+1)*sum(j=0,2*n+1,j^(n+j)*x^j/j!*exp(-j*x +x*O(x^k))),k)} \\ Paul D. Hanna, Oct 31 2012
for(n=1,10,for(k=1,n,print1(T(n,k),", "));print(""))

T(n, m) = sum(k=0, n-m, (-1)^(n+k)*binomial(2*n+1, k)*stirling(2*n-m-k+1, n-m-k+1, 1)); \\ Michel Marcus, Dec 07 2021

@CachedFunction
def A008517(n, k):
    if n==1: return 1 if k==0 else 0
    return A008517(n-1,k)*(k+1)+A008517(n-1,k-1)*(2*n-k-1)
for n in (1..9): [A008517(n, k) for k in(0..n-1)] # Peter Luschny, Oct 31 2012

T(n,k) = 0 if n < k, T(1,1) = 1, T(n,-1) = 0, T(n,k) = k*T(n-1,k) + (2*n-k)*T(n-1,k-1).
a(n,m) = Sum_{k=0..n-m} (-1)^(n+k)*binomial(2*n+1, k)*Stirling1(2*n-m-k+1, n-m-k+1). - Johannes W. Meijer, Oct 16 2009
From Peter Bala, Sep 29 2011: (Start)
For k = 0,1,2,... put G(k,x,t) := x-(1+2^k*t)*x^2/2+(1+2^k*t+3^k*t^2)*x^3/3-(1+2^k*t+3^k*t^2+4^k*t^3)*x^4/4+.... Then the series reversion of G(k,x,t) with respect to x gives an e.g.f. for the present table when k = 1 and for the Eulerian numbers A008292 when k = 0.
Let v = -t*exp((1-t)^2*x-t) and let B(x,t) = -(1+1/t*LambertW(v))/(1+LambertW(v)). From the e.g.f. given by Copeland above we find B(x,t) = compositional inverse with respect to x of G(1,x,t) = Sum_{n>=1} R(n,t)*x^n/n! = x+(1+2*t)*x^2/2!+(1+8*t+6*t^2)*x^3/3!+.... The function B(x,t) satisfies the differential equation dB/dx = (1+B)*(1+t*B)^2 = 1 + (2*t+1)*B + t*(t+2)*B^2 + t^2*B^3.
Applying [Bergeron et al., Theorem 1] gives a combinatorial interpretation for the row generating polynomials R(n,t): R(n,t) counts plane increasing trees where each vertex has outdegree <= 3, the vertices of outdegree 1 come in 2*t+1 colors, the vertices of outdegree 2 come in t*(t+2) colors and the vertices of outdegree 3 come in t^2 colors. An example is given below. Cf. A008292. Applying [Dominici, Theorem 4.1] gives the following method for calculating the row polynomials R(n,t): Let f(x,t) = (1+x)*(1+t*x)^2 and let D be the operator f(x,t)*d/dx. Then R(n+1,t) = D^n(f(x,t)) evaluated at x = 0. (End)
From Tom Copeland, Oct 03 2011: (Start)
a(n,k) = Sum_{i=0..k} (-1)^(k-i) binomial(n-i,k-i) A134991(n,i), offsets 0.
  P(n+1,t) = (1-t)^(2n+1) Sum_{k>=1} k^(n+k) [t*exp(-t)]^k / k! for n>0; consequently, Sum_{k>=1} (-1)^k k^(n+k) x^k/k!= [1+LW(x)]^(-(2n+1))P[n+1,-LW(x)] where LW(x) is the Lambert W-Function and P(n,t), for n > 0, are the row polynomials as given in Copeland's 2008 comment. (End)
The e.g.f. A(x,t) = -v * { Sum_{j>=1} D(j-1,u) (-z)^j / j! } where u=x*(1-t)^2-t, v=(1+u)/(1-t), z=(t+u)/[(1+u)^2] and D(j-1,u) are the polynomials of A042977. dA(x,t)/dx=(1-t)/[1+u-(1-t)A(x,t)]=(1-t)/{1+LW[-t exp(u)]}, (Copeland's e.g.f. in 2008 comment). - Tom Copeland, Oct 06 2011
A133314 applied to the derivative of A(x,t) implies (a.+b.)^n = 0^n, for (b_n)=P(n+1,t) and (a_0)=1, (a_1)=-t, and (a_n)=-P(n,t) otherwise. E.g., umbrally, (a.+b.)^2 = a_2*b_0 + 2 a_1*b_1 + a_0*b_2 = 0. - Tom Copeland, Oct 08 2011
The compositional inverse (with respect to x) of y = y(t;x) = (x-t*(exp(x)-1)) is  1/(1-t)*y + t/(1-t)^3*y^2/2! + (t+2*t^2)/(1-t)^5*y^3/3! + (t+8*t^2+6*t^3)/(1-t)^7*y^4/4! + .... The numerator polynomials of the rational functions in t are the row polynomials of this triangle. As observed in the Comments section, the rational functions in t are the generating functions for the diagonals of the triangle of Stirling numbers of the second kind (A048993). See the Bala link for a proof. Cf. A112007 and A134991. - Peter Bala, Dec 04 2011
O.g.f. of row n: (1-x)^(2*n+1) * Sum_{k>=0} k^(n+k) * exp(-k*x) * x^k/k!. - Paul D. Hanna, Oct 31 2012
T(n, k) = n!*[x^n][t^k](egf) where egf = (1-t)/(1 + LambertW(-exp(t^2*x - 2*t*x - t + x)*t)) and after expansion W(-exp(-t)t) is substituted by (-t). - Shamil Shakirov, Feb 17 2025

A112007 Coefficient triangle for polynomials used for o.g.f.s for unsigned Stirling1 diagonals.

Original entry on oeis.org

1, 2, 1, 6, 8, 1, 24, 58, 22, 1, 120, 444, 328, 52, 1, 720, 3708, 4400, 1452, 114, 1, 5040, 33984, 58140, 32120, 5610, 240, 1, 40320, 341136, 785304, 644020, 195800, 19950, 494, 1, 362880, 3733920, 11026296, 12440064, 5765500, 1062500, 67260, 1004, 1

Offset: 0

Wolfdieter Lang, Sep 12 2005

This is the row reversed second-order Eulerian triangle A008517(k+1,k+1-m). For references see A008517.
The o.g.f. for the k-th diagonal, k >= 1, of the unsigned Stirling1 triangle |A008275| is G1(1,x)=1/(1-x) if k=1 and G1(k,x) = g1(k-2,x)/(1-x)^(2*k-1), if k >= 2, with the row polynomials g1(k;x):=Sum_{m=0..k} a(k,m)*x^m.
The recurrence eq. for the row polynomials is g1(k,x)=((k+1)+k*x)*g1(k-1,x) + x*(1-x)*(d/dx)g1(k-1,x), k >= 1, with input g1(0,x):=1.
The column sequences start with A000142 (factorials), A002538, A002539, A112008, A112485.
This o.g.f. computation was inspired by Bender et al. article where the Stirling polynomials have been rediscussed.
The A163936 triangle is identical to the triangle given above except for an extra right hand column [1, 0, 0, 0, ... ]. The A163936 triangle is related to the higher order exponential integrals E(x,m,n), see A163931 and A163932. - Johannes W. Meijer, Oct 16 2009

			Triangle begins:
    1;
    2,   1;
    6,   8,   1;
   24,  58,  22,   1;
  120, 444, 328,  52,   1;
  ...
G.f. for k=3 sequence A000914(n-1), [2,11,35,85,175,322,546,...], is G1(3,x)= g1(1,x)/(1-x)^5= (2+x)/(1-x)^5.

Robert Israel, Table of n, a(n) for n = 0..10010 (rows 0 to 140, flattened)
Peter Bala, Diagonals of triangles with generating function exp(t*F(x))
C. M. Bender, D. C. Brody and B. K. Meister, Bernoulli-like polynomials associated with Stirling Numbers, arXiv:math-ph/0509008 [math-ph], 2005.
E. Burlachenko, Composition polynomials of the RNA matrix and B-composition polynomials of the Riordan pseudo-involution, arXiv:1907.12272 [math.NT], 2019.
Tom Copeland, Generators, Inversion, and Matrix, Binomial, and Integral Transforms
Wolfdieter Lang, First 10 rows.
Wolfdieter Lang, On Generating functions of Diagonals Sequences of Sheffer and Riordan Number Triangles, arXiv:1708.01421 [math.NT], August 2017.
R. Paris, A uniform asymptotic expansion for the incomplete gamma function, Journal of Computational and Applied Mathematics, 148 (2002), p. 223-239. See 234. [_Tom Copeland_, Jan 03 2016]
Andrew Elvey Price, Alan D. Sokal, Phylogenetic trees, augmented perfect matchings, and a Thron-type continued fraction (T-fraction) for the Ward polynomials, arXiv:2001.01468 [math.CO], 2020.

Row sums give A001147(k+1) = (2*k+1)!!, k>=0.

a:= proc(k,m) option remember; if m >= 0 and k >= 0 then (k+m+1)*procname(k-1,m)+(k-m+1)*procname(k-1,m-1) else 0 fi end proc:
a(0,0):= 1:
seq(seq(a(k,m),m=0..k),k=0..10); # Robert Israel, Jul 20 2017

a[k_, m_] = Sum[(-1)^(k + n + 1)*Binomial[2k + 3, n]*StirlingS1[m + k - n + 2, m + 1 - n], {n, 0, m}]; Flatten[Table[a[k, m], {k, 0, 8}, {m, 0, k}]][[1 ;; 45]] (* Jean-François Alcover, Jun 01 2011, after Johannes W. Meijer *)

a(k, m)=sum(n=0, m, (-1)^(k + n + 1)*binomial(2*k + 3, n)*stirling(m + k - n + 2, m + 1 - n, 1));
for(k=0, 10, for(m=0, k, print1(a(k, m),", "))) \\ Indranil Ghosh, Jul 21 2017

a(k, m) = (k+m+1)*a(k-1, m) + (k-m+1)*a(k-1, m-1), if k >= m >= 0, a(0, 0)=1; a(k, -1):=0, otherwise 0.
a(k,m) = Sum_{n=0..m} (-1)^(k+n+1)*C(2*k+3,n)*Stirling1(m+k-n+2,m+1-n). - Johannes W. Meijer, Oct 16 2009
The compositional inverse (with respect to x) of y = y(t,x) = (x+t*log(1-x)) is  x = x(t,y) = 1/(1-t)*y + t/(1-t)^3*y^2/2! + (2*t+t^2)/(1-t)^5*y^3/3! + (6*t+8*t^2+t^3)/(1-t)^7*y^4/4! + .... The numerator polynomials of the rational functions in t are the row polynomials of this triangle. As observed above, the rational functions in t are the generating functions for the diagonals of |A008275|. See the Bala link for a proof. Cf. A008517. - Peter Bala, Dec 02 2011

A288964 Number of key comparisons to sort all n! permutations of n elements by quicksort.

Original entry on oeis.org

0, 0, 2, 16, 116, 888, 7416, 67968, 682272, 7467840, 88678080, 1136712960, 15655438080, 230672171520, 3621985113600, 60392753971200, 1065907048550400, 19855856150323200, 389354639411404800, 8017578241634304000, 172991656889856000000, 3903132531903897600000

Offset: 0

Daniel Krenn, Jun 20 2017

nonn

From Petros Hadjicostas, May 04 2020: (Start)
Depending on the assumptions used in the literature, the average number to sort n items in random order by quicksort appears as -C*n + 2*(1+n)*HarmonicNumber(n), where C = 2, 3, or 4. (To get the number of key comparisons to sort all n! permutations of n elements by quicksort, multiply this number by n!.)
For this sequence, we have C = 4. The corresponding number of key comparisons to sort all n! permutations of n elements by quicksort when C = 3 is A063090(n). Thus, a(n) = A063090(n) - n!*n.
For more details, see my comments and references for sequences A093418, A096620, and A115107. (End)

Daniel Krenn, Table of n, a(n) for n = 0..100
Pamela E. Harris, Jan Kretschmann, and J. Carlos Martínez Mori, Lucky Cars and the Quicksort Algorithm, arXiv:2306.13065 [math.CO], 2023.
Index entries for sequences related to sorting

Cf. A063090, A093418, A096620, A115107, A117627, A117628, A159324, A288965.

a:= proc(n) option remember; `if`(n<3, n*(n-1),
      ((2*n^2-3*n-1)*a(n-1)-(n-1)^2*n*a(n-2))/(n-2))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Jun 21 2017

a[n_] := n! (2(n+1)HarmonicNumber[n] - 4n);
a /@ Range[0, 25] (* Jean-François Alcover, Oct 29 2020 *)

[n.factorial() * (2*(n+1)*sum(1/k for k in srange(1, n+1)) - 4*n) for n in srange(21)]

# alternative using the recurrence relation
@cached_function
def c(n):
    if n <= 1:
        return 0
    return (n - 1) + 2/n*sum(c(i) for i in srange(n))
[n.factorial() * c(n) for n in srange(21)]

a(n) = n!*(2*(n+1)*H(n) - 4*n).
c(n) = a(n) / n! satisfies c(n) = (n-1) + 2/n * Sum_{i < n} c(i).
a(n) = 2*A002538(n-1), n >= 2. - Omar E. Pol, Jun 20 2017
E.g.f.: -2*log(1-x)/(1-x)^2 - 2*x/(1-x)^2. - Daniel Krenn, Jun 20 2017
a(n) = ((2*n^2-3*n-1)*a(n-1) -(n-1)^2*n*a(n-2))/(n-2) for n >= 3, a(n) = n*(n-1) for n < 3. - Alois P. Heinz, Jun 21 2017
From Petros Hadjicostas, May 03 2020: (Start)
a(n) = A063090(n) - n!*n for n >= 1.
a(n) = n!*A115107(n)/A096620(n) = n!*(-n + A093418(n)/A096620(n)). (End)

A340556 E2(n, k), the second-order Eulerian numbers with E2(0, k) = δ_{0, k}. Triangle read by rows, E2(n, k) for 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 1, 8, 6, 0, 1, 22, 58, 24, 0, 1, 52, 328, 444, 120, 0, 1, 114, 1452, 4400, 3708, 720, 0, 1, 240, 5610, 32120, 58140, 33984, 5040, 0, 1, 494, 19950, 195800, 644020, 785304, 341136, 40320, 0, 1, 1004, 67260, 1062500, 5765500, 12440064, 11026296, 3733920, 362880

Offset: 0

Peter Luschny, Feb 05 2021

The second-order Eulerian number E2(n, k) is the number of Stirling permutations of order n with exactly k descents; here the last index is defined to be a descent. More formally, let Q_n denote the set of permutations of the multiset {1,1,2,2, ..., n,n} in which, for all j, all entries between two occurrences of j are larger than j, then E2(n, k) = card({s in Q_n with des(s) = k}), where des(s) = card({j: s(j) > s(j+1)}) is the number of descents of s.
Also the number of Riordan trapezoidal words of length n with k distinct letters (see Riordan 1976, p. 9).
Also the number of rooted plane trees on n + 1 vertices with k leaves (see Janson 2008, p. 543).
Let b(n) = (1/2)*Sum_{k=0..n-1} (-1)^k*E2(n-1, k+1) / C(2*n-1, k+1). Apparently b(n) = Bernoulli(n, 1) = -n*Zeta(1 - n) = Integral_{x=0..1}F_n(x) for n >= 1. Here F_n(x) are the signed Fubini polynomials (A278075). (See Rzadkowski and Urlinska, example 4.)

			Triangle starts:
  [0] 1;
  [1] 0, 1;
  [2] 0, 1, 2;
  [3] 0, 1, 8,    6;
  [4] 0, 1, 22,   58,    24;
  [5] 0, 1, 52,   328,   444,     120;
  [6] 0, 1, 114,  1452,  4400,    3708,    720;
  [7] 0, 1, 240,  5610,  32120,   58140,   33984,    5040;
  [8] 0, 1, 494,  19950, 195800,  644020,  785304,   341136,   40320;
  [9] 0, 1, 1004, 67260, 1062500, 5765500, 12440064, 11026296, 3733920, 362880.
To illustrate the generating function for row 3: The expansion of (1 - x)^7*(x*exp(-x) + 16*x^2*exp(-x)^2 + (243*x^3*exp(-x)^3)/2) gives the polynomial x + 8*x^2 + 6*x^3. The coefficients of this polynomial give row 3.
.
Stirling permutations of order 3 with exactly k descents: (When counting the descents one may assume an invisible '0' appended to the permutations.)
  T[3, k=0]:
  T[3, k=1]: 112233;
  T[3, k=2]: 331122; 223311; 221133; 133122; 122331; 122133; 113322; 112332;
  T[3, k=3]: 332211; 331221; 233211; 221331; 133221; 123321.

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, 2nd ed. Addison-Wesley, Reading, MA, 1994, p. 270.

J. Fernando Barbero G., Jesús Salas, and Eduardo J. S. Villaseñor, Generalized Stirling permutations and forests: Higher-order Eulerian and Ward numbers, Electronic Journal of Combinatorics 22(3), 2015.
Kenny Barrese, Jennifer Elder, Pamela E. Harris, and Anthony Simpson, Enumerating Flat Fubini Rankings, arXiv:2504.06466 [math.CO], 2025. Conjecture 4.4. p. 14.
Brian Drake, An inversion theorem for labeled trees and some limits of areas under lattice paths (Example 1.10.1), Thesis, Brandeis Univ., Aug. 2008, p. 58.
Sergi Elizalde, Descents on quasi-Stirling permutations, arXiv:2002.00985 [math.CO], 2020.
I. Gessel and R. P. Stanley, Stirling polynomials, J. Combin. Theory, A 24, 24-33, 1978.
Svante Janson, Plane recursive trees, Stirling permutations and an urn model, Fifth Colloquium on Mathematics and Computer Science, 541-547, Discrete Math. Theor. Comput. Sci. Proc., AI, 2008.
Peter Luschny, A companion to A340556, A SageMath-Jupyter notebook, Feb. 2021.
Peter Luschny, How are the Eulerian numbers of the first-order related to the Eulerian numbers of the second-order?, MathOverflow, Feb. 2021.
Andrew Elvey Price and Alan D. Sokal, Phylogenetic trees, augmented perfect matchings, and a Thron-type continued fraction (T-fraction) for the Ward polynomials, arXiv:2001.01468 [math.CO], 2020.
John Riordan, The blossoming of Schröder's fourth problem, Acta Math., 137 (1976), 1-16.
G. Rzadkowski and M. Urlinska, A Generalization of the Eulerian Numbers, arXiv:1612.06635 [math.CO], 2016.

Indexing the second-order Eulerian numbers comes in three flavors: A008517 (following Riordan and Comtet), A201637 (following Graham, Knuth, and Patashnik) and this indexing, extending the definition of Gessel and Stanley. (A008517 is the main entry of the numbers.) The corresponding triangles of the first-order Eulerian numbers are A008292, A173018, and A123125.
Row reversed: A163936 (with offset = 0).
Values: E2poly(n, 1) = A001147(n), E2poly(n, -1) ~ -A001662(n+1), E2poly(n, 2) = A112487(n), 2^n*E2poly(n, 1/2) = A000311(n+1), 2^n*E2poly(n, -1/2) = A341106(n).
Diagonals: A000142, A002538, A002539, A112008, A112485.
Columns: A000007, A000012, A005803, A004301, A006260.
Cf. A008299, A137375, A008306, A106828, A269939, A278075, A331998.

# Using the recurrence:
E2 := proc(n, k) option remember;
if k = 0 and n = 0 then return 1 fi; if n < 0 then return 0 fi;
E2(n-1, k)*k + E2(n-1, k-1)*(2*n - k) end: seq(seq(E2(n, k), k = 0..n), n = 0..9);
# Using the row generating function:
E2egf := n -> (1-x)^(2*n+1)*add(k^(n+k)/k!*(x*exp(-x))^k, k=0..n);
T := (n, k) -> coeftayl(E2egf(n), x=0, k): seq(print(seq(T(n, j),j=0..n)), n=0..7);
# Using the built-in function:
E2 := (n, k) -> `if`(k=0, k^n, combinat:-eulerian2(n, k-1)):
# Using the compositional inverse (series reversion):
E2triangle := proc(N) local r, s, C; Order := N + 2;
s := solve(y = series(x - t*(exp(x) - 1), x), x):
r := n -> -n!*(t - 1)^(2*n - 1)*coeff(s, y, n); C := [seq(expand(r(n)), n = 1..N)];
seq(print(seq(coeff(C[n+1], t, k), k = 0..n)), n = 0..N-1) end: E2triangle(10);

T[n_, k_] := T[n, k] = If[k == 0, Boole[n == 0], If[n < 0, 0, k T[n - 1, k] + (2 n - k) T[n - 1, k - 1]]]; Table[T[n, k], {n, 0, 9}, {k, 0, n}] // Flatten
(* Via row polynomials: *)
E2poly[n_] := If[n == 0, 1,
  Expand[Simplify[x (x - 1)^(2 n) D[((1 - x)^(1 - 2 n) E2poly[n - 1]), x]]]];
Table[CoefficientList[E2poly[n], x], {n, 0, 9}] // Flatten
(* Series reversion *)
Revert[gf_, len_] := Module[{S = InverseSeries[Series[gf, {x, 0, len + 1}], x]},
Table[CoefficientList[(n + 1)! (1 - t)^(2 n + 1) Coefficient[S, x, n + 1], t],
{n, 0, len}] // Flatten]; Revert[x + t - t Exp[x], 6]

E2poly(n) = if(n == 0, 1, x*(x-1)^(2*n)*deriv((1-x)^(1-2*n)*E2poly(n-1)));
{ for(n = 0, 9, print(Vecrev(E2poly(n)))) }

T(n, k) = sum(j=0, n-k, (-1)^(n-j)*binomial(2*n+1, j)*stirling(2*n-k-j+1, n-k-j+1, 1)); \\ Michel Marcus, Feb 11 2021

# See also link to notebook.
@cached_function
def E2(n, k):
    if n < 0: return 0
    if k == 0: return k^n
    return k * E2(n - 1, k) + (2*n - k) * E2(n - 1, k - 1)  # Peter Luschny, Mar 08 2025

E2(n, k) = E2(n-1, k)*k + E2(n-1, k-1)*(2*n - k) for n > 0 and 0 <= k <= n, and E2(0, 0) = 1; in all other cases E(n, k) = 0.
E2(n, k) = Sum_{j=0..n-k}(-1)^(n-j)*binomial(2*n+1, j)*Stirling1(2*n-k-j+1, n-k-j+1).
E2(n, k) = Sum_{j=0..k}(-1)^(k-j)*binomial(2*n + 1, k - j)*Stirling2(n + j, j).
Stirling1(x, x - n) = (-1)^n*Sum_{k=0..n} E2(n, k)*binomial(x + k - 1, 2*n).
Stirling2(x, x - n) = Sum_{k=0..n} E2(n, k)*binomial(x + n - k, 2*n).
E2poly(n, x) = Sum_{k=0..n} E2(n, k)*x^k, as row polynomials.
E2poly(n, x) = x*(x-1)^(2*n)*d_{x}((1-x)^(1-2*n)*E2poly(n-1)) for n>=1 and E2poly(0)=1.
E2poly(n, x) = (1 - x)^(2*n + 1)*Sum_{k=0..n}(k^(n + k)/k!)*(x*exp(-x))^k.
W(n, k) = [x^k] (1+x)^n*E2poly(n, x/(1 + x)) are the Ward numbers A269939.
E2(n, k) = [x^k] (1-x)^n*Wpoly(n, x/(1 - x)); Wpoly(n, x) = Sum_{k=0..n}W(n, k)*x^k.
W(n, k) = Sum_{j=0..k} E2(n, j)*binomial(n - j, n - k).
E2(n, k) = Sum_{j=0..k} (-1)^(k-j)*W(n, j)*binomial(n - j, k - j).
The compositional inverse with respect to x of x - t*(exp(x) - 1) (see B. Drake):
T(n, k) = [t^k](n+1)!*(1-t)^(2*n+1)*[x^(n+1)] InverseSeries(x - t*(exp(x)-1), x).
AS1(n, k) = Sum_{j=0..n-k} binomial(j, n-2*k)*E2(n-k, j+1), where AS1(n, k) are the associated Stirling numbers of the first kind (A008306, A106828).
E2(n, k) = Sum_{j=0..n-k+1} (-1)^(n-k-j+1)*AS1(n+j, j)*binomial(n-j, n-k-j+1), for n >= 1.
AS2(n, k) = Sum_{j=0..n-k} binomial(j, n-2*k)*E2(n-k, n-k-j) for n >=1, where AS2(n, k) are the associated Stirling numbers of the second kind (A008299, A137375).
E2(n, k) = Sum_{j=0..k} (-1)^(k-j)*AS2(n + j, j)*binomial(n - j, k - j).

A163936 Triangle related to the o.g.f.s. of the right-hand columns of A130534 (E(x,m=1,n)).

Original entry on oeis.org

1, 1, 0, 2, 1, 0, 6, 8, 1, 0, 24, 58, 22, 1, 0, 120, 444, 328, 52, 1, 0, 720, 3708, 4400, 1452, 114, 1, 0, 5040, 33984, 58140, 32120, 5610, 240, 1, 0, 40320, 341136, 785304, 644020, 195800, 19950, 494, 1, 0, 362880, 3733920, 11026296, 12440064, 5765500, 1062500

Offset: 1

Johannes W. Meijer, Aug 13 2009

The asymptotic expansions of the higher-order exponential integral E(x,m=1,n) lead to triangle A130524, see A163931 for information on E(x,m,n). The o.g.f.s. of the right-hand columns of triangle A130534 have a nice structure: gf(p) = W1(z,p)/(1-z)^(2*p-1) with p = 1 for the first right-hand column, p = 2 for the second right-hand column, etc. The coefficients of the W1(z,p) polynomials lead to the triangle given above, n >= 1 and 1 <= m <= n. Our triangle is the same as A112007 with an extra right-hand column, see also the second Eulerian triangle A008517. The row sums of our triangle lead to A001147.
We observe that the row sums of the triangles A163936 (m=1), A163937 (m=2), A163938 (m=3) and A163939 (m=4) for z=1 lead to A001147, A001147 (minus a(0)), A001879 and A000457 which are the first four left-hand columns of the triangle of the Bessel coefficients A001497 or, if one wishes, the right-hand columns of A001498. We checked this phenomenon for a few more values of m and found that this pattern persists: m = 5 leads to A001880, m=6 to A001881, m=7 to A038121 and m=8 to A130563 which are the next left- (right-) hand columns of A001497 (A001498). An interesting phenomenon.
If one assumes the triangle not (1,1) based but (0,0) based, one has T(n, k) = E2(n, n-k), where E2(n, k) are the second-order Eulerian numbers A340556. - Peter Luschny, Feb 12 2021

			Triangle starts:
[ 1]      1;
[ 2]      1,       0;
[ 3]      2,       1,      0;
[ 4]      6,       8,      1,      0;
[ 5]     24,      58,     22,      1,      0;
[ 6]    120,     444,    328,     52,      1,     0;
[ 7]    720,    3708,   4400,   1452,    114,     1,   0;
[ 8]   5040,   33984,  58140,  32120,   5610,   240,   1,  0;
[ 9]  40320,  341136, 785304, 644020, 195800, 19950, 494,  1, 0;
The first few W1(z,p) polynomials are
W1(z,p=1) = 1/(1-z);
W1(z,p=2) = (1 + 0*z)/(1-z)^3;
W1(z,p=3) = (2 + 1*z + 0*z^2)/(1-z)^5;
W1(z,p=4) = (6 + 8*z + 1*z^2 + 0*z^3)/(1-z)^7.

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened

Row sums equal A001147.
A000142, A002538, A002539, A112008, A112485 are the first few left hand columns.
A000007, A000012, A005803(n+2), A004301, A006260 are the first few right hand columns.
Cf. A163931 (E(x,m,n)), A048994 (Stirling1) and A008517 (Euler).
Cf. A112007, A163937 (E(x,m=2,n)), A163938 (E(x,m=3,n)) and A163939 (E(x,m=4,n)).
Cf. A001497 (Bessel), A001498 (Bessel), A001147 (m=1), A001147 (m=2), A001879 (m=3) and A000457 (m=4), A001880 (m=5), A001881 (m=6) and A038121 (m=7).
Cf. A340556.

with(combinat): a := proc(n, m): add((-1)^(n+k+1)*binomial(2*n-1, k)*stirling1(m+n-k-1, m-k), k=0..m-1) end: seq(seq(a(n, m), m=1..n), n=1..9);  # Johannes W. Meijer, revised Nov 27 2012

Table[Sum[(-1)^(n + k + 1)*Binomial[2*n - 1, k]*StirlingS1[m + n - k - 1, m - k], {k, 0, m - 1}], {n, 1, 10}, {m, 1, n}] // Flatten (* G. C. Greubel, Aug 13 2017 *)

for(n=1,10, for(m=1,n, print1(sum(k=0,m-1,(-1)^(n+k+1)* binomial(2*n-1,k)*stirling(m+n-k-1,m-k, 1)), ", "))) \\ G. C. Greubel, Aug 13 2017

\\ assuming offset = 0:
E2poly(n,x) = if(n == 0, 1, x*(x-1)^(2*n)*deriv((1-x)^(1-2*n)*E2poly(n-1,x)));
{ for(n = 0, 9, print(Vec(E2poly(n,x)))) } \\ Peter Luschny, Feb 12 2021

a(n, m) = Sum_{k=0..(m-1)} (-1)^(n+k+1)*binomial(2*n-1,k)*Stirling1(m+n-k-1,m-k), for 1 <= m <= n.

Assuming offset = 0 the T(n, k) are the coefficients of recursively defined polynomials. T(n, k) = [x^k] x^n*E2poly(n, 1/x), where E2poly(n, x) = x*(x - 1)^(2*n)*d_{x}((1 - x)^(1 - 2*n)*E2poly(n - 1, x))) for n >= 1 and E2poly(0, x) = 1. - Peter Luschny, Feb 12 2021

A002539 Eulerian numbers of the second kind: <>.

Original entry on oeis.org

1, 22, 328, 4400, 58140, 785304, 11026296, 162186912, 2507481216, 40788301824, 697929436800, 12550904017920, 236908271543040, 4687098165573120, 97049168010017280, 2099830209402931200, 47405948832458496000, 1115089078488795648000, 27290469545695931904000, 694002594415741341696000

Offset: 0

N. J. A. Sloane , Simon Plouffe, Robert G. Wilson v, Mira Bernstein

Eulerian permutations of the multiset {1,1,2,2,...,n+3,n+3} with n ascents.Eulerian permutations have the restriction that for all m, all integers between the two copies of m are less than m. In particular, the two 1s are always next to each other.

The sequence gives the Eulerian numbers <<3,0>>, <<4,1>>, <<5,2>>, <<6,3>>, ... (and in particular the offset is 0).

			For instance, a(1) = 22 because among the 7!! = 105 permutations of {1,1,2,2,3,3,4,4} selected according to the definition of Eulerian numbers of the second kind, only 22 contain n = 1 descent, namely : 11223443, 11224433, 11233244, 11233442, 11244233, 11332244, 11334422, 11442233, 12213344, 12233144, 12233441, 12244133, 13312244, 13344122, 14412233, 22113344, 22331144, 22334411, 22441133, 33112244, 33441122, 44112233. - _Jean-François Alcover_, Mar 28 2011

Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Math., 2nd edition; Addison-Wesley, 1994, pp. 270-271.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=0..99
L. Carlitz, Some numbers related to the Stirling numbers of the first and second kind, Univ. Beograd Publ. Elektrotehn. Fak. Ser. Mat. Fiz., Numbers 544-576 (1976): 49-55. [Annotated scanned copy. The triangle is A008517.]
I. Gessel and R. P. Stanley, Stirling polynomials, J. Combin. Theory, A 24 (1978), 24-33.
O. J. Munch, Om potensproduktsummer [Norwegian, English summary], Nordisk Matematisk Tidskrift, 7 (1959), 5-19. [Annotated scanned copy]
O. J. Munch, Om potensproduktsummer [ Norwegian, English summary ], Nordisk Matematisk Tidskrift, 7 (1959), 5-19. There are errors in the last two rows of his table.

3rd diagonal of A008517, third column of A112007.

b[1]=1; b[2]=22; b[n_] := b[n] = ((n-1)*(n-1)!*n^3 - (n+2)*(n+3)*b[n-2]*n + (n*(2*n+5)-4)*b[n-1]) / (n-1); a[n_] := b[n+1]; Table[a[n], {n, 0, 19}] (* Jean-François Alcover, Mar 23 2011, updated Oct 12 2015 *)

{a=vector(30,n,1);a[2]=22;for(n=3,#a,a[n]=(n-1)!*n^3+((n*(2*n+5)-4)*a[n-1] - n*(n+2)*(n+3)*a[n-2])/(n-1));a} \\ Uses offet 1 for technical reasons. - M. F. Hasler, Sep 19 2015

a(n)= (n+5)*a(n-1) + (n+1)*A002538(n+1), n>=1, a(0)=1.
Recurrence: (n-1)*n^2*a(n) = (n-1)*(3*n^3 + 12*n^2 + 6*n + 1)*a(n-1) - (n+1)*(3*n^4 + 15*n^3 + 13*n^2 - 15*n - 4)*a(n-2) + n*(n+1)^3*(n+2)*(n+3)*a(n-3). - Vaclav Kotesovec, May 24 2014
a(n) ~ n! * n^5 * log(n) * (log(n)*(1/2+181/(24*n)) + gamma*(1+181/(12*n)) - 2 - 65/(3*n)), where gamma is the Euler-Mascheroni constant (A001620). - Vaclav Kotesovec, May 24 2014

Formulas adapted for offset 0 by Vaclav Kotesovec, May 24 2014

More terms from M. F. Hasler, Sep 19 2015

A220884 Triangle read by rows: row n gives coefficients of expansion of Product_{k=2..n} ((n+1-k)*x+k), starting with lowest power.

Original entry on oeis.org

1, 1, 2, 1, 6, 8, 2, 24, 58, 37, 6, 120, 444, 504, 204, 24, 720, 3708, 6388, 4553, 1318, 120, 5040, 33984, 81136, 87296, 44176, 9792, 720, 40320, 341136, 1064124, 1582236, 1203921, 463860, 82332, 5040, 362880, 3733920, 14602320, 28328480, 29724000, 17164320, 5270480, 773280, 40320, 3628800, 44339040, 210852936, 512539012, 700870638, 557061609, 255644668, 64621692, 8026416, 362880

Offset: 0

N. J. A. Sloane, Dec 29 2012

Related to Stirling numbers A008275, A008277.

			Triangle begins:
[1]
[1]
[2, 1]
[6, 8, 2]
[24, 58, 37, 6]
[120, 444, 504, 204, 24]
[720, 3708, 6388, 4553, 1318, 120]
[5040, 33984, 81136, 87296, 44176, 9792, 720]
...

Alois P. Heinz, Rows n = 0..141, flattened
Irfan Durmić, Alex Han, Pamela E. Harris, Rodrigo Ribeiro, and Mei Yin, Probabilistic Parking Functions, arXiv:2211.00536 [math.CO], 2022.
Jean-Christophe Novelli and Jean-Yves Thibon, Duplicial algebras and Lagrange inversion, arXiv preprint arXiv:1209.5959 [math.CO], 2012-2013.

Cf. A220883, A008275, A008277.
Row sums give A000272(n+1).
Columns k=0-1 give A000142, A002538(n-1).

T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(
         expand(mul((n+1-k)*x+k, k=2..n))):
seq(T(n), n=0..10);  # Alois P. Heinz, Nov 29 2015

row[n_] := CoefficientList[Product[((n+1-k)*x+k), {k, 2, n}], x]; Table[ row[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Feb 17 2016 *)

T(0,0)=1 prepended by Alois P. Heinz, Nov 29 2015

A288874 Row reversed version of triangle A201637 (second-order Eulerian triangle).

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 6, 8, 1, 0, 24, 58, 22, 1, 0, 120, 444, 328, 52, 1, 0, 720, 3708, 4400, 1452, 114, 1, 0, 5040, 33984, 58140, 32120, 5610, 240, 1, 0, 40320, 341136, 785304, 644020, 195800, 19950, 494, 1, 0, 362880, 3733920, 11026296, 12440064, 5765500, 1062500, 67260, 1004, 1, 0, 3628800, 44339040, 162186912, 238904904, 155357384, 44765000, 5326160, 218848, 2026, 1

Offset: 0

Wolfdieter Lang, Jul 20 2017

See A201637, and also A008517 (offset 1 for rows and columns).
The row polynomials of this triangle P(n, x) = Sum_{m=0..n} T(n, m)*x^m appear as numerator polynomials in the o.g.f.s for the diagonal sequences of triangle A132393 (|Stirling1| with offset 0 for rows and columns). See the comment and the P. Bala link there.
For similar triangles see also A112007 and A163936.

			The triangle T(n, m) begins:
n\m 0      1       2        3        4       5       6     7    8  9 ...
0:  1
1:  0      1
2:  0      2       1
3:  0      6       8        1
4:  0     24      58       22        1
5:  0    120     444      328       52       1
6:  0    720    3708     4400     1452     114       1
7:  0   5040   33984    58140    32120    5610     240     1
8:  0  40320  341136   785304   644020  195800   19950   494    1
9:  0 362880 3733920 11026296 12440064 5765500 1062500 67260 1004  1
...

Seiichi Manyama, Rows n = 0..139, flattened
Andrew Elvey Price, Alan D. Sokal, Phylogenetic trees, augmented perfect matchings, and a Thron-type continued fraction (T-fraction) for the Ward polynomials, arXiv:2001.01468 [math.CO], 2020.
Wikipedia, Eulerian numbers of the second kind

Cf. A201637, A008517, A112007, A163936.
Columns m = 0..5: A000007, A000142, A002538, A002539, A112008, A112485.
Diagonals d = 0..3: A000012, A005803, A004301, A006260.
T(2n,n) gives A290306.

T:= (n, k)-> combinat[eulerian2](n, n-k):
seq(seq(T(n, k), k=0..n), n=0..12);  # Alois P. Heinz, Jul 26 2017
# Using the e.g.f:
alias(W = LambertW): len := 10:
egf := (t - 1)*(1/(W(-exp(((t - 1)^2*x - 1)/t)/t) + 1) - 1):
ser := simplify(subs(W(-exp(-1/t)/t) = (-1/t), series(egf, x, len+1))):
seq(seq(n!*coeff(coeff(ser, x, n), t, k), k = 0..n), n = 0..len);  # Peter Luschny, Mar 13 2025

Table[Boole[n == 0] + Sum[(-1)^(n + k) * Binomial[2 n + 1, k] StirlingS1[2 n - m - k, n - m - k], {k, 0, n - m - 1}], {n, 0, 10}, {m, n, 0, -1}] // Flatten (* Michael De Vlieger, Jul 21 2017, after Jean-François Alcover at A201637 *)

T(n, m) = A201637(n, n-m), n >= m >= 0.
Recurrence: T(0, 0) = 1, T(n, -1) = 0, T(n, m) = 0 if n < m, (n-m+1)*T(n-1, m-1) + (n-1+m)*T(n-1, m), n >= 1, m = 0..n; from the A008517 recurrence.
T(0, 0) = 1, T(n, m) = Sum_{p = 0..m-1} (-1)^(n-p)*binomial(2*n+1, p)*A132393(n+m-p, m-p), n >= 1, m = 0..n; from a A008517 program.
T(n, k) = n! * [t^k][x^n] (t - 1)*(1/(W(-exp(((t - 1)^2*x - 1)/t)/t) + 1) - 1) where after expansion W(-exp(-1/t)/t) is substituted by (-1/t). [Inspired by a formula of Shamil Shakirov in A008517.] - Peter Luschny, Mar 13 2025

cp's OEIS Frontend

A047867 Erroneous version of A002538.

Views

Author

Keywords

Comments

Formula

A001286 Lah numbers: a(n) = (n-1)*n!/2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Maxima

PARI

Python

Sage

Formula

A008517 Second-order Eulerian triangle T(n,k), 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Sage

Formula

A112007 Coefficient triangle for polynomials used for o.g.f.s for unsigned Stirling1 diagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A288964 Number of key comparisons to sort all n! permutations of n elements by quicksort.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

SageMath

SageMath

Formula

A340556 E2(n, k), the second-order Eulerian numbers with E2(0, k) = δ_{0, k}. Triangle read by rows, E2(n, k) for 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple