

A008517


Secondorder Eulerian triangle T(n,k), 1 <= k <= n.


63



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>> = 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,nk) = Sum_{m=0..k1} T(k,m+1)*binomial(n+k1+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 kth 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(k1,x) + (2k)*G(k1,x))/(1k*x), k >= 2, with G(1,x) = 1/(1x).  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(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_{n>=1, 1<=k<=n} [T(n,k)x^n/n!*y^k] 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>=1} n^(n1)*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 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
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)) ) / (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
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)
Hilbert series of the preWDVV ring, thus hvectors 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


REFERENCES

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


LINKS

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.
O. J. Munch, Om potensproduktsummer [Norwegian, English summary], Nordisk Matematisk Tidskrift, 7 (1959), 519. [Annotated scanned copy]
O. J. Munch, Om potensproduktsummer [ Norwegian, English summary ], Nordisk Matematisk Tidskrift, 7 (1959), 519.


FORMULA

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).
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
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..k} (1)^(ki) binomial(ni,ki) A134991(n,i), offsets 0.
P(n+1,t) = (1t)^(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 WFunction 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(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) of y = y(t;x) = (xt*(exp(x)1)) is 1/(1t)*y + t/(1t)^3*y^2/2! + (t+2*t^2)/(1t)^5*y^3/3! + (t+8*t^2+6*t^3)/(1t)^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: (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);
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);


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) = my(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))}; /* Michael Somos, 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(""))
(PARI) T(n, m) = sum(k=0, nm, (1)^(n+k)*binomial(2*n+1, k)*stirling(2*nmk+1, nmk+1, 1)); \\ Michel Marcus, Dec 07 2021
(Sage)
@CachedFunction
if n==1: return 1 if k==0 else 0


CROSSREFS

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.


KEYWORD



AUTHOR



STATUS

approved



