A303843 The number of unlabeled trees with n nodes rooted at 3 indistinguishable roots.

0, 0, 1, 4, 15, 51, 175, 573, 1866, 5978, 19000, 59859, 187503, 584012, 1811212, 5595239, 17228943, 52898764, 162013452, 495100454, 1510029296, 4597430832, 13975327501, 42422033217, 128606150706, 389423872694, 1177925775148, 3559477190797, 10746362772325

Offset

1,4

Comments

A unique path exists between any two of the roots. These will intersect at a single vertex which might coincide with one of the original roots. This intersecting vertex can be chosen as a root to which the other trees are attached. - Andrew Howroyd, May 03 2018

Links

Andrew Howroyd, Table of n, a(n) for n = 1..500

Formula

G.f.: g(x)*(g(x)^3 + 3*g(x)*g(x^2) + 2*g(x^3) + 3*g(x)^2 + 3*g(x^2))/(6*(1 + g(x)) where g(x)=T(x)/(1-T(x)) and T(x) is the g.f. of A000081. - Andrew Howroyd, May 03 2018

Example

a(3)=1 (all nodes are roots). a(4)=4: the linear tree has the non-root node either at a leaf or not, and the star tree has the non-root node either at the center or at a leaf.

Mathematica

m = 30; T[_] = 0;
Do[T[x_] = x Exp[Sum[T[x^k]/k, {k, 1, j}]] + O[x]^j // Normal, {j, 1, m}];
g[x_] = T[x]/(1 - T[x]) + O[x]^m // Normal;
g[x]((g[x]^3 + 3g[x]g[x^2] + 2g[x^3] + 3g[x]^2 + 3g[x^2])/(6(1 + g[x]))) + O[x]^m // CoefficientList[#, x]& // Rest (* Jean-François Alcover, Feb 16 2020, after Andrew Howroyd *)

Prog

(PARI) \\ here TreeGf is gf of A000081
TreeGf(N) = {my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}
seq(n) = {my(T=TreeGf(n)); my(g=T/(1-T)); T*(g^3 + 3*subst(g, x, x^2)*g + 2*subst(g, x, x^3) + 3*g^2 + 3*subst(g, x, x^2))/6}
concat([0, 0], Vec(seq(30))) \\ Andrew Howroyd, May 03 2018

Crossrefs

4th column of A294783.

Cf. A000081 (1-rooted), A303833 (2-rooted).

Sequence in context: A283276 A196835 A055218 * A107307 A240365 A005492

Adjacent sequences: A303840 A303841 A303842 * A303844 A303845 A303846

Keyword

nonn

Author

R. J. Mathar, May 01 2018

Extensions

Terms a(11) and beyond from Andrew Howroyd, May 03 2018

Status

approved