login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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