OFFSET
0,5
COMMENTS
The tree notation [Z, T1, T2] denotes an internal node and its two children T1 and T2. The notation U indicates a leaf.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..500
Marko Riedel et al., Math Stackexchange, How many ways are there to count binary trees with superleaves
FORMULA
G.f.: (sqrt(1 - 4*z + 4*z^4) - sqrt(1 - 4*z))/(2*z).
D-finite with recurrence -(n+1)*(n-3)*a(n) +(11*n^2-43*n+6)*a(n-1) +4*(-10*n^2+59*n-60)*a(n-2) +12*(2*n-5)*(2*n-11)*a(n-3) -4*(n-3)*(n-5)*a(n-4) +4*(7*n-29)*(n-6)*a(n-5) -24*(2*n-11)*(n-7)*a(n-6)=0. - R. J. Mathar, Mar 06 2022
EXAMPLE
a(3) = 1 because from the five trees total, four paths do not contain the required subtree. These trees are:
. [Z, U, [Z, U, [Z, U, U]]],
. [Z, U, [Z, [Z, U, U], U]],
. [Z, [Z, U, U], [Z, U, U]], (*)
. [Z, [Z, U, [Z, U, U]], U],
. [Z, [Z, [Z, U, U], U], U].
The starred one is the one that contributes.
PROG
(PARI) seq(n)={Vec((sqrt(1 - 4*x + 4*x^4 + O(x*x^n)) - sqrt(1 - 4*x + O(x*x^n)))/(2*x), -n)} \\ Andrew Howroyd, Mar 11 2020
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Marko Riedel, Mar 10 2020
STATUS
approved