login
A301470
Signed recurrence over enriched r-trees: a(n) = (-1)^n + Sum_y Product_{i in y} a(y) where the sum is over all integer partitions of n - 1.
4
1, 0, 1, 0, 1, 1, 2, 3, 5, 9, 15, 27, 47, 87, 155, 288, 524, 983, 1813, 3434, 6396, 12174, 22891, 43810, 82925, 159432, 303559, 585966, 1121446, 2171341, 4172932, 8106485, 15635332, 30445899, 58925280, 115014681, 223210718, 436603718, 849480835, 1664740873
OFFSET
0,7
LINKS
FORMULA
O.g.f.: 1/(1 + x) + x Product_{i > 0} 1/(1 - a(i) x^i).
a(n) = Sum_t (-1)^w(t) where the sum is over all enriched r-trees of size n and w(t) is the sum of leaves of t.
MAPLE
b:= proc(n, i) option remember; `if`(n=0, 1,
`if`(i<1, 0, b(n, i-1)+a(i)*b(n-i, min(n-i, i))))
end:
a:= n-> `if`(n<2, 1-n, b(n-2$2)+b(n-1, n-2)):
seq(a(n), n=0..45); # Alois P. Heinz, Jun 23 2018
MATHEMATICA
a[n_]:=a[n]=(-1)^n+Sum[Times@@a/@y, {y, IntegerPartitions[n-1]}];
Array[a, 30]
(* Second program: *)
b[n_, i_] := b[n, i] = If[n == 0, 1,
If[i < 1, 0, b[n, i - 1] + a[i] b[n - i, Min[n - i, i]]]];
a[n_] := If[n < 2, 1 - n, b[n - 2, n - 2] + b[n - 1, n - 2]];
a /@ Range[0, 45] (* Jean-François Alcover, May 20 2021, after Alois P. Heinz *)
KEYWORD
nonn
AUTHOR
Gus Wiseman, Mar 21 2018
STATUS
approved