

A008517


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



OFFSET

1,3


COMMENTS

Secondorder 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,nk) = sum(T(k,m+1)*binomial(n+k1+m,2*k),m=0..k1) 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 kth diagonal of the Stirling2 triangle A048993.
The o.g.f. for column k satisfies the recurrence G(k,x)= x*(2*x*diff(G(k1,x),x) + (2k)*G(k1,x))/(1k*x),k>=2, with G(1,x)=1/(1x).  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(n1,k)+(2*nk)*T(n1,k1).
This triangle is in some sense generated by the differential equation y' = 12/(1+x+y). (This is the differential equation satisfied by the function defined implicitly as x+y=exp(xy).) 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)= (c1)/(c+1) and for n>1 a(n) = 2^n/n! (1+c)^(12n)( T(n,1)c  T(n,2)c^2 + T(n,3)c^3...+ (1)^(n1) 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/y2x)F_x + (y1)F_y, with (nonelementary) solution F(x,y) = (1y)/(1Phi(w)) where w = y*exp(x(y1)^2y) 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^(n1)*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 207208). 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 y1. The e.g.f. for the row sums A001147 is 1/sqrt(12*x) and the demonstration that F(x,1) = 1/sqrt(12*x) is interesting: two applications of l'Hopital's rule to lim_{y>1}F(x,y) yield F(x,1) = 1/(12x)*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)) ) / (1t) = WD(x*(1t), t/(1t)) / (1t)
where u = x*(1t)^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 2Eulerian polynomials by a simple transformation.
Note also apparently P(4,t) / (1t)^3 = Ward Poly(4, t/(1t)) = 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/(1t)^2)*(exp(x*(1t))x*(1t)1) )
= x  t*x^2/2!  t*(1t)*x^3/3!  t*(1t)^2*x^4/4!  t*(1t)^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/(1t))*(exp(x*(1t))1)), an e.g.f. in x for row polynomials in t of A008292, then the nth 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 hvectors of A134991.  Tom Copeland, Oct 03 2011


REFERENCES

L. Carlitz, The coefficients in an asymptotic expansion. Proc. Amer. Math. Soc. 16 (1965) 248252.  David Callan, Aug 27 2009
I. Gessel and R. P. Stanley, Stirling polynomials, J. Combin. Theory, A 24 (1978), 2433.
J. Ginsburg, Note on Stirling's Numbers. Amer. Math. Monthly 35 (1928), no. 2, 7780.  David Callan, Aug 27 2009
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, 2nd ed. AddisonWesley, Reading, MA, 1994, p. 270.
Martin Klazar, Twelve countings with rooted plane trees, Europ. J. Combinatorics, Vol. 18, 1997, 195210.
O. J. Munch, Om potensproduktsummer [Norwegian, English summary], Nordisk Matematisk Tidskrift, 7 (1959), 519.
Carla D. Savage and Gopal Viswanathan, The 1/kEulerian Polynomials, Electr. J. Combinatorics, 19 (2012), #P9.  From N. J. A. Sloane, Feb 06 2013


LINKS

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. 2448.
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.
ShiMei Ma, Some combinatorial sequences associated with contextfree 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, SecondOrder Eulerian Triangle


FORMULA

a(n,m) = sum(k=0..nm, (1)^(n+k)*binomial(2*n+1,k)*stirling1(2*nmk+1,nmk+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((1t)^2*xt) 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)^(ki) binomial(ni,ki) A134991(n,i), offsets 0.
P(n+1,t) = (1t)^(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 WFunction 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(j1,u) (z)^j / j! } where u=x*(1t)^2t , v=(1+u)/(1t), z= (t+u)/[(1+u)^2] and D(j1,u) are the polynomials of A042977. dA(x,t)/dx=(1t)/[1+u(1t)A(x,t)]=(1t)/{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) (xt*(exp(x)1))^(1) = 1/(1t)*x + t/(1t)^3*x^2/2! + (t+2*t^2)/(1t)^5*x^3/3! + (t+8*t^2+6*t^3)/(1t)^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: (1x)^(2*n+1) * Sum_{k>=0} k^(n+k) * exp(k*x) * x^k/k!.  Paul D. Hanna, Oct 31 2012


EXAMPLE

Triangle begins:
1;
1,2;
1,8,6;
1,22,58,24;
1,52,328,444,120; ...
Row 3: There are three plane increasing 0123 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.


MAPLE

with(combinat): A008517 := proc(n, m) local k: add((1)^(n+k)* binomial(2*n+1, k)* stirling1(2*nmk+1, nmk+1), k=0..nm) 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(n1, k)* (k+1) + A008517(n1, k1)*(2*nk1)) end: seq(print(seq(A008517(n, k), k=0..n1)), n=1..9);
#  Peter Luschny, Apr 20 2011


MATHEMATICA

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


PROG

(PARI) {T(n, k) = local(z); if( n<1, 0, z = 1 + O(x); for( k=1, n, z = 1 + intformal( z^2 * (z+y1))); n! * polcoeff( polcoeff(z, n), k))}; /* Oct 13 2002 */
(PARI) {T(n, k)=polcoeff((1x)^(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(""))
(Sage)
@CachedFunction
def A008517(n, k):
if n==1: return 1 if k==0 else 0
return A008517(n1, k)*(k+1)+A008517(n1, k1)*(2*nk1)
for n in (1..9): [A008517(n, k) for k in(0..n1)] # Peter Luschny, Oct 31 2012


CROSSREFS

Columns include A005803, A004301, A006260. Righthand 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


KEYWORD

nonn,tabl,nice,easy


AUTHOR

N. J. A. Sloane


EXTENSIONS

More terms from Michael Somos, Oct 13, 2002
Corrected exponents of P(4,t) Tom Copeland, May 19 2010


STATUS

approved



