A000671 Number of boron trees with n nodes, i.e. n-node rooted trees with degree <= 3 at root and out-degree <= 2 elsewhere.

0, 1, 1, 2, 4, 7, 14, 29, 60, 127, 275, 598, 1320, 2936, 6584, 14858, 33744, 76999, 176557, 406456, 939241, 2177573, 5064150, 11809632, 27610937, 64705623, 151966597, 357623905, 843176524, 1991439229, 4711115672, 11162025770, 26484061667, 62923251955

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

The subsequence of primes begins: 2, 7, 29, 127, 176557, 2177573, 151966597.

References

• 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. 450).
• 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).

Links

• T. D. Noe, Table of n, a(n) for n = 0..200
• 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.
• R. C. Read, Letter to N. J. A. Sloane, Oct. 29, 1976
• Index entries for sequences related to trees
• Index entries for sequences related to rooted trees

Crossrefs

Cf. A001190, A036657, A036658.

Programs

Maple

N := 40: t1 := G001190/x: G000671 := series(x*(1/3!)*(t1^3+3*subs(x=x^2,t1)*t1+2*subs(x=x^3,t1)), x, N); A000671 := n->coeff(G000671,x,n);
CI2 := proc(f) (1/2)*(f^2+subs(x=x^2,f)); end; CI3 := proc(f) (1/6)*(f^3+3*subs(x=x^2,f)*f+2*subs(x=x^3,f)); end;
N := 40: B0 := series(1 + x,x,N): G000671 := series(x*(CI3(B0) + CI3(G036656) + CI3(G036657) + CI2(B0)*(G036656 + G036657) + CI2(G036656)*(G036657 + B0) + CI2(G036657)*(B0 + G036656) + B0*G036656*G036657),x,N); A036658 := n->coeff(G036658,x,n);

Mathematica

terms = 32; (* B = g.f. for A001190 *) B[] = 0; Do[B[x] = x + (1/2)*(B[x]^2 + B[x^2]) + O[x]^terms // Normal, terms];
f[x_] = B[x]/x;
A[x_] = x*(1/3!)*(f[x]^3 + 3*f[x^2]*f[x] + 2*f[x^3]) + O[x]^terms;
CoefficientList[A[x], x] (* Jean-François Alcover, May 29 2012, from first g.f., updated Jan 10 2018 *)

Formula

G.f.: A(x) = x*(1/3!)*(f^3+3*subs(x=x^2, f)*f+2*subs(x=x^3, f)), where f = G001190(x)/x, G001190 = g.f. for A001190.

a(n) = A001190(n) + A036657(n) + A036658(n).

Another g.f.: let B0(x) = 1+x, G036656(x) = g.f. for A036656, G036657(x) = g.f. for A036657.

Then g.f.: x*(cycle_index(S3, B0)+cycle_index(S3, G036656)+cycle_index(S3, G036657)+cycle_index(S2, B0)*(G036656+G036657)+cycle_index(S2, G036656)*(G036657+B0)+cycle_index(S2, G036657)*(B0+G036656)+B0*G036656*G036657), where cycle_index(Sk, f) means apply the cycle index for the symmetric group S_k to f(x).

E.g., cycle_index(S2, f) = (1/2!)*(f^2+subs(x=x^2, f), cycle_index(S3, f) = (1/3!)*(f^3+3*subs(x=x^2, f)*f+2*subs(x=x^3, f)).