A291443 Number of leaf-balanced trees with n nodes.

1, 1, 2, 4, 8, 14, 25, 41, 70, 116, 198, 331, 568, 957, 1635, 2776, 4757, 8144, 14089, 24428, 42707, 74895, 131983, 232895, 411725, 727434, 1284809, 2265997, 3992154, 7023718, 12347202, 21690274, 38096244, 66915426, 117591030, 206791336, 364037186, 641690280

Offset

1,3

Comments

An unlabeled rooted tree is leaf-balanced if every branch has the same number of leaves and every non-leaf rooted subtree is also leaf-balanced.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..50

Example

The a(5)=8 leaf-balanced trees are: ((((o)))), (((oo))), ((o(o))), ((ooo)), (o((o))), ((o)(o)), (oo(o)), (oooo). The tree (o(oo)) is not leaf-balanced.

Mathematica

allbal[n_]:=allbal[n]=If[n===1, {{}}, Join@@Function[c, Select[Union[Sort/@Tuples[allbal/@c]], SameQ@@(Count[#, {}, {0, Infinity}]&/@#)&]]/@IntegerPartitions[n-1]];
Table[Length[allbal[n]], {n, 15}]

Prog

(PARI)
PartitionProduct(p, f)={my(r=1, k=0); for(i=1, length(p), if(i==length(p) || p[i]!=p[i+1], r*=f(p[i], i-k); k=i)); r}
UPick(total, kinds)=binomial(total+kinds-1, kinds-1);
D(n)={my(v=vector(n)); v[1]=[1]; for(n=2, n, v[n]=vector(n-1); forpart(p=n-1, for(leaves=1, length(v[p[1]]), v[n][leaves*length(p)]+=PartitionProduct(p, (t, e)->UPick(e, v[t][leaves]))))); v}
a(n)=vecsum(D(n)[n]); \\ Andrew Howroyd, Sep 02 2017

Crossrefs

Cf. A000081, A003238, A291442.

Sequence in context: A066456 A066342 A340658 * A210145 A020956 A164393

Adjacent sequences: A291440 A291441 A291442 * A291444 A291445 A291446

Keyword

nonn

Author

Gus Wiseman, Aug 23 2017

Extensions

Terms a(26) and beyond from Andrew Howroyd, Sep 02 2017

Status

approved