This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A008517 Second-order Eulerian triangle T(n,k), 1 <= k <= n. 55
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 (list; table; graph; refs; listen; history; text; internal format)



Second-order Eulerian numbers <<n,k>> 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(T(k,m+1)*binomial(n+k-1+m,2*k),m=0..k-1) 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*diff(G(k-1,x),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[T(n,k)x^n/n!*y^k,{n>=1,1<=k<=n}] 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^(n-1)*x^n/n!,{n>=1}]. 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: (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


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

P. Bala, Diagonals of triangles with generating function exp(t*F(x)).

J. Fernando Barbero G., Jesús Salas, 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, 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.

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

D. Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions. arXiv:math/0501052v2 [math.CA], 2005.

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. - From T. Copeland, Jan 2 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.

M. Klazar, Twelve countings with rooted plane trees, European Journal of Combinatorics 18 (1997), 195-210; Addendum, 18 (1997), 739-740.

Paul Levande, Two New Interpretations of the Fishburn Numbers and their Refined Generating Functions, arXiv:1006.3013 [math.CO], 2010.

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, 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.

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.

C. D. Savage, 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.

L. M. Smiley, Completion of a rational function sequence of Carlitz, arXiv:0006106 [math.CO], 2000.

Eric Weisstein's World of Mathematics, Second-Order Eulerian Triangle

Wikipedia, Eulerian numbers of the second kind


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)

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. - Tom Copeland, Oct 03 2011

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


Triangle begins:


  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





The total number of trees is (2*t+1)^2 + t*(t+2) + t*(t+2) = 1 + 8*t + 6*t^2.


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


(PARI) {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 */

(PARI) {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(""))



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


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.

Sequence in context: A160641 A011244 A189966 * A142336 A193735 A114193

Adjacent sequences:  A008514 A008515 A008516 * A008518 A008519 A008520




N. J. A. Sloane


Exponents of P(4,t) corrected by Tom Copeland, May 19 2010



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 July 27 02:39 EDT 2017. Contains 289840 sequences.