login
A301467
Number of enriched r-trees of size n with no empty subtrees.
25
1, 2, 4, 8, 20, 48, 136, 360, 1040, 2944, 8704, 25280, 76320, 226720, 692992, 2096640, 6470016, 19799936, 61713152, 190683520, 598033152, 1863995392, 5879859200, 18438913536, 58464724992, 184356152832, 586898946048, 1859875518464, 5941384080384, 18901502482432
OFFSET
1,2
COMMENTS
An enriched r-tree of size n > 0 with no empty subtrees is either a single node of size n, or a finite nonempty sequence of enriched r-trees with no empty subtrees and with weakly decreasing sizes summing to n - 1.
LINKS
FORMULA
O.g.f.: x^2/(1 - x) + x Product_{i > 0} 1/(1 - a(i) x^i).
EXAMPLE
The a(4) = 8 enriched r-trees with no empty subtrees: 4, (3), (21), ((2)), (111), ((11)), ((1)1), (((1))).
The a(5) = 20 enriched r-trees with no empty subtrees:
5,
(4), ((3)), ((21)), (((2))), ((111)), (((11))), (((1)1)), ((((1)))),
(31), (22), (2(1)), ((2)1), ((1)2), ((11)1), ((1)(1)), (((1))1),
(211), ((1)11),
(1111).
MAPLE
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
add(b(n-i*j, i-1)* a(i)^j, j=0..n/i)))
end:
a:= n-> `if`(n<2, n, 1+b(n-1$2)):
seq(a(n), n=1..30); # Alois P. Heinz, Jun 21 2018
MATHEMATICA
pert[n_]:=pert[n]=If[n===1, 1, 1+Sum[Times@@pert/@y, {y, IntegerPartitions[n-1]}]];
Array[pert, 30]
(* Second program: *)
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0,
Sum[b[n - i*j, i - 1] a[i]^j, {j, 0, n/i}]]];
a[n_] := a[n] = If[n < 2, n, 1 + b[n-1, n-1]];
Array[a, 30] (* Jean-François Alcover, May 09 2021, after Alois P. Heinz *)
PROG
(PARI) seq(n)={my(v=vector(n)); v[1]=1; for(n=2, n, v[n] = 1 + polcoef(1/prod(k=1, n-1, 1 - v[k]*x^k + O(x^n)), n-1)); v} \\ Andrew Howroyd, Aug 26 2018
KEYWORD
nonn
AUTHOR
Gus Wiseman, Mar 21 2018
STATUS
approved