A036657 -id:A036657 - cp's OEIS frontend

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

N. J. A. Sloane

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

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

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

Cf. A001190, A036657, A036658.

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

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

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

A088326 Triangle T(n,k) (n>=1, 1<=k<=n) read by rows, giving number of Piet Hut's "coat-hanger" arrangements: unlabeled forests of rooted trees with n edges and k connected components, in which the outdegree of each node is <= 2 and the symmetric group acts on the components.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 6, 5, 3, 1, 1, 11, 12, 6, 3, 1, 1, 23, 23, 14, 6, 3, 1, 1, 46, 52, 29, 15, 6, 3, 1, 1, 98, 109, 68, 31, 15, 6, 3, 1, 1, 207, 244, 147, 74, 32, 15, 6, 3, 1, 1, 451, 532, 337, 163, 76, 32, 15, 6, 3, 1, 1, 983, 1196, 757, 380, 169, 77, 32, 15, 6, 3, 1, 1

Offset: 1

N. J. A. Sloane, Nov 06 2003

			See A088325 for illustration.
Triangle begins
   1
   1  1
   2  1 1
   3  3 1 1
   6  5 3 1 1
  11 12 6 3 1 1
  ...

Alois P. Heinz, Rows n = 1..141, flattened

First 3 columns are A001190, A036657, A036658.
Row sums are A088325.
T(2n,n) gives A305839.

g:= proc(n) option remember; `if`(n<2, n, `if`(n::odd, 0,
      (t-> t*(1-t)/2)(g(n/2)))+add(g(i)*g(n-i), i=1..n/2))
    end:
b:= proc(n, i, p) option remember; `if`(p>n, 0, `if`(n=0, 1,
      `if`(min(i, p)<1, 0, add(b(n-i*j, i-1, p-j)*binomial(
       g(i+1)+j-1, j), j=0..min(n/i, p)))))
    end:
T:= (n, k)-> b(n$2, k):
seq(seq(T(n, k), k=1..n), n=1..14);  # Alois P. Heinz, Sep 11 2017

g[n_] := g[n] = If[n<2, n, If[OddQ[n], 0, Function[t, t*(1-t)/2][g[n/2]]] + Sum[g[i]*g[n - i], {i, 1, n/2}]];
b[n_, i_, p_] := b[n, i, p] = If[p>n, 0, If[n == 0, 1, If[Min[i, p]<1, 0, Sum[b[n-i*j, i-1, p-j]*Binomial[g[i+1]+j-1, j], {j, 0, Min[n/i, p]}]]]];
T[n_, k_] := b[n, n, k];
Table[T[n, k], {n, 1, 14}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jun 11 2018, after Alois P. Heinz *)

G.f.: exp( Sum_{k>=1} z^k*B(x^k)/k ), where B(x) = x + x^2 + 2*x^3 + 3*x^4 + 6*x^5 + 11*x^6 + ... = G001190(x)/x - 1 and G001190 is the g.f. for the Wedderburn-Etherington numbers A001190.

G.f.: Product_{j>=1} 1/(1-y*x^j)^A001190(j+1). - Alois P. Heinz, Sep 11 2017

More terms from Vladeta Jovovic, Nov 06 2003

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula