A298204 Number of unlabeled rooted trees with n nodes in which all outdegrees are either 0, 1, or 3.

1, 1, 1, 2, 3, 5, 9, 16, 29, 55, 104, 200, 389, 763, 1507, 3002, 6010, 12102, 24484, 49751, 101475, 207723, 426542, 878451, 1813945, 3754918, 7790326, 16196629, 33739335, 70410401, 147187513, 308171861, 646188276, 1356847388, 2852809425, 6005542176

Offset: 1

Author

Gus Wiseman, Jan 14 2018

Keywords

• nonn

Examples

			The a(7) = 9 trees: ((((((o)))))), ((((ooo)))), (((oo(o)))), ((oo((o)))), ((o(o)(o))), (oo(((o)))), (oo(ooo)), (o(o)((o))), ((o)(o)(o)).
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..1000
• Gus Wiseman, Illustration of the first 8 terms.

Crossrefs

Cf. A000081, A000598, A001190, A001399, A004111, A014591, A032305, A273873, A292050, A295461, A298118, A298205.

Programs

Maple

b:= proc(n, i, v) option remember; `if`(n=0,
      `if`(v=0, 1, 0), `if`(i<1 or v<1 or n `if`(n<2, n, add(b(n-1$2, j), j=[1, 3])):
seq(a(n), n=1..40);  # Alois P. Heinz, Jan 30 2018

Mathematica

multing[n_,k_]:=Binomial[n+k-1,k];
a[n_]:=a[n]=If[n===1,1,Sum[Product[multing[a[x],Count[ptn,x]],{x,Union[ptn]}],{ptn,Select[IntegerPartitions[n-1],MemberQ[{1,3},Length[#]]&]}]];
Table[a[n],{n,40}]
(* Second program: *)
b[n_, i_, v_] := b[n, i, v] = If[n == 0,
     If[v == 0, 1, 0], If[i < 1 || v < 1 || n < v, 0,
     If[n == v, 1, Sum[Binomial[a[i] + j - 1, j]*
     b[n - i*j, i - 1, v - j], {j, 0, Min[n/i, v]}]]]];
a[n_] := If[n < 2, n, Sum[b[n - 1, n - 1, j], {j, {1, 3}}]];
Array[a, 40] (* Jean-François Alcover, May 10 2021, after Alois P. Heinz *)