OFFSET
0,4
COMMENTS
A binary strict tree of weight n > 0 is either a single node of weight n, or an ordered pair of binary strict trees with strictly decreasing weights summing to n.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000
FORMULA
a(n) = 1 + Sum_{x + y = n, 0 < x < y < n} a(x) * a(y).
EXAMPLE
The a(5) = 6 binary strict trees: 5, (41), (32), ((31)1), ((21)2), (((21)1)1).
The a(6) = 10 binary strict trees:
6,
(51), (42),
((41)1), ((32)1), ((31)2),
(((31)1)1), (((21)2)1), (((21)1)2),
((((21)1)1)1).
MAPLE
a:= proc(n) option remember;
1+add(a(j)*a(n-j), j=1..(n-1)/2)
end:
seq(a(n), n=0..40); # Alois P. Heinz, Mar 06 2018
MATHEMATICA
k[n_]:=k[n]=1+Sum[Times@@k/@y, {y, Select[IntegerPartitions[n], Length[#]===2&&UnsameQ@@#&]}];
Array[k, 40]
(* Second program: *)
a[n_] := a[n] = 1 + Sum[a[j]*a[n - j], {j, 1, (n - 1)/2}];
a /@ Range[0, 40] (* Jean-François Alcover, May 13 2021, after Alois P. Heinz *)
PROG
(PARI) seq(n)={my(v=vector(n)); for(n=1, n, v[n] = 1 + sum(k=1, (n-1)\2, v[k]*v[n-k])); concat([1], v)} \\ Andrew Howroyd, Aug 25 2018
CROSSREFS
KEYWORD
nonn
AUTHOR
Gus Wiseman, Mar 05 2018
STATUS
approved