login
Number of leaf-balanced trees with n nodes.
15

%I #10 Sep 03 2017 17:16:12

%S 1,1,2,4,8,14,25,41,70,116,198,331,568,957,1635,2776,4757,8144,14089,

%T 24428,42707,74895,131983,232895,411725,727434,1284809,2265997,

%U 3992154,7023718,12347202,21690274,38096244,66915426,117591030,206791336,364037186,641690280

%N Number of leaf-balanced trees with n nodes.

%C 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.

%H Andrew Howroyd, <a href="/A291443/b291443.txt">Table of n, a(n) for n = 1..50</a>

%e 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.

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

%t Table[Length[allbal[n]],{n,15}]

%o (PARI)

%o 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}

%o UPick(total,kinds)=binomial(total+kinds-1,kinds-1);

%o 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}

%o a(n)=vecsum(D(n)[n]); \\ _Andrew Howroyd_, Sep 02 2017

%Y Cf. A000081, A003238, A291442.

%K nonn

%O 1,3

%A _Gus Wiseman_, Aug 23 2017

%E Terms a(26) and beyond from _Andrew Howroyd_, Sep 02 2017