This site is supported by donations to The OEIS Foundation.



Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A008517 Second-order Eulerian triangle T(n,k), 1<=k<=n. 52
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 numerator polynomials appearing in the o.g.f. for the k-th diagonal 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

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

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 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, ... row polynomials of top 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


L. Carlitz, The coefficients in an asymptotic expansion. Proc. Amer. Math. Soc. 16 (1965) 248-252. - David Callan, Aug 27 2009

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

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

Martin Klazar, Twelve countings with rooted plane trees, Europ. J. Combinatorics, Vol. 18, 1997, 195-210.

O. J. Munch, Om potensproduktsummer [Norwegian, English summary], Nordisk Matematisk Tidskrift, 7 (1959), 5-19.

Carla D. Savage and Gopal Viswanathan, The 1/k-Eulerian Polynomials, Electr. J. Combinatorics, 19 (2012), #P9. - From N. J. A. Sloane, Feb 06 2013


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

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.

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

Jim Haglund and Mirko Visontai, Stable multivariate Eulerian polynomials and generalized Stirling permutations.

Paul Levande, Two New Interpretations of the Fishburn Numbers and their Refined Generating Functions, arXiv:1006.3013v1.

Shi-Mei Ma, Some combinatorial sequences associated with context-free grammars, arXiv:1208.3104v2 [math.CO]. - 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, 2013

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

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


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 to 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 to infin) k^(n+k) [t*exp(-t)]^k / k! for n>0; consequently, sum(k=1 to infin)(-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 to infin) 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) (x-t*(exp(x)-1))^(-1) = 1/(1-t)*x + t/(1-t)^3*x^2/2! + (t+2*t^2)/(1-t)^5*x^3/3! + (t+8*t^2+6*t^3)/(1-t)^7*x^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,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.



....|................. /.\............/.\..........

....|................ /...\........../...\.........






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) = local(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))}; /* 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.

Sequence in context: A160641 A011244 A189966 * A142336 A193735 A114193

Adjacent sequences:  A008514 A008515 A008516 * A008518 A008519 A008520




N. J. A. Sloane


More terms from Michael Somos, Oct 13, 2002

Corrected exponents of P(4,t) Tom Copeland, May 19 2010



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified April 20 13:52 EDT 2014. Contains 240806 sequences.