A005172 -id:A005172 - 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.

1, 1, 2, 1, 1, 6, 12, 10, 3, 1, 14, 61, 124, 131, 70, 15, 1, 30, 240, 890, 1830, 2226, 1600, 630, 105, 1, 62, 841, 5060, 16990, 35216, 47062, 40796, 22225, 6930, 945, 1, 126, 2772, 25410, 127953, 401436, 836976, 1196532, 1182195, 795718, 349020, 90090, 10395

Offset: 1

André F. Labossière, Jun 01 2004

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

			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.
Triangle starts:
  1;
  1,  2,   1;
  1,  6,  12,  10,    3;
  1, 14,  61, 124,  131,   70,   15;
  1, 30, 240, 890, 1830, 2226, 1600, 630, 105;
  ...
From _Peter Bala_, Jun 14 2016: (Start)
Connection with row polynomials of A134991:
  R(2,z) = (1 + z)^2*z
  R(3,z) = (1 + z)^2*(z + 3*z^2)
  R(4,z) = (1 + z)^4*(z + 10*z^2 + 15*z^3)
  R(5,z) = (1 + z)^5*(z + 25*z^2 + 105*z^3 + 105*z^4). (End)
From _Andrew Howroyd_, Mar 28 2025: (Start)
The T(3,3) = 12 trees up to relabeling have one of the following 3 forms:
     {}         {1}        {1}
    /  \       /   \        |
  {1} {2,3}   {2}  {3}     {2}
                            |
                           {3}
(End)

Andrew Howroyd, Table of n, a(n) for n = 1..2500 (rows 1..50)
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Milton Abramowitz and Irene A. Stegun, eds., Handbook of Mathematical Functions (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.
J. Fernando Barbero G., Jesús Salas, Eduardo J. S. Villaseñor, Generalized Stirling permutations and forests: Higher-order Eulerian and Ward numbers, Electronic Journal of Combinatorics 22(3) (2015), #P3.37.
M. Kazarian, KP hierarchy for Hodge integrals, p. 2, arxiv:0809.3263 [math.AG], 18 Sep 2008. [From _Tom Copeland_, Jun 12 2015]
F. R. McMorris and T. Zaslavsky, The number of cladistic characters, Math. Biosciences, 54 (1981), 3-10.
F. R. McMorris and T. Zaslavsky, The number of cladistic characters, Math. Biosciences, 54 (1981), 3-10. [Annotated scanned copy]
Eric Weisstein's World of Mathematics, Stirling numbers of the 2nd kind.

Row sums are A005172.
Columns 1..4 are A000012, A000918, A005173, A005174, A005175.
Cf. A008277, A000217, A001296, A001297, A001298, A008517, A134991, A112494, A144969.

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):
seq(T_row(n),n=0..6); # Peter Luschny, Jun 15 2016

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

T(n)={my(g=serreverse(log(((1+1/y)*x+1)/exp(x + O(x*x^n))))); [Vecrev(p/y) | p<-Vec(serlaplace(g))]}
{ my(A=T(5)); for(i=1, #A, print(A[i])) } \\ Andrew Howroyd, Mar 28 2025

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
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
From Peter Bala, Jun 14 2016: (Start)
T(n,k) = k*T(n,k) + 2*(k - 1)*T(n,k-1) + (k - 2)*T(n,k-2).
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,....
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.
Consequently, R(n+1,z) = (1 + z)^2*z*d/dz(R(n,z)) for n >= 1 as conjectured above by Copeland.
R(n,z) = (1 + z)^n*P(n,z) where P(n,z) are the row polynomials of A134991.
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)
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
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

Edited and Name changed by Peter Bala, Jun 16 2016

Name changed by Andrew Howroyd, Mar 28 2025

A005264 Number of labeled rooted Greg trees with n nodes.

Original entry on oeis.org

1, 3, 22, 262, 4336, 91984, 2381408, 72800928, 2566606784, 102515201984, 4575271116032, 225649908491264, 12187240730230528, 715392567595403520, 45349581052869924352, 3087516727770990992896, 224691760916830871873536

Offset: 1

N. J. A. Sloane

A rooted Greg tree can be described as a rooted tree with 2-colored nodes where only the black nodes are counted and labeled and the white nodes have at least 2 children. - Christian G. Bower, Nov 15 1999

			G.f. = x + 3*x^2 + 22*x^3 + 262*x^4 + 4336*x^5 + 91984*x^6 + 2381408*x^7 + ...

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Robert Israel, Table of n, a(n) for n = 1..358
D. Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions. arXiv:math/0501052v2 [math.CA], 2005.
J. Felsenstein, The number of evolutionary trees, Systematic Zoology, 27 (1978), 27-33.
J. Felsenstein, The number of evolutionary trees, Systematic Zoology, 27 (1978), 27-33. (Annotated scanned copy)
C. Flight, How many stemmata?, Manuscripta, 34 (1990), 122-128.
C. Flight, How many stemmata?, Manuscripta, 34 (1990), 122-128. (Annotated scanned copy)
C. Flight, Letter to N. J. A. Sloane, Nov 1990
L. R. Foulds and R. W. Robinson, Determining the asymptotic number of phylogenetic trees, pp. 110-126 of Combinatorial Mathematics VII (Newcastle, August 1979), ed. R. W. Robinson, G. W. Southern and W. D. Wallis. Lect. Notes in Math., 829. Springer, 1980.
L. R. Foulds & R. W. Robinson, Determining the asymptotic number of phylogenetic trees, Lecture Notes in Math., 829 (1980), 110-126. (Annotated scanned copy)
Armin Hoenen, Steffen Eger, and Ralf Gehrke, How Many Stemmata with Root Degree k?, Proceedings of the 15th Meeting on the Mathematics of Language, pp. 11-21, 2017.
D. J. Jeffrey, G. A. Kalugin, and N. Murdoch, Lagrange inversion and Lambert W, Preprint, 2015 17th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC).
M. Josuat-Vergès, Derivatives of the tree function, arXiv preprint arXiv:1310.7531 [math.CO], 2013.
Vladimir Kruchinin, The method for obtaining expressions for coefficients of reverse generating functions, arXiv:1211.3244 [math.CO], 2012.
Paul Laubie, Combinatorics of pre-Lie products sharing a Lie bracket, arXiv:2309.05552 [math.QA], 2023. See pp. 1, 5.
N. J. A. Sloane, Transforms
N. S. Wedd, Letter to N. J. A. Sloane, N.D.
Index entries for reversions of series
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Inverse Stirling transform of A005172 (hence corrected and extended). - John W. Layman

Cf. A005263, A048159, A048160, A052300, A052301, A052302, A052303, A157142.

T := proc(n,k) option remember; if k=0 and (n=0 or n=1) then return(1) fi; if k<0 or k>n then return(0) fi;
(n-1)*T(n-1,k-1)+(3*n-k-4)*T(n-1,k)-(k+1)*T(n-1,k+1) end:
A005264 := proc(n) add(T(n,k)*(-1)^k*2^(n-k-1), k=0..n-1) end;
seq(A005264(n),n=1..17); # Peter Luschny, Nov 10 2012

max = 17; f[x_] := -1/2 - ProductLog[-E^(-1/2)*(x + 1)/2]; Rest[ CoefficientList[ Series[ f[x], {x, 0, max}], x]*Range[0, max]!] (* Jean-François Alcover, May 23 2012, after Peter Bala *)
a[ n_] := If[ n < 1, 0, n! SeriesCoefficient[ InverseSeries[ Series[ Exp[-x] (1 + 2 x) - 1, {x, 0, n}]], n]]; (* Michael Somos, Jun 07 2012 *)

a(n):=if n=1 then 1 else sum((n+k-1)!*sum(1/(k-j)!*sum(1/(l!*(j-l)!)*sum(((-1)^(i+l)*l^i*binomial(l,n+j-i-1)*2^(n+j-i-1))/i!,i,0,n+j-1),l,1,j),j,1,k),k,1,n-1); /* Vladimir Kruchinin, May 04 2012 */

{a(n) = local(A); if( n<1, 0, for( k= 1, n, A += x * O(x^k); A = truncate( (1 + x) * exp(A) - 1 - A) ); n! * polcoeff( A, n))}; /* Michael Somos, Apr 02 2007 */

{a(n) = if( n<1, 0, n! * polcoeff( serreverse( exp( -x + x * O(x^n) ) * (1 + 2*x) - 1), n))}; /* Michael Somos, Mar 26 2011 */

@CachedFunction
def T(n,k):
    if k==0 and (n==0 or n==1): return 1
    if k<0 or k>n: return 0
    return (n-1)*T(n-1,k-1)+(3*n-k-4)*T(n-1,k)-(k+1)*T(n-1,k+1)
A005264 = lambda n: add(T(n,k)*(-1)^k*2^(n-k-1) for k in (0..n-1))
[A005264(n) for n in (1..17)]  # Peter Luschny, Nov 10 2012

Exponential reversion of A157142 with offset 1. - Michael Somos, Mar 26 2011
The REVEGF transform of the odd numbers [1,3,5,7,9,11,...] is  [1, -3, 22, -262, 4336, -91984, 2381408, ...] - N. J. A. Sloane, May 26 2017
E.g.f. A(x) = y satisfies y' = (1 + 2*y) / ((1 - 2*y) * (1 + x)). - Michael Somos, Mar 26 2011
E.g.f. A(x) satisfies (1 + x) * exp(A(x)) = 1 + 2 * A(x).
From Peter Bala, Sep 08 2011: (Start)
A(x) satisfies the separable differential equation A'(x) = exp(A(x))/(1-2*A(x)) with A(0) = 0. Thus the inverse function A^-1(x) = int {t = 0..x} (1-2*t)/exp(t) = exp(-x)*(2*x+1)-1 = x-3*x^2/2!+5*x^3/3!-7*x^4/4!+.... A(x) = -1/2-LambertW(-exp(-1/2)*(x+1)/2).
The expansion of A(x) can be found by inverting the above integral using the method of [Dominici, Theorem 4.1] to arrive at the result a(n) = D^(n-1)(1) evaluated at x = 0, where D denotes the operator g(x) -> d/dx(exp(x)/(1-2*x)*g(x)). Compare with [Dominici, Example 9].
(End)
a(n)=sum(k=1..n-1, (n+k-1)!*sum(j=1..k, 1/(k-j)!*sum(l=1..j,  1/(l!*(j-l)!)* sum(i=0..n+j-1, ((-1)^(i+l)*l^i*binomial(l,n+j-i-1)*2^(n+j-i-1))/i!)))), n>1, a(1)=1. - Vladimir Kruchinin, May 04 2012
Let T(n,k) = 1 if k=0 and (n=0 or n=1); T(n,k) = 0 if k<0 or k>n; and otherwise T(n,k) = (n-1)*T(n-1,k-1)+(3*n-k-4)*T(n-1,k)-(k+1)*T(n-1,k+1). Define polynomials p(n,w) = w^n*sum_{k=0..n-1}(T(n,k)*w^k)/(1+w)^(2*n-1), then a(n) = (-1)^n*p(n,-1/2). - Peter Luschny, Nov 10 2012
a(n) ~ n^(n-1) / (sqrt(2) * exp(n/2) * (2-exp(1/2))^(n-1/2)). - Vaclav Kotesovec, Jul 09 2013
E.g.f.: -W(-(1+x)*exp(-1/2)/2)-1/2 where W is the Lambert W function. - Robert Israel, Mar 28 2017

A005263 Number of labeled Greg trees.

Original entry on oeis.org

1, 1, 1, 4, 32, 396, 6692, 143816, 3756104, 115553024, 4093236352, 164098040448, 7345463787136, 363154251536896, 19653476190481408, 1155636468524067328, 73364615077878838784, 5001199614295920565248, 364363128390631094137856

Offset: 0

N. J. A. Sloane

A Greg tree can be described as a tree with 2-colored nodes where only the black nodes are counted and labeled and the white nodes are of degree at least 3.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Robert Israel, Table of n, a(n) for n = 0..359
C. Flight, How many stemmata?, Manuscripta, 34 (1990), 122-128.
C. Flight, How many stemmata?, Manuscripta, 34 (1990), 122-128. (Annotated scanned copy)
C. Flight, Letter to N. J. A. Sloane, Nov 1990
L. R. Foulds & R. W. Robinson, Determining the asymptotic number of phylogenetic trees, Lecture Notes in Math., 829 (1980), 110-126. (Annotated scanned copy)
V. Kurauskas, On graphs containing few disjoint excluded minors. Asymptotic number and structure of graphs containing few disjoint minors K_4, arXiv preprint arXiv:1504.08107 [math.CO], V1, Apr 30, 2015; V2, Jul 14 2019.
Dimitris Papamichail, Angela Huang, Edward Kennedy, Jan-Lucas Ott, Andrew Miller, Georgios Papamichail, Most Compact Parsimonious Trees, arXiv preprint arXiv:1603.03315 [cs.DS], 2016.
Index entries for sequences related to trees

Cf. A005264, A005640, A048159, A048160, A052300-A052303.

E:= 1/4 -LambertW(-(1+x)*exp(-1/2)/2)^2 - 2*LambertW(-(1+x)*exp(-1/2)/2):
S:= series(E,x,21):
seq(coeff(S,x,j)*j!, j=0..20); # Robert Israel, Mar 28 2017

max = 18; b[x] := -1/2 - ProductLog[-Exp[-1/2]*(x+1)/2]; f[x_] := Sum[c[k]*x^k, {k, 0, max}]; sol = SolveAlways[ Normal[ Series[f[x] - (1 + b[x] - b[x]^2), {x, 0, max}]] == 0, x]; First[Table[c[k], {k, 0, max}] /. sol]*Range[0, max]! (* Jean-François Alcover, May 21 2012, from e.g.f. *)
a[ n_] := If[ n < 1, Boole[n == 0], n! SeriesCoefficient[ With[ {B =      InverseSeries[ Series[ Exp[-x] (1 + 2 x) - 1, {x, 0, n}]]}, B - B^2], n]] (* Michael Somos, Jun 07 2012 *)

{a(n) = local(A); if( n<1, n==0, for( k=1, n, A += x * O(x^k); A = truncate( (1 + x) * exp(A) - 1 - A) ); A += x * O(x^n); A -= A^2; n! * polcoeff( A, n))} /* Michael Somos, Apr 02 2007 */

E.g.f.: 1 + B(x) - B(x)^2 where B(x) is e.g.f. of A005264.
a(n) ~ n^(n-2) / (sqrt(2) * exp(n/2) * (2-exp(1/2))^(n-3/2)). - Vaclav Kotesovec, Jul 09 2013
E.g.f.: 1/4 - W(-(1+x)*exp(-1/2)/2)^2 - 2*W(-(1+x)*exp(-1/2)/2) where W is the Lambert W function. - Robert Israel, Mar 28 2017

More terms, formula and comment from Christian G. Bower, Nov 15 1999

A005640 Number of phylogenetic trees with n labels.

Original entry on oeis.org

1, 1, 2, 8, 64, 832, 15104, 352256, 10037248, 337936384, 13126565888, 577818263552, 28425821618176, 1545553369366528, 92034646352592896, 5956917762776367104, 416397789920380321792, 31262503202358260924416, 2508985620606225641111552, 214348807882902869374926848, 19422044917978876510600167424

Offset: 0

N. J. A. Sloane

Each node of the tree is a subset of the labeled set {1,...,n}. If the subset node is empty, it must have degree at least 3.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.26.

Vincenzo Librandi, Table of n, a(n) for n = 0..100
L. R. Foulds and R. W. Robinson, Determining the asymptotic number of phylogenetic trees, pp. 110-126 of Combinatorial Mathematics VII (Newcastle, August 1979), ed. R. W. Robinson, G. W. Southern and W. D. Wallis. Lecture Notes in Math., 829 (1980), 110-126. (Annotated scanned copy)
J. P. Hayes, Enumeration of fanout-free Boolean functions, J. ACM, 23 (1976), 700-709.
K. L. Kodandapani and S. C. Seth, On combinational networks with restricted fan-out, IEEE Trans. Computers, 27 (1978), 309-318. (Annotated scanned copy)
N. J. A. Sloane, Transforms
Index entries for sequences related to trees

Cf. A000311, A005172, A005263, A006351.

a[n_ /; n > 2] := 2^(n-1)*(n-2)!*Sum[ Binomial[n+k-2, n-2]*Sum[ (-1)^j*Binomial[k, j]*Sum[ ((-1)^l*2^(j-l)*Binomial[j, l]*(j-l)!*StirlingS1[n+j-l-2, j-l])/(n+j-l-2)!, {l, 0, j}], {j, 1, k}], {k, 1, n-2}]; a[0] = a[1] = 1; a[2] = 2; Table[a[n], {n, 0, 17}] (* Jean-François Alcover, Apr 10 2012, after Vladimir Kruchinin *)

STIRLING transform of A005263.
E.g.f.: 1+B(x)-B(x)^2 where B(x) is e.g.f. of A005172.
For n >= 2, a(n) = 2^n*A006351(n) = 2^(n+1)*A000311(n).

More terms, formula and comment from Christian G. Bower, Nov 15 1999

A225171 Triangle read by rows: T(n,k), 1 <= k <= n, is the number of non-degenerate fanout-free Boolean functions of n variables having AND rank k.

Original entry on oeis.org

2, 4, 4, 32, 24, 8, 416, 304, 96, 16, 7552, 5440, 1760, 320, 32, 176128, 125824, 41280, 8000, 960, 64, 5018624, 3566080, 1180928, 237440, 31360, 2688, 128, 168968192, 119614464, 39875584, 8212736, 1146880, 111104, 7168, 256, 6563282944, 4633387008, 1552320512, 325183488, 47104512, 4902912, 365568, 18432, 512

Offset: 1

N. J. A. Sloane, Apr 30 2013

Also the Bell transform of A225170. For the definition of the Bell transform see A264428. - Peter Luschny, Jan 29 2016

			Triangle begins
2,
4,4,
32,24,8,
416,304,96,16,
7552,5440,1760,320,32,
176128,125824,41280,8000,960,64,
5018624,3566080,1180928,237440,31360,2688,128,
168968192,119614464,39875584,8212736,1146880,111104,7168,256,
...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)
J. P. Hayes, Enumeration of fanout-free Boolean functions, J. ACM, 23 (1976), 700-709.
Index entries for sequences related to Boolean functions

Columns give A225170 (or A005172), A005756, A224767, A224768.

Row sums are A224766.

# Function BellMatrix defined in A264428.
BellMatrix(n -> `if`(n=0,2,add(combinat:-eulerian2(n, k)*2^(2*n-k), k=0..n)), 9); # Peter Luschny, Jan 29 2016

BellMatrix[f_Function, len_] := With[{t = Array[f, len, 0]}, Table[BellY[n, k, t], {n, 0, len - 1}, {k, 0, len - 1}]];
rows = 12;
M = BellMatrix[If[# == 0, 2, Sum[(#+k)!*Sum[(-1)^j/(k-j)!*Sum[(-1)^i*2^(# - i + j)*StirlingS1[# - i + j, j - i]/((# - i + j)!*i!), {i, 0, j}], {j, 1, k}], {k, 1, #}]]&, rows];
Table[M[[n, k]], {n, 2, rows}, {k, 2, n}] // Flatten (* Jean-François Alcover, Jun 24 2018, after Peter Luschny *)

T(n) = { my(g=serreverse((1 + 2*x - exp(x + O(x*x^n)))/2)); [Vecrev(p/y) | p<-Vec(serlaplace(exp(y*g)-1))] }
{ my(A=T(8)); for(i=1, #A, print(A[i])) } \\ Andrew Howroyd, Mar 28 2025

Hayes (1976, Theorem 3) gives a recurrence.

a(46) onwards from Andrew Howroyd, Mar 28 2025

A224766 Number of non-degenerate fanout-free Boolean functions of n variables using And, Or and Not gates.

Original entry on oeis.org

2, 2, 8, 64, 832, 15104, 352256, 10037248, 337936384, 13126565888, 577818263552, 28425821618176, 1545553369366528, 92034646352592896, 5956917762776367104, 416397789920380321792, 31262503202358260924416, 2508985620606225641111552, 214348807882902869374926848

Offset: 0

N. J. A. Sloane, Apr 30 2013

nonn

Apart from initial term and offset, same as A005640, which is the main entry for this sequence.

J. P. Hayes, Enumeration of fanout-free Boolean functions, J. ACM, 23 (1976), 700-709.

Andrew Howroyd, Table of n, a(n) for n = 0..200

Row sums of A225171.

Cf. A005172, A005640, A005736, A005737, A225170.

seq(n) = Vec(2*serlaplace(1 - x + serreverse((1 + 2*x - exp(x + O(x*x^n)))/2))) \\ Andrew Howroyd, Mar 28 2025

a(n) = 2*A005172(n) for n > 0. - Andrew Howroyd, Mar 28 2025

Name clarified and a(19) onwards from Andrew Howroyd, Mar 28 2025

A225170 Number of non-degenerate fanout-free Boolean functions of n variables having AND rank 1.

Original entry on oeis.org

2, 4, 32, 416, 7552, 176128, 5018624, 168968192, 6563282944, 288909131776, 14212910809088, 772776684683264, 46017323176296448, 2978458881388183552, 208198894960190160896, 15631251601179130462208, 1254492810303112820555776, 107174403941451434687463424

Offset: 1

N. J. A. Sloane, Apr 30 2013

nonn

Apart from initial term, same as A005172, which is the main entry for this sequence.

Vaclav Kotesovec, Table of n, a(n) for n = 1..241
J. P. Hayes, Enumeration of fanout-free Boolean functions, J. ACM, 23 (1976), 700-709.
Index entries for sequences related to Boolean functions

Column 1 of A225171.

Cf. A000311, A005172.

max = 16; s = -ProductLog[-Exp[x-1/2]/2] + O[x]^max; Join[{2}, Drop[CoefficientList[s, x]*Range[0, max-1]!, 2]] (* Jean-François Alcover, Oct 18 2016 *)
a[1] = 2; a[n_] := (Sum[(n + k - 1)!*Sum[(-1)^j/(k - j)!*Sum[(-1)^i*2^(n - i + j - 1)*StirlingS1[n - i + j - 1, j - i]/((n - i + j - 1)!*i!), {i, 0, j}], {j, 1, k}], {k, 1, n - 1}]);
Array[a, 20] (* Jean-François Alcover, Jun 24 2018, after Vladimir Kruchinin *)

seq(n) = Vec(serlaplace(serreverse((1 + 2*x - exp(x + O(x*x^n)))/2 ))) \\ Andrew Howroyd, Mar 28 2025

Hayes (1976, Theorem 3) gives a recurrence.
G.f.: 1/Q(0) + 1, where Q(k)= 1 - 2*x*(k+1) - 2*x*(k+1)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 18 2013
a(n) ~ (log(2)-1/2)^(1/2 - n) * n^(n-1) / exp(n). - Vaclav Kotesovec, Oct 19 2016
a(n) = 2^n * A000311(n). - Andrew Howroyd, Mar 28 2025

A005173 Number of rooted trees with 3 nodes of 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.

Original entry on oeis.org

0, 1, 12, 61, 240, 841, 2772, 8821, 27480, 84481, 257532, 780781, 2358720, 7108921, 21392292, 64307941, 193185960, 580082161, 1741295052, 5225982301, 15682141200, 47054812201, 141181213812, 423577195861, 1270798696440, 3812530307041, 11437859356572, 34314114940621

Offset: 1

N. J. A. Sloane

			From _Andrew Howroyd_, Mar 28 2025: (Start)
The a(3) = 12 trees up to relabeling have one of the following 3 forms:
     {}         {1}        {1}
    /  \       /   \        |
  {1} {2,3}   {2}  {3}     {2}
                            |
                           {3}
(End)

F. R. McMorris and T. Zaslavsky, The number of cladistic characters, Math. Biosciences, 54 (1981), 3-10.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 1..500
F. R. McMorris and T. Zaslavsky, The number of cladistic characters, Math. Biosciences, 54 (1981), 3-10. [Annotated scanned copy]
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
Index entries for sequences related to trees
Index entries for linear recurrences with constant coefficients, signature (6, -11, 6).

Column 3 of A094262.

Cf. A003063.

A005173:=-z*(1+6*z)/(z-1)/(3*z-1)/(2*z-1); # conjectured by Simon Plouffe in his 1992 dissertation

CoefficientList[Series[x (1+6 x)/(1-x)/(1-2 x)/(1-3 x),{x,0,30}],x] (* Harvey P. Dale, Jul 03 2023 *)

G.f.: x*(1 + 6*x) / ((1 - x)*(1 - 2*x)*(1 - 3*x)). [corrected by Ray Chandler, Jun 26 2023]
First differences give A003063, 3^(n-1) - 2^n.
From Andrew Howroyd, Mar 28 2025: (Start)
a(n) = (3^(n+1) - 2^(n+3) + 7)/2.
E.g.f.: (3*exp(x)/2 - 1)*(exp(x) - 1)^2. (End)

More terms from Larry Reeves (larryr(AT)acm.org), Feb 06 2001

Name clarified by Andrew Howroyd, Mar 28 2025

A005174 Number of rooted trees with 4 nodes of 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.

Original entry on oeis.org

0, 0, 10, 124, 890, 5060, 25410, 118524, 527530, 2276020, 9613010, 40001324, 164698170, 672961380, 2734531810, 11066546524, 44652164810, 179768037140, 722553165810, 2900661482124, 11634003919450, 46630112719300, 186802788139010, 748058256616124

Offset: 1

N. J. A. Sloane

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 1..500
F. R. McMorris and T. Zaslavsky, The number of cladistic characters, Math. Biosciences, 54 (1981), 3-10.
F. R. McMorris and T. Zaslavsky, The number of cladistic characters, Math. Biosciences, 54 (1981), 3-10. [Annotated scanned copy]
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
Index entries for sequences related to trees
Index entries for linear recurrences with constant coefficients, signature (10,-35,50,-24).

Column 4 of A094262.

A005174:=2*z**2*(5+12*z)/(z-1)/(3*z-1)/(2*z-1)/(4*z-1); # conjectured by Simon Plouffe in his 1992 dissertation

The terms a(1)-a(18) are given by a(n) = (8/3)*(4^n - 4) - 9*3^n + 11*2^n + 5. - John W. Layman, Jul 20 1999
Formula of Layman matches the proven formula in McMorris and Zaslavsky. - Sean A. Irvine, Apr 12 2016
E.g.f.: (1/3)*(-17*exp(x) + 66*exp(2*x) - 81*exp(3*x) + 32*exp(4*x)). - Ilya Gutkovskiy, Apr 12 2016
G.f.: 2*x^3*(5 + 12*x)/((1 - x)*(1 - 2*x)*(1 - 3*x)*(1 - 4*x)). - Andrew Howroyd, Mar 28 2025

Name clarified by Andrew Howroyd, Mar 28 2025

A005175 Number of rooted trees with 5 nodes of 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.

Original entry on oeis.org

0, 0, 3, 131, 1830, 16990, 127953, 851361, 5231460, 30459980, 170761503, 931484191, 4979773890, 26223530970, 136522672653, 704553794621, 3611494269120, 18415268221960, 93516225653403, 473366777478651, 2390054857197150, 12043393363764950, 60590148885015753

Offset: 1

N. J. A. Sloane

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 1..500
F. R. McMorris and T. Zaslavsky, The number of cladistic characters, Math. Biosciences, 54 (1981), 3-10.
F. R. McMorris and T. Zaslavsky, The number of cladistic characters, Math. Biosciences, 54 (1981), 3-10. [Annotated scanned copy]
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
Index entries for sequences related to trees
Index entries for linear recurrences with constant coefficients, signature (15,-85,225,-274,120).

Column 5 of A094262.

A005175:=-z**2*(3+86*z+120*z**2)/(z-1)/(4*z-1)/(3*z-1)/(2*z-1)/(5*z-1); # conjectured by Simon Plouffe in his 1992 dissertation

Table[(125/24) 5^n - (64/3) 4^n + (135/4) 3^n - (76/3) 2^n + 209/24, {n, 20}] (* Michael De Vlieger, Apr 12 2016 *)

a(n+1) = 3*(3^n - 2*2^n + 1)/2 + 113*(4^n - 3*3^n + 3*2^n - 1)/6 + 625*(5^n - 4*4^n + 6*3^n - 4*2^n + 1)/24. - formula fitted by John W. Layman
a(n) = (125/24) * 5^n - (64/3) * 4^n + (135/4)*3^n - (76/3) * 2^n + 209/24 proven in McMorris and Zaslavsky, matches Layman's formula with an offset of 1. - Sean A. Irvine, Apr 12 2016
E.g.f.: (1/24)*exp(x)*(-1 + exp(x))^2*(209 - 798*exp(x) + 625*exp(2*x)). - Ilya Gutkovskiy, Apr 12 2016
G.f.: x^3*(3 + 86*x + 120*x^2)/((1 - x)*(1 - 2*x)*(1 - 3*x)*(1 - 4*x)*(1 - 5*x)). - Andrew Howroyd, Mar 28 2025

Name clarified by Andrew Howroyd, Mar 28 2025

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A005264 Number of labeled rooted Greg trees with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

PARI

Sage

Formula

A005263 Number of labeled Greg trees.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A005640 Number of phylogenetic trees with n labels.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A225171 Triangle read by rows: T(n,k), 1 <= k <= n, is the number of non-degenerate fanout-free Boolean functions of n variables having AND rank k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A224766 Number of non-degenerate fanout-free Boolean functions of n variables using And, Or and Not gates.

Views

Author

Keywords

Comments

References

Links

Crossrefs