|
%I #244 Jul 05 2023 17:05:04
%S 1,1,2,1,8,6,1,22,58,24,1,52,328,444,120,1,114,1452,4400,3708,720,1,
%T 240,5610,32120,58140,33984,5040,1,494,19950,195800,644020,785304,
%U 341136,40320,1,1004,67260,1062500,5765500,12440064,11026296,3733920,362880
%N Second-order Eulerian triangle T(n,k), 1 <= k <= n.
%C Second-order 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.
%C When seen as coefficients of polynomials with descending exponents, evaluations are in A000311 (x=2) and A001662 (x=-1).
%C 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|.
%C 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).
%C 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.
%C 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
%C 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
%C 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
%C 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
%C From _Tom Copeland_, Oct 12 2008; May 19 2010: (Start)
%C 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
%C exp(x*P(.,t)) = ( u + Tree(t*exp(u)) ) / (1-t) = WD(x*(1-t), t/(1-t)) / (1-t)
%C 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.
%C Note also apparently P(4,t) / (1-t)^3 = Ward Poly(4, t/(1-t)) = essentially an e.g.f. for A093500.
%C The compositional inverse of f(x,t) = exp(P(.,t)*x) about x=0 is
%C g(x,t) = ( x - (t/(1-t)^2)*(exp(x*(1-t))-x*(1-t)-1) )
%C = 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! - ... .
%C Can apply A134685 to these coefficients to generate f(x,t). (End)
%C 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
%C From _Tom Copeland_, Sep 04 2011: (Start)
%C 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.
%C 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)
%C The rows are the h-vectors of A134991. - _Tom Copeland_, Oct 03 2011
%C Hilbert series of the pre-WDVV ring, thus h-vectors of the Whitehouse simplicial complex (cf. Readdy, Table 1). - _Tom Copeland_, Sep 20 2014
%C Arises in Buckholtz's analysis of the error term in the series for exp(nz). - _N. J. A. Sloane_, Jul 05 2016
%D 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]
%H Vincenzo Librandi, <a href="/A008517/b008517.txt">Rows n = 1..50, flattened</a>
%H Peter Bala, <a href="/A112007/a112007_Bala.txt">Diagonals of triangles with generating function exp(t*F(x)).</a>
%H J. Fernando Barbero G., Jesús Salas, and Eduardo J. S. Villaseñor, <a href="http://arxiv.org/abs/1307.2010">Bivariate Generating Functions for a Class of Linear Recurrences. I. General Structure</a>, arXiv:1307.2010 [math.CO], 2013.
%H J. F. Barbero G., J. Salas and E. J. S. Villaseñor, <a href="http://arxiv.org/abs/1307.5624">Bivariate Generating Functions for a Class of Linear Recurrences. II. Applications</a>, arXiv preprint arXiv:1307.5624 [math.CO], 2013.
%H J. Fernando Barbero G., Jesús Salas, and Eduardo J. S. Villaseñor, <a href="https://doi.org/10.37236/4814">Generalized Stirling permutations and forests: Higher-order Eulerian and Ward numbers</a>, Electronic Journal of Combinatorics 22(3) (2015), #P3.37.
%H F. Bergeron, Ph. Flajolet and B. Salvy, <a href="http://algo.inria.fr/flajolet/Publications/BeFlSa92.pdf">Varieties of Increasing Trees</a>, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer (1992), pp. 24-48.
%H J. D. Buckholtz, <a href="http://dx.doi.org/10.1090/S0002-9939-1963-0151770-9">Concerning an approximation of Copson</a>, Proc. Amer. Math. Soc., 14 (1963), 564-568.
%H Naiomi T. Cameron and Kendra Killpatrick, <a href="https://arxiv.org/abs/1902.09021">Statistics on Linear Chord Diagrams</a>, arXiv:1902.09021 [math.CO], 2019.
%H L. Carlitz, <a href="http://dx.doi.org/10.1090/S0002-9939-1965-0172814-6">The coefficients in an asymptotic expansion</a>, Proc. Amer. Math. Soc. 16 (1965) 248-252.
%H L. Carlitz, <a href="/A002538/a002538.pdf">Some numbers related to the Stirling numbers of the first and second kind</a>, Univ. Beograd Publ. Elektrotehn. Fak. Ser. Mat. Fiz., Numbers 544-576 (1976): 49-55. [Annotated scanned copy. The triangle is A008517.]
%H T. Copeland, <a href="http://tcjpn.wordpress.com/2015/12/21/generators-inversion-and-matrix-binomial-and-integral-transforms/">Generators, Inversion, and Matrix, Binomial, and Integral Transforms</a>
%H Ming-Jian Ding and Jiang Zeng, <a href="https://arxiv.org/abs/2307.00566">Proof of an explicit formula for a series from Ramanujan's Notebooks via tree functions</a>, arXiv:2307.00566 [math.CO], 2023.
%H D. Dominici, <a href="http://arxiv.org/abs/math/0501052">Nested derivatives: A simple method for computing series expansions of inverse functions.</a> arXiv:math/0501052v2 [math.CA], 2005.
%H Sen-Peng Eu, Tung-Shan Fu, and Yeh-Jong Pan, <a href="https://doi.org/10.1016/j.ejc.2013.05.001">A refined sign-balance of simsun permutations</a>, Eur. J. Comb. 36 (2014) 97-109
%H W. Gautschi, <a href="http://nvlpubs.nist.gov/nistpubs/jres/62/jresv62n3p123_A1b.pdf">Exponential integral ... for large values of n</a>, Jrn. of Rsch. of the National Bureau of Standards, Vol. 62, No. 3, March 1959, Rsch. paper 2941. - _Tom Copeland_, Jan 02 2016
%H I. Gessel and R. P. Stanley, <a href="https://doi.org/10.1016/0097-3165(78)90042-0">Stirling polynomials</a>, J. Combin. Theory, A 24 (1978), 24-33.
%H J. Ginsburg, <a href="http://www.jstor.org/stable/2299462">Note on Stirling's Numbers</a>, Amer. Math. Monthly 35 (1928), no. 2, 77-80. - _David Callan_, Aug 27 2009
%H Jim Haglund and Mirko Visontai, <a href="http://hans.math.upenn.edu/~jhaglund/preprints/es-final.pdf">Stable multivariate Eulerian polynomials and generalized Stirling permutations</a>, European Journal of Combinatorics, Volume 33, Issue 4, May 2012, pp. 477-487.
%H M. Klazar, <a href="http://dx.doi.org/10.1006/eujc.1995.0095">Twelve countings with rooted plane trees</a>, European Journal of Combinatorics 18 (1997), 195-210; Addendum, 18 (1997), 739-740.
%H Dmitry V. Kruchinin and Vladimir V. Kruchinin, <a href="https://arxiv.org/abs/1802.09003">A generating function for the Euler numbers of the second kind and its application</a>, arXiv:1802.09003 [math.CO], 2018.
%H Paul Levande, <a href="http://arxiv.org/abs/1006.3013">Two New Interpretations of the Fishburn Numbers and their Refined Generating Functions</a>, arXiv:1006.3013 [math.CO], 2010.
%H Peter Luschny, <a href="http://luschny.de/math/oeis/A340556.html">Second-order Eulerian numbers</a>, A companion to A340556, Feb 2021.
%H Shi-Mei Ma, <a href="http://arxiv.org/abs/1208.3104">Some combinatorial sequences associated with context-free grammars</a>, arXiv:1208.3104v2 [math.CO], 2012. - From _N. J. A. Sloane_, Aug 21 2012
%H S.-M. Ma, T. Mansour, and M. Schork. <a href="http://arxiv.org/abs/1308.0169">Normal ordering problem and the extensions of the Stirling grammar</a>, arXiv preprint arXiv:1308.0169 [math.CO], 2013.
%H S.-M. Ma, T. Mansour, <a href="http://arxiv.org/abs/1409.6525">The 1/k-Eulerian polynomials and k-Stirling permutations</a>, arXiv preprint arXiv:1409.6525 [math.CO], 2014.
%H O. J. Munch, <a href="/A000460/a000460.pdf">Om potensproduktsummer</a> [Norwegian, English summary], Nordisk Matematisk Tidskrift, 7 (1959), 5-19. [Annotated scanned copy]
%H O. J. Munch, <a href="http://www.jstor.org/stable/24524919">Om potensproduktsummer</a> [ Norwegian, English summary ], Nordisk Matematisk Tidskrift, 7 (1959), 5-19.
%H Andrew Elvey Price and Alan D. Sokal, <a href="https://arxiv.org/abs/2001.01468">Phylogenetic trees, augmented perfect matchings, and a Thron-type continued fraction (T-fraction) for the Ward polynomials</a>, arXiv:2001.01468 [math.CO], 2020.
%H M. A. Readdy, <a href="http://www.ms.uky.edu/~readdy/Papers/pre_WDVV.pdf">The pre-WDVV ring of physics and its topology</a>, preprint 2002, The Ramanujan Journal, October 2005, Volume 10, Issue 2, pp 269-281.
%H Grzegorz Rzadkowski and M Urlinska, <a href="http://arxiv.org/abs/1612.06635">A Generalization of the Eulerian Numbers</a>, arXiv preprint arXiv:1612.06635, 2016
%H C. D. Savage and G. Viswanathan, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i1p9">The 1/k-Eulerian polynomials</a>, Elec. J. of Comb., Vol. 19, Issue 1, #P9 (2012). - From _N. J. A. Sloane_, Feb 06 2013
%H M. D. Schmidt, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Schmidt/multifact.html">Generalized j-Factorial Functions, Polynomials, and Applications </a>, J. Int. Seq. 13 (2010), 10.6.7, Section 5.1.
%H L. M. Smiley, <a href="https://arxiv.org/abs/math/0006106">Completion of a rational function sequence of Carlitz</a>, arXiv:0006106 [math.CO], 2000.
%H M. Z. Spivey, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Spivey/spivey31.html">On Solutions to a General Combinatorial Recurrence</a>, J. Int. Seq. 14 (2011) # 11.9.7.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Second-OrderEulerianTriangle.html">Second-Order Eulerian Triangle</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Eulerian_number#Eulerian_numbers_of_the_second_kind">Eulerian numbers of the second kind</a>
%F 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).
%F 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
%F From _Peter Bala_, Sep 29 2011: (Start)
%F 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.
%F 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.
%F 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)
%F From _Tom Copeland_, Oct 03 2011: (Start)
%F a(n,k) = Sum_{i=0..k} (-1)^(k-i) binomial(n-i,k-i) A134991(n,i), offsets 0.
%F 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)
%F 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
%F 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
%F 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
%F 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
%e Triangle begins:
%e 1;
%e 1, 2;
%e 1, 8, 6;
%e 1, 22, 58, 24;
%e 1, 52, 328, 444, 120; ...
%e 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.
%e .
%e 1o (2*t+1) 1o t*(t+2) 1o t*(t+2)
%e | / \ / \
%e | / \ / \
%e 2o (2*t+1) 2o 3o 3o 2o
%e |
%e |
%e 3o
%e .
%e The total number of trees is (2*t+1)^2 + t*(t+2) + t*(t+2) = 1 + 8*t + 6*t^2.
%p 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);
%p # _Johannes W. Meijer_, Oct 16 2009, revised Nov 22 2012
%p 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);
%p # _Peter Luschny_, Apr 20 2011
%t 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_ *)
%o (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 */
%o (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
%o for(n=1,10,for(k=1,n,print1(T(n,k),", "));print(""))
%o (PARI) 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
%o (Sage)
%o @CachedFunction
%o def A008517(n, k):
%o if n==1: return 1 if k==0 else 0
%o return A008517(n-1,k)*(k+1)+A008517(n-1,k-1)*(2*n-k-1)
%o for n in (1..9): [A008517(n, k) for k in(0..n-1)] # _Peter Luschny_, Oct 31 2012
%Y Columns include A005803, A004301, A006260.
%Y Right-hand columns include A000142, A002538, A002539.
%Y Row sums are A001147.
%Y 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.
%K nonn,tabl,nice,easy
%O 1,3
%A _N. J. A. Sloane_
|
