login
Number of leaf-balanced rooted plane trees with n nodes.
6

%I #12 Dec 14 2020 01:37:32

%S 1,1,2,5,12,27,59,128,277,597,1280,2730,5794,12248,25836,54508,115222,

%T 244144,518104,1099499,2330326,4930089,10415135,21992400,46470911,

%U 98353146,208580686,443186181,942988423,2007981801,4276830431,9109431322,19404918449,41357252072,88236092543

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

%C A rooted plane tree is leaf-balanced if every branch of the root has the same number of leaves, and every branch of the root is itself leaf-balanced.

%H Andrew Howroyd, <a href="/A304175/b304175.txt">Table of n, a(n) for n = 1..500</a>

%e The a(5) = 12 leaf-balanced plane trees:

%e ((((o)))), (((oo))), (((o)o)), ((o(o))), ((ooo)),

%e (((o))o), (o((o))), ((o)(o)),

%e ((o)oo), (o(o)o), (oo(o)),

%e (oooo).

%e Missing from this list are ((oo)o) and (o(oo)).

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

%t Table[Length[lbplane[n]],{n,10}]

%o (PARI) seq(n)={my(v=vector(n)); v[1]=x/(1-x) + O(x*x^n); for(k=2, n, v[k]=x*sumdiv(k, d, if(d<k, v[d]^(k/d)))/(1-x) ); Vec(vecsum(v) + O(x*x^n))} \\ _Andrew Howroyd_, Dec 13 2020

%Y Cf. A000081, A000108, A001003, A001006, A003238, A007853, A126120, A291442, A291443, A304173.

%K nonn

%O 1,3

%A _Gus Wiseman_, Aug 16 2018

%E Terms a(17) and beyond from _Andrew Howroyd_, Dec 13 2020