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

Author

Gus Wiseman, Aug 23 2017

Keywords

• nonn

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.

Examples

			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.
		

Links

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

Crossrefs

Cf. A000081, A003238, A291442.

Programs

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}]

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

Extensions

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