A331233 Number of unlabeled rooted trees with n vertices and more than two branches of the root.

0, 0, 0, 1, 2, 5, 12, 30, 75, 194, 501, 1317, 3485, 9302, 24976, 67500, 183290, 500094, 1369939, 3766831, 10391722, 28756022, 79794407, 221987348, 619019808, 1729924110, 4844242273, 13590663071, 38195831829, 107523305566, 303148601795, 855922155734, 2419923253795

Offset: 1

Author

Gus Wiseman, Jan 21 2020

Keywords

• nonn

Examples

			The a(4) = 1 through a(7) = 12 rooted trees:
  (ooo)  (oooo)   (ooooo)    (oooooo)
         (oo(o))  (oo(oo))   (oo(ooo))
                  (ooo(o))   (ooo(oo))
                  (o(o)(o))  (oooo(o))
                  (oo((o)))  (o(o)(oo))
                             (oo((oo)))
                             (oo(o)(o))
                             (oo(o(o)))
                             (ooo((o)))
                             ((o)(o)(o))
                             (o(o)((o)))
                             (oo(((o))))
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..1000 (first 500 terms from Andrew Howroyd)

Crossrefs

The Matula-Goebel numbers of these trees are given by A033942.

The series-reduced case is A331488.

The lone-child-avoiding case is (also) A331488.

The labeled version is A331577.

Unlabeled rooted trees are counted by A000081.

Cf. A001678, A001679, A004111, A033185, A060313, A206429, A331490, A331578.

Programs

Maple

g:= proc(n, i, t) option remember; `if`(n=0, `if`(t=0, 1, 0),
      `if`(i<1, 0, add(binomial(g(i-1$2, 0)+j-1, j)*
         g(n-i*j, i-1, max(0, t-j)), j=0..n/i)))
    end:
a:= n-> g(n-1$2, 3):
seq(a(n), n=1..40);  # Alois P. Heinz, Jan 22 2020

Mathematica

urt[n_]:=Join@@Table[Union[Sort/@Tuples[urt/@ptn]],{ptn,IntegerPartitions[n-1]}];
Table[Length[Select[urt[n],Length[#]>2&]],{n,10}]
(* Second program: *)
g[n_, i_, t_] := g[n, i, t] = If[n == 0, If[t == 0, 1, 0],
     If[i < 1, 0, Sum[Binomial[g[i - 1, i - 1, 0] + j - 1, j]*
     g[n - i*j, i - 1, Max[0, t - j]], {j, 0, n/i}]]];
a[n_] := g[n-1, n-1, 3];
Array[a, 40] (* Jean-François Alcover, May 20 2021, after Alois P. Heinz *)

PARI

\\ TreeGf gives 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(g=TreeGf(n)); Vec(g - x*(1 + g + (g^2 + subst(g, x, x^2))/2), -n)} \\ Andrew Howroyd, Jan 22 2020

Formula

For n > 1, a(n) = Sum_{k > 2} A033185(n - 1, k).

G.f.: f(x) - x*(1 + f(x) + (f(x)^2 + f(x^2))/2) where f(x) is the g.f. of A000081. - Andrew Howroyd, Jan 22 2020