cp's OEIS Frontend

A094262 Triangle read by rows: T(n,k) is the number of rooted trees with k nodes which are disjoint sets of labels with union {1..n}. If a node has an empty set of labels then it must have at least two children.

%I A094262 #65 Mar 28 2025 14:13:03
%S A094262 1,1,2,1,1,6,12,10,3,1,14,61,124,131,70,15,1,30,240,890,1830,2226,
%T A094262 1600,630,105,1,62,841,5060,16990,35216,47062,40796,22225,6930,945,1,
%U A094262 126,2772,25410,127953,401436,836976,1196532,1182195,795718,349020,90090,10395
%N A094262 Triangle read by rows: T(n,k) is the number of rooted trees with k nodes which are disjoint sets of labels with union {1..n}. If a node has an empty set of labels then it must have at least two children.
%C A094262 The original name for this sequence was "Triangle read by rows giving the coefficients of formulas generating each variety of S2(n,k) (Stirling numbers of 2nd kind). The p-th row (p>=1) contains T(i,p) for i=1 to 2*p-1, where T(i,p) satisfies Sum_{i=1..2*p-1} T(i,p) * C(n-p,i-1)".
%C A094262 The terms of the n-th diagonal sequence of the triangle of Stirling numbers of the second kind A008277, i.e., (Stirling2(N + n - 1,N)), N>=1, are given by a polynomial in N of degree 2*n - 2. This polynomial may be expressed as a linear combination of the falling factorial polynomials binomial(N - n,0), binomial(N - n,1), ... , binomial(N - n,2*n - 2). This table gives the coefficients in these expansions.
%C A094262 The formulas obtained are those for Stirling2(N+1,N) (A000217), Stirling2(N+2,N) (A001296), Stirling2(N+3,N) (A001297), Stirling2(N+4,N) (A001298), Stirling2(N+5,N) (A112494), Stirling2(N+6,N) (A144969) and so on.
%H A094262 Andrew Howroyd, <a href="/A094262/b094262.txt">Table of n, a(n) for n = 1..2500</a> (rows 1..50)
%H A094262 M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
%H A094262 Milton Abramowitz and Irene A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a> (with Formulas, Graphs and Mathematical Tables), U.S. Dept. of Commerce, National Bureau of Standards, Applied Math. Series 55, 1964, 1046 pages (9th Printing: November 1970) - Combinatorial Analysis, Table 24.4, Stirling Numbers of the Second Kind (author: Francis L. Miksa), p. 835.
%H A094262 J. Fernando Barbero G., Jesús Salas, Eduardo J. S. Villaseñor, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i3p37">Generalized Stirling permutations and forests: Higher-order Eulerian and Ward numbers</a>, Electronic Journal of Combinatorics 22(3) (2015), #P3.37.
%H A094262 M. Kazarian, <a href="http://arxiv.org/abs/0809.3263">KP hierarchy for Hodge integrals</a>, p. 2,  arxiv:0809.3263 [math.AG], 18 Sep 2008. [From _Tom Copeland_, Jun 12 2015]
%H A094262 F. R. McMorris and T. Zaslavsky, <a href="http://dx.doi.org/10.1016/0025-5564(81)90071-7">The number of cladistic characters</a>, Math. Biosciences, 54 (1981), 3-10.
%H A094262 F. R. McMorris and T. Zaslavsky, <a href="/A005172/a005172.pdf">The number of cladistic characters</a>, Math. Biosciences, 54 (1981), 3-10. [Annotated scanned copy]
%H A094262 Eric Weisstein's World of Mathematics, <a href="http://www.mathworld.wolfram.com/StirlingNumberoftheSecondKind.html">Stirling numbers of the 2nd kind</a>.
%F A094262 Apparently, a raising operator for bivariate polynomials P(n,u,z) having these coefficients is R = (u+z)^2 * z * d/dz with P(0,u,z) = z. E.g., R P(1,u,z) = R^2 P(0,u,z) = R^2 z = u^4 z + 6 u^3 z^2 + 12 u^2 z^3 + 10 u z^4 + 3 z^5 = P(2,u,z). See the Kazarian link. - _Tom Copeland_, Jun 12 2015
%F A094262 Reverse polynomials seem to be generated by 1 + exp[t*(x+1+z)^2*(1+z)d/dz]z evaluated at z = 0. - _Tom Copeland_, Jun 13 2015
%F A094262 From _Peter Bala_, Jun 14 2016: (Start)
%F A094262 T(n,k) = k*T(n,k) + 2*(k - 1)*T(n,k-1) + (k - 2)*T(n,k-2).
%F A094262 n-th diagonal of A008277: Stirling2(N + n - 1,N) = Sum_{k = 1..2*n - 1} T(n,k)*binomial(N - n,k - 1) for N = 1,2,3,....
%F A094262 Row polynomials R(n,z) = Sum_{k >= 1} k^(n+k-1)*( z/(1 + z)*exp(-z/(1 + z)) )^k/k!, n = 1,2,..., follows from the formula given in A008277 for the o.g.f.'s of the diagonals of the Stirling numbers of the second kind.
%F A094262 Consequently, R(n+1,z) = (1 + z)^2*z*d/dz(R(n,z)) for n >= 1 as conjectured above by Copeland.
%F A094262 R(n,z) = (1 + z)^n*P(n,z) where P(n,z) are the row polynomials of A134991.
%F A094262 R(n,z) = (1 + z)^(2*n+1)*B(n,z/(1 + z)), where B(n,z) are the row polynomials of the triangle of second-order Eulerian numbers A008517 (see Barbero et al., Section 6, equation 27). (End)
%F A094262 Based on the comment of Bala the row polynomials have the explicit form R(n, z) = (1+z)^(n+1)*Sum_{k=0..n}(z^k*Sum_{m=0..k}((-1)^(m+k)*binomial(n+k, n+m)* Stirling2(n+m,m))). - _Peter Luschny_, Jun 15 2016
%F A094262 E.g.f. G(x,y) satisfies G(x,y) = y*(exp(x)*exp(G(x,y)) - G(x,y) - 1). - _Andrew Howroyd_, Mar 28 2025
%e A094262 Row 5 contains 1,30,240,890,1830,2226,1600,630,105, so the formula generating Stirling2(n+4,n) numbers (A001298) will be the following: 1 + 30*(n-5) + 240*C(n-5,2) + 890*C(n-5,3) + 1830*C(n-5,4) + 2226*C(n-5,5) + 1600*C(n-5,6) + 630*C(n-5,7) + 105*C(n-5,8). For example, taking n = 9 gives Stirling2(13,9) = 359502.
%e A094262 Triangle starts:
%e A094262   1;
%e A094262   1,  2,   1;
%e A094262   1,  6,  12,  10,    3;
%e A094262   1, 14,  61, 124,  131,   70,   15;
%e A094262   1, 30, 240, 890, 1830, 2226, 1600, 630, 105;
%e A094262   ...
%e A094262 From _Peter Bala_, Jun 14 2016: (Start)
%e A094262 Connection with row polynomials of A134991:
%e A094262   R(2,z) = (1 + z)^2*z
%e A094262   R(3,z) = (1 + z)^2*(z + 3*z^2)
%e A094262   R(4,z) = (1 + z)^4*(z + 10*z^2 + 15*z^3)
%e A094262   R(5,z) = (1 + z)^5*(z + 25*z^2 + 105*z^3 + 105*z^4). (End)
%e A094262 From _Andrew Howroyd_, Mar 28 2025: (Start)
%e A094262 The T(3,3) = 12 trees up to relabeling have one of the following 3 forms:
%e A094262      {}         {1}        {1}
%e A094262     /  \       /   \        |
%e A094262   {1} {2,3}   {2}  {3}     {2}
%e A094262                             |
%e A094262                            {3}
%e A094262 (End)
%p A094262 row_poly := n -> (1+z)^(n+1)*add(z^k*add((-1)^(m+k)*binomial(n+k,n+m)*Stirling2(n+m,m), m=0..k), k=0..n): T_row := n -> seq(coeff(row_poly(n),z,j),j=1..2*n+1):
%p A094262 seq(T_row(n),n=0..6); # _Peter Luschny_, Jun 15 2016
%t A094262 Clear[T, q, u]; T[0] = q[1];T[n_] := Sum[m*(u^2*q[m] + 2*u*q[m+1] + q[m+2])*D[T[n-1], q[m]], {m, 1, 2*n+1}]; row[n_] := List @@ Expand[T[n-1]] /. {u -> 1, q[_] -> 1}; Table[row[n], {n, 1, 7}] // Flatten (* _Jean-François Alcover_, Jun 12 2015 *)
%o A094262 (PARI)
%o A094262 T(n)={my(g=serreverse(log(((1+1/y)*x+1)/exp(x + O(x*x^n))))); [Vecrev(p/y) | p<-Vec(serlaplace(g))]}
%o A094262 { my(A=T(5)); for(i=1, #A, print(A[i])) } \\ _Andrew Howroyd_, Mar 28 2025
%Y A094262 Row sums are A005172.
%Y A094262 Columns 1..4 are A000012, A000918, A005173, A005174, A005175.
%Y A094262 Cf. A008277, A000217, A001296, A001297, A001298, A008517, A134991, A112494, A144969.
%K A094262 nonn,tabf,easy
%O A094262 1,3
%A A094262 _André F. Labossière_, Jun 01 2004
%E A094262 Edited and Name changed by _Peter Bala_, Jun 16 2016
%E A094262 Name changed by _Andrew Howroyd_, Mar 28 2025