login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A291443 Number of leaf-balanced trees with n nodes. 15
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 (list; graph; refs; listen; history; text; internal format)
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: A164175 A066456 A066342 * 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 14 19:47 EDT 2020. Contains 336483 sequences. (Running on oeis4.)