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,5

Links

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

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

Example

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

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

Prog

(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

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.

Sequence in context: A326793 A026580 A092247 * A108360 A051163 A051450

Adjacent sequences: A331230 A331231 A331232 * A331234 A331235 A331236

Keyword

nonn

Author

Gus Wiseman, Jan 21 2020

Status

approved