A144528 -id:A144528 - cp's OEIS frontend

A000602 Number of n-node unrooted quartic trees; number of n-carbon alkanes C(n)H(2n+2) ignoring stereoisomers.

1, 1, 1, 1, 2, 3, 5, 9, 18, 35, 75, 159, 355, 802, 1858, 4347, 10359, 24894, 60523, 148284, 366319, 910726, 2278658, 5731580, 14490245, 36797588, 93839412, 240215803, 617105614, 1590507121, 4111846763, 10660307791, 27711253769

Offset: 0

N. J. A. Sloane

Trees are unrooted, nodes are unlabeled. Every node has degree <= 4.
Ignoring stereoisomers means that the children of a node are unordered. They can be permuted in any way and it is still the same tree. See A000628 for the analogous sequence with stereoisomers counted.
In alkanes every carbon has valence exactly 4 and every hydrogen has valence exactly 1. But the trees considered here are just the carbon "skeletons" (with all the hydrogen atoms stripped off) so now each carbon bonds to 1 to 4 other carbons. The degree of each node is then <= 4.

			a(6)=5 because hexane has five isomers: n-hexane; 2-methylpentane; 3-methylpentane; 2,2-dimethylbutane; 2,3-dimethylbutane. - Michael Lugo (mtlugo(AT)mit.edu), Mar 15 2003 (corrected by _Andrey V. Kulsha_, Sep 22 2011)

Klemens Adam, Die Anzahlbestimmung der isomeren Alkane, MNU 1983, 36, 29 (in German).
F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 290.
L. Bytautats, D. J. Klein, Alkane Isomer Combinatorics: Stereostructure enumeration and graph-invariant and molecular-property distributions, J. Chem. Inf. Comput. Sci 39 (1999) 803, Table 1.
A. Cayley, Über die analytischen Figuren, welche in der Mathematik Baeume genannt werden..., Chem. Ber. 8 (1875), 1056-1059.
R. Davies and P. J. Freyd, C_{167}H_{336} is The Smallest Alkane with More Realizable Isomers than the Observable Universe has Particles, Journal of Chemical Education, Vol. 66, 1989, pp. 278-281.
J. L. Faulon, D. Visco and D. Roe, Enumerating Molecules, In: Reviews in Computational Chemistry Vol. 21, Ed. K. Lipkowitz, Wiley-VCH, 2005.
Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, Section 5.6.1 Chemical Isomers, p. 299.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 529.
Handbook of Combinatorics, North-Holland '95, p. 1963.
J. B. Hendrickson and C. A. Parks, "Generation and Enumeration of Carbon skeletons", J. Chem. Inf. Comput. Sci, vol. 31 (1991) pp. 101-107. See Table 2, column 2 on page 103.
M. D. Jackson and T. I. Bieber, Applications of degree distribution, 2: construction and enumeration of isomers in the alkane series, J. Chem. Info. and Computer Science, 33 (1993), 701-708.
J. Lederberg et al., Applications of artificial intelligence for chemical systems, I: The number of possible organic compounds. Acyclic structures containing C, H, O and N, J. Amer. Chem. Soc., 91 (1969), 2973-2097.
L. M. Masinter, Applications of artificial intelligence for chemical systems, XX, Exhaustive generation of cyclic and acyclic isomers, J. Amer. Chem. Soc., 96 (1974), 7702-7714.
D. Perry, The number of structural isomers ..., J. Amer. Chem. Soc. 54 (1932), 2918-2920. [Gives a(60) correctly - compare first link below]
M. Petkovsek and T. Pisanski, Counting disconnected structures: chemical trees, fullerenes, I-graphs and others, Croatica Chem. Acta, 78 (2005), 563-567.
D. H. Rouvray, An introduction to the chemical applications of graph theory, Congress. Numerant., 55 (1986), 267-280. - N. J. A. Sloane, Apr 08 2012
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Marten J. ten Hoor, Formula for Success?, Education in Chemistry, 2005, 42(1), 10.
S. Wagner, Graph-theoretical enumeration and digital expansions: an analytic approach, Dissertation, Fakult. f. Tech. Math. u. Tech. Physik, Tech. Univ. Graz, Austria, Feb., 2006.

Pontus von Brömssen, Table of n, a(n) for n = 0..1000 (terms n = 0..60 from N. J. A. Sloane)
Jean-François Alcover, Mathematica program translated from N. J. A. Sloane's Maple program for A000022, A000200, A000598, A000602, A000678
M. van Almsick, H. Dolhaine and H. Honig, Efficient algorithms to enumerate isomers and diamutamers with more than one type of substituent, J. Chem. Info. and Computer Science, 40 (2000), 956-966.
Vijayakumar Ambat, Article about OEIS in Malayalam that mentions this sequence, Mathrubhumi (daily newspaper in Kerala State), circa Nov 20 2022.
R. Aringhieri, P. Hansen and F. Malucelli, Chemical Tree Enumeration Algorithms, Report TR-99-09, Dept. Informatica, Univ. Pisa, 1999.
A. T. Balaban, J. W. Kennedy and L. V. Quintas, The number of alkanes having n carbons and a longest chain of length d, J. Chem. Education, 65 (1988), 304-313.
H. Bottomley, Illustration of initial terms of A000022, A000200, A000602
L. Bytautas and D. J. Klein, Chemical combinatorics for alkane-isomer enumeration and more, J. Chem. Inf. Comput. Sci., 38 (1998), 1063-1078.
A. Cayley, Über die analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen, Chem. Ber. 8 (1875), 1056-1059. (Annotated scanned copy)
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 478
Alfred W. Francis, Numbers of Isomeric Alkylbenzenes, J. Am. Chem. Soc., 69:6 (1947), pp. 1536-1537.
R. K. Guy, Letter to N. J. A. Sloane, Mar. 1988
F. Harary and R. Z. Norman, Dissimilarity characteristic theorems for graphs, Proc. Amer. Math. Soc. 11 (1960), 332-334.
H. R. Henze and C. M. Blair, The number of isomeric hydrocarbons of the methane series, J. Amer. Chem. Soc., 53 (8) (1931), 3077-3085.
H. R. Henze and C. M. Blair, The number of isomeric hydrocarbons of the methane series, J. Amer. Chem. Soc., 53 (1931), 3077-3085. (Annotated scanned copy)
H. R. Henze and C. M. Blair, The number of structurally isomeric Hydrocarbons of the Ethylene Series, J. Amer. Chem. Soc., 55 (2) (1933), 680-686.
F. Hermann, Ueber das Problem, die Anzahl der isomeren Paraffine der Formel C_n H_{2n+2} zu bestimmung, Chem. Ber., 13 (1880), 792. [I (1880), Annotated scanned copy]
F. Hermann, Ueber das Problem, die Anzahl der isomeren Paraffine der Formel C_n H_{2n+2} zu bestimmung, Chem. Ber., 30 (1897), 2423-2426. [II (1897), Annotated scanned copy]
F. Hermann, Entgegnung, Chem. Ber., 31 (1898), 91. [III (1898), Annotated scanned copy]
Lorentz Jäntschi and Lavinia-Lorena Pruteanu, Geometry of C_32 cyclic polyyne and some of its clusters, Carpathian J. Math. (2025) Vol. 41, No. 2, 371-391. See p. 371.
Michael A. Kappler, GENSMI: Exhaustive Enumeration of Simple Graphs. Daylight CIS, Inc., EuroMUG '04;4-Nov 05 2004.
E. V. Konstantinova and M. V. Vidyuk, Discriminating tests of information and topological indices; animals and trees; J. Chem. Inf. Comput. Sci., 43 (2003), 1860-1871.
J. Lederberg, Letter to N. J. A. Sloane, Aug 13 1971
J. Lederberg, The topology of molecules, in The Mathematical Sciences. Cambridge, Mass.: MIT Press, 1969, pages 37-51. [Annotated scanned copy]
J. Lederberg, Dendral-64, I, Report to NASA, Dec 1964 [Annotated scanned copy]
J. Lederberg, Dendral-64, II, Report to NASA, Dec 1965 [Annotated scanned copy]
J. Lederberg, Dendral-64, III, Report to NASA, Dec 1968 [Annotated scanned copy]
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1 (1992), pp. 53-80.
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
S. M. Losanitsch, Die Isomerie-Arten bei den Homologen der Paraffin-Reihe, Chem. Ber. 30 (1897), 1917-1926.
S. M. Losanitsch, Die Isomerie-Arten bei den Homologen der Paraffin-Reihe, Chem. Ber. 30 (1897), 1917-1926. (Annotated scanned copy)
S. M. Losanitsch, Bemerkungen zu der Hermasnnschen Mitteillung: Die Anzahl..., Chem. Ber., 30 (1897), 3059-3060 [Annotated scanned copy]
A. Masoumi, M. Antoniazzi, and M. Soutchanski, Modeling organic chemistry and planning organic synthesis, GCAI 2015. Global Conference on Artificial Intelligence (2015), pp. 176-195.
W. R. Mueller et al., Molecular topological index, J. Chem. Inf. Comput. Sci., 30 (1990),160-163.
R. Otter, The number of trees, Ann. of Math. (2) 49 (1948), 583-599 discusses asymptotics.
D. Perry, The number of structural isomers of certain homologs of methane and methanol, J. Amer. Chem. Soc. 54 (1932), 2918-2920. [Gives a(60) correctly] (Annotated scanned copy)
G. Polya, Algebraische Berechnung der Anzahl der Isomeren einiger organischer Verbindungen, Zeit. f. Kristall., 93 (1936), 415-443
G. Polya, Algebraische Berechnung der Anzahl der Isomeren einiger organischer Verbindungen, Zeit. f. Kristall., 93 (1936), 415-443. (Annotated scanned copy)
E. M. Rains and N. J. A. Sloane, On Cayley's Enumeration of Alkanes (or 4-Valent Trees), J. Integer Sequences, Vol. 2 (1999), Article 99.1.1.
R. C. Read, The Enumeration of Acyclic Chemical Compounds, pp. 25-61 of A. T. Balaban, ed., Chemical Applications of Graph Theory, Ac. Press, 1976. [Annotated scanned copy] See p. 28.
R. W. Robinson, F. Harary and A. T. Balaban, Numbers of chiral and achiral alkanes and monosubstituted alkanes, Tetrahedron 32 (3) (1976), 355-361.
R. W. Robinson, F. Harary and A. T. Balaban, Numbers of chiral and achiral alkanes and monosubstituted alkanes, Tetrahedron 32 (3) (1976), 355-361. (Annotated scanned copy)
Hugo Schiff, Zur Statistik chemischer Verbindungen, Berichte der Deutschen Chemischen Gesellschaft, Vol. 8, pp. 1542-1547, 1875. [Annotated scanned copy]
Nicholas I. Shepherd-Barron, Asymptotic period relations for Jacobian elliptic surfaces, arXiv:1904.13344 [math.AG], 2019.
N. J. A. Sloane, Maple program and first 60 terms for A000022, A000200, A000598, A000602, A000678
N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 5.
N. Trinajstich, Z. Jerievi, J. V. Knop, W. R. Muller and K. Szymanski, Computer Generation of Isomeric Structures, Pure & Appl. Chem., Vol. 55, No. 2, pp. 379-390, 1983.
Stephan Wagner, On the average Wiener index of degree-restricted trees
Sylvia Wenmackers, Huiswerk (met bijna twintig jaar vertraging) (in Dutch), 2015.
Index entries for sequences related to trees
Index entries for "core" sequences

Column k=4 of A144528.
A000602 = A000022 + A000200 for n>0.
Cf. A000598, A000625, A000628, A067608, A067609, A067610.

A000602 := proc(n)
    if n=0 then
        1
    else
        A000022(n)+A000200(n);
    end if;
end proc:

n = 40; (* algorithm from Rains and Sloane *)
S3[f_,h_,x_] := f[h,x]^3/6 + f[h,x] f[h,x^2]/2 + f[h,x^3]/3;
S4[f_,h_,x_] := f[h,x]^4/24 + f[h,x]^2 f[h,x^2]/4 + f[h,x] f[h,x^3]/3 + f[h,x^2]^2/8 + f[h,x^4]/4;
T[-1,z_] := 1;  T[h_,z_] := T[h,z] = Table[z^k, {k,0,n}].Take[CoefficientList[z^(n+1) + 1 + S3[T,h-1,z]z, z], n+1];
Sum[Take[CoefficientList[z^(n+1) + S4[T,h-1,z]z - S4[T,h-2,z]z - (T[h-1,z] - T[h-2,z]) (T[h-1,z]-1),z], n+1], {h,1,n/2}] + PadRight[{1,1}, n+1] + Sum[Take[CoefficientList[z^(n+1) + (T[h,z] - T[h-1,z])^2/2 + (T[h,z^2] - T[h-1,z^2])/2, z],n+1], {h,0,n/2}] (* Robert A. Russell, Sep 15 2018 *)
b[n_, i_, t_, k_] := b[n,i,t,k] = If[i<1, 0, Sum[Binomial[b[i-1,i-1,
  k,k] + j-1, j]* b[n-i*j, i-1, t-j, k], {j, 0, Min[t, n/i]}]];
b[0, i_, t_, k_] = 1; m = 3; (* m = maximum children *) n = 40;
gf[x_] = 1 + Sum[b[j-1,j-1,m,m]x^j,{j,1,n}]; (* G.f. for A000598 *)
ci[x_] = SymmetricGroupIndex[m+1, x] /. x[i_] -> gf[x^i];
CoefficientList[Normal[Series[gf[x] - (gf[x]^2 - gf[x^2])/2 + x ci[x],
{x, 0, n}]],x] (* Robert A. Russell, Jan 19 2023 *)

a(n) = A010372(n) + A010373(n/2) for n even, a(n) = A010372(n) for n odd.
Also equals A000022 + A000200 (n>0), both of which have known generating functions. Also g.f. = A000678(x) - A000599(x) + A000598(x^2) = (x + x^2 + 2x^3 + ...) - (x^2 + x^3 + 3x^4 + ...) + (1 + x^2 + x^4 + ...) = 1 + x + x^2 + x^3 + 2x^4 + 3x^5 + ...
G.f.: B(x) - cycle_index(S2,-B(x)) + x * cycle_index(S4,B(x)) = B(x) - (B(x)^2 - B(x^2)) / 2 + x * (B(x)^4 + 6*B(x)^2*B(x^2) + 8*B(x)*B(x^3) + 3*B(x^2)^2 + 6*B(x^4)) / 24, where B(x) = 1 + x * cycle_index(S3,B(x)) = 1 + x * (B(x)^3 + 3*B(x)*B(x^2) + 2*B(x^3)) / 6 is the generating function for A000598. - Robert A. Russell, Jan 16 2023

Additional comments from Steve Strand (snstrand(AT)comcast.net), Aug 20 2003

A000672 Number of 3-valent trees (= boron trees or binary trees) with n nodes.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 4, 6, 11, 18, 37, 66, 135, 265, 552, 1132, 2410, 5098, 11020, 23846, 52233, 114796, 254371, 565734, 1265579, 2841632, 6408674, 14502229, 32935002, 75021750, 171404424, 392658842, 901842517, 2076217086, 4790669518, 11077270335

Offset: 0

N. J. A. Sloane

This can be described in 2 ways: (a) Trees with n nodes of valency <= 3, for n = 0,1,2,3,... (b) Trees with t = 2n+2 nodes of valency either 1 or 3 (implying that there are n nodes of valency 3 - the boron atoms - and n+2 nodes of valency 1 - the hydrogen atoms), for t = 2,4,6,8,...

Essentially the same sequences arises from studying the number of unrooted, unlabeled binary tree topologies with n leaves (see A129860). - Steven Kelk, Jul 22 2016

			The 4 trees with 6 nodes are:
._._._._._. . ._._._._. . ._._._._. . ._._._.
. . . . . . . . | . . . . . . | . . . . | |
G.f. = 1 + x + x^2 + x^3 + 2*x^4 + 2*x^5 + 4*x^6 + 6*x^7 + 11*x^8 + ...

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 307.
P. J. Cameron, Oligomorphic Permutation Groups, Cambridge; see Fig. 2 p. 35.
A. Cayley, On the analytical forms called trees, with application to the theory of chemical combinations, Reports British Assoc. Advance. Sci. 45 (1875), 257-305 = Math. Papers, Vol. 9, 427-460 (see p. 451).
Joseph Felsenstein, Inferring Phylogenies. Sinauer Associates, Inc., 2004, page 33. Note that at least the first two editions give an incorrect version of this sequence.
R. C. Read, personal communication.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. J. Mathar, Table of n, a(n) for n = 0..191 [b-file corrected by _N. J. A. Sloane_, Oct 04 2010]
Dominik Bendle, Janko Boehm, Yue Ren, and Benjamin Schröter, Parallel Computation of tropical varieties, their positive part, and tropical Grassmannians, arXiv:2003.13752 [math.AG], 2020.
Nicolas Broutin and Philippe Flajolet, The distribution of height and diameter in random non-plane binary trees, Random Struct. Algorithms 41, No. 2, 215-252 (2012).
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
P. J. Cameron, Some treelike objects, Quart. J. Math. Oxford, 38 (1987), 155-183.
M. Chan, Tropical hyperelliptic curves, arXiv preprint arXiv:1110.0273 [math.CO], 2011.
Sergio Consoli, Jan Korst, Gijs Geleijnse, and Steffen Pauws, On the minimum quartet tree cost problem, arXiv:1807.00566 [cs.DM], 2018.
S. J. Cyvin, J. Brunvoll, and B. N. Cyvin, Enumeration of constitutional isomers of polyenes, J. Molec. Struct. (Theochem) 357, no. 3 (1995) 255-261.
V. Fack, S. Lievens, and J. Van der Jeugt, On the diameter of the rotation graph of binary coupling trees, Discrete Math. 245 (2002), no. 1-3, 1--18. MR1887046 (2003i:05047).
Jean-François Fortin, Wen-Jie Ma, and Witold Skiba, Six-Point Conformal Blocks in the Snowflake Channel, arXiv:2004.02824 [hep-th], 2020.
Jean-François Fortin, Wen-Jie Ma, and Witold Skiba, Seven-Point Conformal Blocks in the Extended Snowflake Channel and Beyond, arXiv:2006.13964 [hep-th], 2020.
Jean-François Fortin, Wen-Jie Ma, and Witold Skiba, All Global One- and Two-Dimensional Higher-Point Conformal Blocks, arXiv:2009.07674 [hep-th], 2020.
M. D. Hendy, C. H. C. Little, David Penny, Comparing trees with pendant vertices labelled, SIAM J. Appl. Math. 44 (5) (1984) Table 1
Virginia Perkins Johnson, Enumeration Results on Leaf Labeled Trees, PhD Dissertation, University of South Carolina, 2012. - From _N. J. A. Sloane_, Dec 22 2012
R. Otter, The number of trees, Ann. of Math. (2) 49 (1948), 583-599 discusses asymptotics.
E. M. Rains and N. J. A. Sloane, On Cayley's Enumeration of Alkanes (or 4-Valent Trees), J. Integer Sequences, Vol. 2 (1999), Article 99.1.1.
R. C. Read, Letter to N. J. A. Sloane, Oct. 29, 1976
Eric Weisstein's World of Mathematics, Trivalent Tree
Index entries for sequences related to trees

Column k = 3 of A144528.
A000672 = A000675 + A000673.
Cf. A001190(n+1) (rooted trees).
Cf. A052120, A000022, A000200, A000602, A129860.

(* c = A001190 *) c[n_?OddQ] := c[n] = Sum[c[k]*c[n-k], {k, 1, (n-1)/2}]; c[n_?EvenQ] := c[n] = (1/2)*c[n/2]*(c[n/2] + 1) + Sum[c[k]*c[n-k], {k, 1, n/2-1}]; c[0] = 0; c[1] = 1; b[x_] := If[IntegerQ[x], c[x+1], 0]; a[0] = a[1] = a[2] = 1; a[n_] := b[n/2] - (1/3)*(b[(n-1)/3]-1)*b[(n-1)/3]*(b[(n-1)/3] + 1) + 2*b[n] - b[n+1] - Sum[(1/2)*(b[i]-1)*b[i]*b[-2*i + n - 1], {i, 1, (n-2)/2}] + Sum[b[i]*Sum[b[j]*b[n-i-j-1], {j, i, (1/2)*(n-i-1)}], {i, 1, (n-1)/3}]; Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Jan 19 2015 *)
n = 50; (* algorithm from Rains and Sloane *)
S2[f_,h_,x_] := f[h,x]^2/2 + f[h,x^2]/2;
S3[f_,h_,x_] := f[h,x]^3/6 + f[h,x] f[h,x^2]/2 + f[h,x^3]/3;
T[-1,z_] := 1;  T[h_,z_] := T[h,z] = Table[z^k, {k,0,n}].Take[CoefficientList[z^(n+1) + 1 + S2[T,h-1,z]z, z], n+1];
Sum[Take[CoefficientList[z^(n+1) + S3[T,h-1,z]z - S3[T,h-2,z]z - (T[h-1,z] - T[h-2,z]) (T[h-1,z]-1),z], n+1], {h,1,n/2}] + PadRight[{1,1}, n+1] + Sum[Take[CoefficientList[z^(n+1) + (T[h,z] - T[h-1,z])^2/2 + (T[h,z^2] - T[h-1,z^2])/2, z],n+1], {h,0,n/2}] (* Robert A. Russell, Sep 15 2018 *)
n = 60; c[n_?OddQ] := c[n] = Sum[c[k]*c[n-k], {k,1,(n-1)/2}];
c[n_?EvenQ] := c[n] = (1/2)*c[n/2]*(c[n/2] + 1) + Sum[c[k]*c[n-k],
  {k,1,n/2-1}]; c[0] = 0; c[1] = 1; (* as in program 1 above *)
gf[x_] := Sum[c[i+1] x^i, {i,0,n}]; (* g.f. for A001190(n+1) *)
ci[x_] := SymmetricGroupIndex[3, x] /. x[i_] -> gf[x^i];
CoefficientList[Normal[Series[gf[x] - (gf[x]^2 - gf[x^2])/2 +
x ci[x], {x,0,n}]], x] (* Robert A. Russell, Jan 17 2023 *)

Rains and Sloane give a g.f.
a(0)=a(1)=a(2)=1, a(n) = 2*b(n+1) - b(n+2) + b((n+1)/2) - 2*C(1+b(n/3), 3) - Sum_{i=1..[(n-1)/2]} C(b(i), 2)*b(n-2*i) + Sum_{i=1..[n/3]} b(i) Sum_{j=i..[(n-i)/2]} b(j)*b(n-i-j), where b(x) = A001190(x+1) if x is an integer, otherwise 0 (Cyvin et al.) [Index of A001190 shifted by R. J. Mathar, Mar 08 2010]
a(n) = A000673(n) + A000675(n).
a(n) ~ c * d^n / n^(5/2), where d = A086317 = 2.4832535361726368585622885181... and c = 1.2551088797592580080398489829149157375... . - Vaclav Kotesovec, Apr 19 2016
G.f.: B(x) - cycle_index(S2,-B(x)) + x * cycle_index(S3,B(x)) = B(x) - (B(x)^2 - B(x^2)) / 2 + x * (B(x)^3 + 3*B(x) B(x^2) + 2*B(x^3)) / 6, where B(x) = 1 + x * cycle_index(S2,B(x)) = 1 + x * (B(x)^2 + B(x^2)) / 2 is the generating function for A001190(n+1). - Robert A. Russell, Jan 17 2023

A144215 Triangle read by rows: T(n,k) is the number of forests on n unlabeled nodes with all nodes of degree <= k (n>=1, 0 <= k <= n-1).

Original entry on oeis.org

1, 1, 2, 1, 2, 3, 1, 3, 5, 6, 1, 3, 7, 9, 10, 1, 4, 11, 17, 19, 20, 1, 4, 15, 28, 34, 36, 37, 1, 5, 22, 52, 67, 73, 75, 76, 1, 5, 30, 90, 129, 144, 150, 152, 153, 1, 6, 42, 170, 264, 305, 320, 326, 328, 329, 1, 6, 56, 310, 542, 645, 686, 701, 707, 709, 710

Offset: 1

N. J. A. Sloane, Dec 20 2008

			Triangle begins:
  1
  1 2
  1 2  3
  1 3  5  6
  1 3  7  9 10
  1 4 11 17 19 20
  1 4 15 28 34 36 37
  ...
From _Andrew Howroyd_, Dec 18 2020: (Start)
Formatted as an array to show the full columns:
========================================================
n\k  | 0 1  2   3    4    5    6    7    8    9   10
-----+--------------------------------------------------
   1 | 1 1  1   1    1    1    1    1    1    1    1 ...
   2 | 1 2  2   2    2    2    2    2    2    2    2 ...
   3 | 1 2  3   3    3    3    3    3    3    3    3 ...
   4 | 1 3  5   6    6    6    6    6    6    6    6 ...
   5 | 1 3  7   9   10   10   10   10   10   10   10 ...
   6 | 1 4 11  17   19   20   20   20   20   20   20 ...
   7 | 1 4 15  28   34   36   37   37   37   37   37 ...
   8 | 1 5 22  52   67   73   75   76   76   76   76 ...
   9 | 1 5 30  90  129  144  150  152  153  153  153 ...
  10 | 1 6 42 170  264  305  320  326  328  329  329 ...
  11 | 1 6 56 310  542  645  686  701  707  709  710 ...
  12 | 1 7 77 600 1161 1431 1536 1577 1592 1598 1600 ...
(End)

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 rows)
Rebecca Neville, Graphs whose vertices are forests with bounded degree, Graph Theory Notes of New York, LIV (2008), 12-21. [Wayback Machine link]

The final diagonal gives A005195.
Column k=2 is A000041.
Cf. A144528, A144529, A339788.

\\ Here V(n,k) gives column k of A144528.
EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
MSet(p,k)={my(n=serprec(p,x)-1); if(min(k,n)<1, 1 + O(x*x^n), polcoef(exp( sum(i=1, min(k,n), (y^i + O(y*y^k))*subst(p + O(x*x^(n\i)), x, x^i)/i ))/(1-y + O(y*y^k)), k, y))}
V(n,k)={my(g=1+O(x)); for(n=2, n, g=x*MSet(g, k-1)); Vec(1 + x*MSet(g, k) + (subst(g, x, x^2) - g^2)/2)}
M(n, m=n)={Mat(vector(m, k, EulerT(V(n,k-1)[2..1+n])~))}
{ my(T=M(12)); for(n=1, #T~, print(T[n, 1..n])) } \\ Andrew Howroyd, Dec 18 2020

Column k is Euler transform of column k of A144528. - Andrew Howroyd, Dec 18 2020

Terms a(29) and beyond from Andrew Howroyd, Dec 18 2020

A036650 Number of 5-valent trees with n nodes.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 6, 10, 21, 42, 94, 204, 473, 1098, 2633, 6353, 15641, 38789, 97416, 246410, 628726, 1614292, 4171955, 10839366, 28308678, 74266477, 195667533, 517504253, 1373640355, 3658205088, 9772510063, 26181295237, 70330621171

Offset: 0

N. J. A. Sloane

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..500
R. Otter, The number of trees, Ann. of Math. (2) 49 (1948), 583-599 discusses asymptotics.
E. M. Rains and N. J. A. Sloane, On Cayley's Enumeration of Alkanes (or 4-Valent Trees)., J. Integer Sequences, Vol. 2 (1999), Article 99.1.1.
Index entries for sequences related to trees

Column k=5 of A144528; A036718 (rooted trees).

Cf. A036648, A036649.

n = 30; (* algorithm from Rains and Sloane *)
S4[f_,h_,x_] := f[h,x]^4/24 + f[h,x]^2 f[h,x^2]/4 + f[h,x] f[h,x^3]/3 + f[h,x^2]^2/8 + f[h,x^4]/4;
S5[f_,h_,x_] := f[h,x]^5/120 + f[h,x]^3 f[h,x^2]/12 + f[h,x]^2 f[h,x^3]/6 + f[h,x] f[h,x^2]^2/8 + f[h,x] f[h,x^4]/4 + f[h,x^2] f[h,x^3]/6 + f[h,x^5]/5;
T[-1,z_] := 1;  T[h_,z_] := T[h,z] = Table[z^k, {k,0,n}].Take[CoefficientList[z^(n+1) + 1 + S4[T,h-1,z]z, z], n+1];
Sum[Take[CoefficientList[z^(n+1) + S5[T,h-1,z]z - S5[T,h-2,z]z - (T[h-1,z] - T[h-2,z]) (T[h-1,z]-1),z], n+1], {h,1,n/2}] + PadRight[{0,1}, n+1] + Sum[Take[CoefficientList[z^(n+1) + (T[h,z] - T[h-1,z])^2/2 + (T[h,z^2] - T[h-1,z^2])/2, z],n+1], {h,0,n/2}] (* Robert A. Russell, Sep 15 2018 *)
b[n_, i_, t_, k_] := b[n,i,t,k] = If[i<1, 0, Sum[Binomial[b[i-1,i-1,
  k,k] + j-1, j]* b[n-i*j, i-1, t-j, k], {j, 0, Min[t, n/i]}]];
b[0, i_, t_, k_] = 1; m = 4; (* m = maximum children *) n = 40;
gf[x_] = 1 + Sum[b[j-1,j-1,m,m]x^j,{j,1,n}]; (* G.f. for A036718 *)
ci[x_] = SymmetricGroupIndex[m+1, x] /. x[i_] -> gf[x^i];
CoefficientList[Normal[Series[gf[x] - (gf[x]^2 - gf[x^2])/2 + x ci[x],
{x, 0, n}]],x] (* Robert A. Russell, Jan 19 2023 *)

a(n) = A036648(n) + A036649(n) for n > 0.

G.f.: B(x) - cycle_index(S2,-B(x)) + x * cycle_index(S5,B(x)) = B(x) - (B(x)^2 - B(x^2)) / 2 + x * (B(x)^5 + 10*B(x)^3*B(x^2) + 15*B(x)*B(x^2)^2 + 20*B(x)^2*B(x^3) + 20*B(x^2)*B(x^3) + 30*B(x)*B(x^4) + 24*B(x^5)) / 120, where B(x) = 1 + x * cycle_index(S4,B(x)) = 1 + x * (B(x)^4 + 6*B(x)^2*B(x^2) + 8*B(x)*B(x^3) + 3*B(x^2)^2 + 6*B(x^4)) / 24 is the generating function for A036718. - Robert A. Russell, Jan 19 2023

a(0) changed to 1 by Andrew Howroyd, Dec 18 2020

A036653 Number of 6-valent trees with n nodes.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 6, 11, 22, 45, 101, 223, 520, 1223, 2954, 7208, 17905, 44863, 113738, 290605, 748711, 1941592, 5067433, 13297590, 35074788, 92939166, 247317085, 660681399, 1771321949, 4764829720, 12857155911, 34793296227, 94410222996, 256826514689, 700311754812, 1913868186951

Offset: 0

N. J. A. Sloane

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..500
R. Otter, The number of trees, Ann. of Math. (2) 49 (1948), 583-599 discusses asymptotics.
E. M. Rains and N. J. A. Sloane, On Cayley's Enumeration of Alkanes (or 4-Valent Trees)., J. Integer Sequences, Vol. 2 (1999), Article 99.1.1.
Index entries for sequences related to trees

Column k=6 of A144528; A036721 (rooted trees).

Cf. A036651, A036652.

n = 20; (* algorithm from Rains and Sloane *)
S5[f_,h_,x_] := f[h,x]^5/120 + f[h,x]^3 f[h,x^2]/12 + f[h,x]^2 f[h,x^3]/6 + f[h,x] f[h,x^2]^2/8 + f[h,x] f[h,x^4]/4 + f[h,x^2] f[h,x^3]/6 + f[h,x^5]/5;
S6[f_,h_,x_] := f[h,x]^6/720 + f[h,x]^4 f[h,x^2]/48 + f[h,x]^3 f[h,x^3]/18 + f[h,x]^2 f[h,x^2]^2/16 + f[h,x]^2 f[h,x^4]/8 + f[h,x] f[h,x^2] f[h,x^3]/6 + f[h,x] f[h,x^5]/5 + f[h,x^2]^3/48 + f[h,x^2] f[h,x^4]/8 + f[h,x^3]^2/18 + f[h,x^6]/6;
T[-1,z_] := 1;  T[h_,z_] := T[h,z] = Table[z^k, {k,0,n}].Take[CoefficientList[z^(n+1) + 1 + S5[T,h-1,z]z, z], n+1];
Sum[Take[CoefficientList[z^(n+1) + S6[T,h-1,z]z - S6[T,h-2,z]z - (T[h-1,z] - T[h-2,z]) (T[h-1,z]-1),z], n+1], {h,1,n/2}] + PadRight[{0,1}, n+1] + Sum[Take[CoefficientList[z^(n+1) + (T[h,z] - T[h-1,z])^2/2 + (T[h,z^2] - T[h-1,z^2])/2, z],n+1], {h,0,n/2}] (* Robert A. Russell, Sep 15 2018 *)
b[n_, i_, t_, k_] := b[n,i,t,k] = If[i<1, 0, Sum[Binomial[b[i-1,i-1,
  k,k] + j-1, j]* b[n-i*j, i-1, t-j, k], {j, 0, Min[t, n/i]}]];
b[0, i_, t_, k_] = 1; m = 5; (* m = maximum children *) n = 40;
gf[x_] = 1 + Sum[b[j-1,j-1,m,m]x^j,{j,1,n}]; (* G.f. for A036721 *)
ci[x_] = SymmetricGroupIndex[m+1, x] /. x[i_] -> gf[x^i];
CoefficientList[Normal[Series[gf[x] - (gf[x]^2 - gf[x^2])/2 + x ci[x],
{x, 0, n}]],x] (* Robert A. Russell, Jan 19 2023 *)

a(n) = A036651(n) + A036652(n) for n > 0.

G.f.: B(x) - cycle_index(S2,-B(x)) + x * cycle_index(S6,B(x)) = B(x) - (B(x)^2 - B(x^2)) / 2 + x * (B(x)^6 + 15*B(x)^4*B(x^2) + 45*B(x)^2*B(x^2)^2 + 15*B(x^2)^3 + 40*B(x)^3*B(x^3) + 120*B(x)*B(x^2)*B(x^3) + 40*B(x^3)^2 + 90*B(x)^2*B(x^4) + 90*B(x^2)*B(x^4) + 144*B(x)*B(x^5) + 120*B(x^6)) / 720, where B(x) = 1 + x * cycle_index(S5,B(x)) = 1 + x * (B(x)^5 + 10*B(x)^3*B(x^2) + 15*B(x)*B(x^2)^2 + 20*B(x)^2*B(x^3) + 20*B(x^2)*B(x^3) + 30*B(x)*B(x^4) + 24*B(x^5)) / 120 is the generating function for A036721. - Robert A. Russell, Jan 19 2023

a(0) changed to 1 and terms a(32) and beyond from Andrew Howroyd, Dec 18 2020

A238414 Triangle read by rows: T(n,k) is the number of trees with n vertices having maximum vertex degree k (n>=1, 0<=k<=n-1).

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 3, 1, 1, 0, 0, 1, 5, 3, 1, 1, 0, 0, 1, 10, 7, 3, 1, 1, 0, 0, 1, 17, 17, 7, 3, 1, 1, 0, 0, 1, 36, 38, 19, 7, 3, 1, 1, 0, 0, 1, 65, 93, 45, 19, 7, 3, 1, 1, 0, 0, 1, 134, 220, 118, 47, 19, 7, 3, 1, 1, 0, 0, 1, 264, 537, 296, 125, 47, 19, 7, 3, 1, 1

Offset: 1

Emeric Deutsch, Mar 05 2014

Sum of entries in row n is A000055(n) (= number of trees with n vertices).
The author knows of no formula for T(n,k). The entries have been obtained in the following manner, explained for row n = 7. In A235111 we find that the 11 (= A000055(7)) trees with 7 vertices have M-indices 25, 27, 30, 35, 36, 40, 42, 48, 49, 56, and 64 (the M-index of a tree t is the smallest of the Matula numbers of the rooted trees isomorphic, as a tree, to t). Making use of the formula in A196046, from these Matula numbers one obtains the maximum vertex degrees: 2, 3, 3, 3, 4, 4, 3, 5, 3, 4, 6; the frequencies of 2,3,4,5,6 are 1, 5, 3, 1, 1, respectively. See the Maple program.
This sequence may be derived from A144528 which can be efficiently computed in the same manner as A000055. - Andrew Howroyd, Dec 17 2020

			Row n=4 is T(4,2)=1,T(4,3)=1; indeed, the maximum vertex degree in the path P[4] is 2, while in the star S[4] it is 3.
Triangle starts:
  1;
  0, 1;
  0, 0, 1;
  0, 0, 1,  1;
  0, 0, 1,  1,  1;
  0, 0, 1,  3,  1, 1;
  0, 0, 1,  5,  3, 1, 1;
  0, 0, 1, 10,  7, 3, 1, 1;
  0, 0, 1, 17, 17, 7, 3, 1, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 12 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Eric Weisstein's World of Mathematics, Maximum Vertex Degree

Row sums are A000055.

Cf. A144528, A196046, A235111, A332760 (connected graphs), A339788 (forests).

MI := [25, 27, 30, 35, 36, 40, 42, 48, 49, 56, 64]: with(numtheory): a := proc (n) local r, s: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: if n = 1 then 0 elif bigomega(n) = 1 then max(a(pi(n)), 1+bigomega(pi(n))) else max(a(r(n)), a(s(n)), bigomega(r(n))+bigomega(s(n))) end if end proc: g := add(x^a(MI[j]), j = 1 .. nops(MI)): seq(coeff(g, x, q), q = 2 .. 6);

\\ Here V(n, k) gives column k of A144528.
MSet(p,k)={my(n=serprec(p,x)-1); if(min(k,n)<1, 1 + O(x*x^n), polcoef(exp( sum(i=1, min(k,n), (y^i + O(y*y^k))*subst(p + O(x*x^(n\i)), x, x^i)/i ))/(1-y + O(y*y^k)), k, y))}
V(n,k)={my(g=1+O(x)); for(n=2, n, g=x*MSet(g, k-1)); Vec(1 + x*MSet(g, k) + (subst(g, x, x^2) - g^2)/2)}
M(n, m=n)={my(v=vector(m, k, V(n,k-1)[2..1+n]~)); Mat(vector(m, k, v[k]-if(k>1, v[k-1])))}
{ my(T=M(12)); for(n=1, #T~, print(T[n, 1..n])) } \\ Andrew Howroyd, Dec 18 2020

T(n,k) = A144528(n,k) - A144528(n, k-1) for k > 0. - Andrew Howroyd, Dec 17 2020

Columns k=0..1 inserted by Andrew Howroyd, Dec 18 2020

A339788 Triangle read by rows: T(n,k) is the number of forests with n unlabeled vertices and maximum vertex degree k, (0 <= k < n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 4, 2, 1, 1, 3, 7, 6, 2, 1, 1, 3, 11, 13, 6, 2, 1, 1, 4, 17, 30, 15, 6, 2, 1, 1, 4, 25, 60, 39, 15, 6, 2, 1, 1, 5, 36, 128, 94, 41, 15, 6, 2, 1, 1, 5, 50, 254, 232, 103, 41, 15, 6, 2, 1, 1, 6, 70, 523, 561, 270, 105, 41, 15, 6, 2, 1

Offset: 1

Andrew Howroyd, Dec 18 2020

A forest is an acyclic graph.

(The component trees here are not rooted. - N. J. A. Sloane, Dec 19 2020)

			Triangle begins:
  1;
  1, 1;
  1, 1,  1;
  1, 2,  2,   1;
  1, 2,  4,   2,   1;
  1, 3,  7,   6,   2,   1;
  1, 3, 11,  13,   6,   2,  1;
  1, 4, 17,  30,  15,   6,  2,  1;
  1, 4, 25,  60,  39,  15,  6,  2, 1;
  1, 5, 36, 128,  94,  41, 15,  6, 2, 1;
  1, 5, 50, 254, 232, 103, 41, 15, 6, 2, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)
Eric Weisstein's World of Mathematics, Maximum Vertex Degree

Row sums are A005195.

Cf. A144215 (max degree <= k), A144528, A238414 (trees), A263293 (graphs).

\\ Here V(n, k) gives column k of A144528.
EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
MSet(p,k)={my(n=serprec(p,x)-1); if(min(k,n)<1, 1 + O(x*x^n), polcoef(exp( sum(i=1, min(k,n), (y^i + O(y*y^k))*subst(p + O(x*x^(n\i)), x, x^i)/i ))/(1-y + O(y*y^k)), k, y))}
V(n,k)={my(g=1+O(x)); for(n=2, n, g=x*MSet(g, k-1)); Vec(1 + x*MSet(g, k) + (subst(g, x, x^2) - g^2)/2)}
M(n, m=n)={my(v=vector(m, k, EulerT(V(n,k-1)[2..1+n])~)); Mat(vector(m, k, v[k]-if(k>1, v[k-1])))}
{ my(T=M(12)); for(n=1, #T~, print(T[n, 1..n])) }

T(n,k) = A144215(n,k) - A144215(n,k-1) for k > 0.

A144520 a(n) = A000055(n) - 1.

Original entry on oeis.org

0, 0, 0, 0, 1, 2, 5, 10, 22, 46, 105, 234, 550, 1300, 3158, 7740, 19319, 48628, 123866, 317954, 823064, 2144504, 5623755, 14828073, 39299896, 104636889, 279793449, 751065459, 2023443031, 5469566584, 14830871801, 40330829029, 109972410220, 300628862479

Offset: 0

N. J. A. Sloane, Dec 20 2008

nonn

Number of free trees with n nodes, each node with degree <= n-2. - Robert A. Russell, Jan 25 2023

Rebecca Neville, Graphs whose vertices are forests with bounded degree, Graph Theory Notes of New York, LIV (2008), 12-21. [Wayback Machine link]

Cf. A000055, A144528.

b[n_,i_,t_,k_] := b[n,i,t,k] = If[i<1, 0, Sum[Binomial[b[i-1,i-1,k,k]
  + j-1, j]* b[n-i*j, i-1, t-j, k], {j, 0, Min[t, n/i]}]];
  b[0,i_,t_,k_] = 1;
Join[{0,0,0,0,1}, Table[m = n - 3;
  gf[x_] := 1 + Sum[b[j - 1, j - 1, m, m] x^j, {j, 1, n}];
  ci[x_] := SymmetricGroupIndex[m + 1, x] /. x[i_] -> gf[x^i];
  SeriesCoefficient[Series[gf[x] - (gf[x]^2 - gf[x^2])/2 + x ci[x],
{x, 0, n}], n], {n,5,35}]] (* Robert A. Russell, Jan 25 2023 *)

a(n) = A144528(n,n-2). - Robert A. Russell, Jan 25 2023

A144527 a(n) = A000055(n) - 2.

Original entry on oeis.org

0, 1, 4, 9, 21, 45, 104, 233, 549, 1299, 3157, 7739, 19318, 48627, 123865, 317953, 823063, 2144503, 5623754, 14828072, 39299895, 104636888, 279793448, 751065458, 2023443030, 5469566583, 14830871800, 40330829028, 109972410219, 300628862478, 823779631719

Offset: 4

N. J. A. Sloane, Dec 20 2008

nonn

Number of free trees with n nodes, each node with degree <= n-3. - Robert A. Russell, Jan 25 2023

Rebecca Neville, Graphs whose vertices are forests with bounded degree, Graph Theory Notes of New York, LIV (2008), 12-21. [Wayback Machine link]

Cf. A000055, A144528.

b[n_,i_,t_,k_] := b[n,i,t,k] = If[i<1, 0, Sum[Binomial[b[i-1,i-1,k,k]
  + j-1, j]* b[n-i*j, i-1, t-j, k], {j, 0, Min[t, n/i]}]];
  b[0,i_,t_,k_] = 1;
Join[{0, 1}, Table[m = n - 4;
  gf[x_] := 1 + Sum[b[j - 1, j - 1, m, m] x^j, {j, 1, n}];
  ci[x_] := SymmetricGroupIndex[m + 1, x] /. x[i_] -> gf[x^i];
  SeriesCoefficient[Series[gf[x] - (gf[x]^2 - gf[x^2])/2 + x ci[x],
{x, 0, n}], n], {n,6,35}]] (* Robert A. Russell, Jan 25 2023 *)

a(n) = A144528(n,n-3). - Robert A. Russell, Jan 25 2023

A359392 Number of trees on n unlabeled nodes with all nodes of degree <= 7.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 6, 11, 23, 46, 104, 230, 539, 1270, 3081, 7536, 18785, 47207, 120074, 307739, 795426, 2069248, 5418014, 14263084, 37742929, 100331646, 267854040, 717863832, 1930888297, 5210968114, 14106844554

Offset: 0

Robert A. Russell, Dec 29 2022

nonn

R. Otter, The number of trees, Ann. of Math. (2) 49 (1948), 583-599 discusses asymptotics.
E. M. Rains and N. J. A. Sloane, On Cayley's Enumeration of Alkanes (or 4-Valent Trees), J. Integer Sequences, Vol. 2 (1999), Article 99.1.1.
Index entries for sequences related to trees

Column k=7 of A144528; A036722 (rooted trees).

n = 30; (* algorithm from Rains and Sloane *)
m = 7; (* maximum degree of node *)
CIm[f_, h_, x_] =  SymmetricGroupIndex[m-1, x] /. x[i_] -> f[h, x^i];
CI[f_, h_, x_] = SymmetricGroupIndex[m, x] /. x[i_] -> f[h, x^i];
T[-1, z_] := 1; T[h_, z_] :=  T[h, z] = Table[z^k, {k, 0, n}] .
  Take[CoefficientList[z^(n+1) + 1 + CIm[T, h-1, z] z, z], n+1];
ReplacePart[Sum[Take[CoefficientList[z^(n+1) + CI[T, h-1, z] z - CI[T, h-2, z] z - (T[h-1, z] - T[h-2, z]) (T[h-1, z] - 1), z], n+1], {h, 1, n/2}] + PadRight[{0, 1}, n+1] + Sum[Take[CoefficientList[z^(n+1) + (T[h, z]
  - T[h-1, z])^2/2 + (T[h, z^2] - T[h-1, z^2])/2, z], n+1], {h, 0, n/2}],
  1->1] (* end of original program *)
b[n_, i_, t_, k_] := b[n,i,t,k] = If[i<1, 0, Sum[Binomial[b[i-1,i-1,
  k,k] + j-1, j]* b[n-i*j, i-1, t-j, k], {j, 0, Min[t, n/i]}]];
b[0, i_, t_, k_] = 1; m = 6; (* m = maximum children *) n = 40;
gf[x_] = 1 + Sum[b[j-1,j-1,m,m]x^j,{j,1,n}]; (* G.f. for A036722 *)
ci[x_] = SymmetricGroupIndex[m+1, x] /. x[i_] -> gf[x^i];
CoefficientList[Normal[Series[gf[x] - (gf[x]^2 - gf[x^2])/2 + x ci[x],
{x, 0, n}]],x] (* Robert A. Russell, Jan 19 2023 *)

G.f.: B(x) - cycle_index(S2,-B(x)) + x * cycle_index(S7,B(x)) = B(x) - (B(x)^2 - B(x^2)) / 2 + x * (B(x)^7 + 21 B(x)^5 B(x^2) + 105 B(x)^3 B(x^2)^2 + 105 B(x) B(x^2)^3 + 70 B(x)^4 B(x^3) + 420 B(x)^2 B(x^2) B(x^3) + 210 B(x^2)^2 B(x^3) + 280 B(x) B(x^3)^2 + 210 B(x)^3 B(x^4) + 630 B(x) B(x^2) B(x^4) + 420 B(x^3) B(x^4) + 504 B(x)^2 B(x^5) + 504 B(x^2) B(x^5) + 840 B(x) B(x^6) + 720 B(x^7)) / 5040, where B(x) = 1 + x * cycle_index(S6,B(x)) = 1 + x * (B(x)^6 + 15*B(x)^4*B(x^2) + 45*B(x)^2*B(x^2)^2 + 15*B(x^2)^3 + 40*B(x)^3*B(x^3) + 120*B(x)*B(x^2)*B(x^3) + 40*B(x^3)^2 + 90*B(x)^2*B(x^4) + 90*B(x^2)*B(x^4) + 144*B(x)*B(x^5) + 120*B(x^6)) / 720 is the generating function for A036722. - Robert A. Russell, Jan 19 2023

cp's OEIS Frontend

A000602 Number of n-node unrooted quartic trees; number of n-carbon alkanes C(n)H(2n+2) ignoring stereoisomers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A000672 Number of 3-valent trees (= boron trees or binary trees) with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A144215 Triangle read by rows: T(n,k) is the number of forests on n unlabeled nodes with all nodes of degree <= k (n>=1, 0 <= k <= n-1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A036650 Number of 5-valent trees with n nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A036653 Number of 6-valent trees with n nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A238414 Triangle read by rows: T(n,k) is the number of trees with n vertices having maximum vertex degree k (n>=1, 0<=k<=n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

Extensions

A339788 Triangle read by rows: T(n,k) is the number of forests with n unlabeled vertices and maximum vertex degree k, (0 <= k < n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs