A331951 Number of binary trees with n internal nodes that contain the subtree [Z, [Z, U, U], [Z, U, U]].

0, 0, 0, 1, 2, 6, 20, 69, 246, 894, 3292, 12242, 45868, 172884, 654792, 2489981, 9500774, 36356214, 139471404, 536217814, 2065543012, 7970227084, 30801517624, 119198827218, 461863265660, 1791626278060, 6957151415832, 27041349974436, 105197526148312, 409575623758440, 1595836895778320

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

a(n) = A000108(n+1)-A226022(n). - 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

Cf. A000108.

Sequence in context: A363812 A163135 A359463 * A047036 A199248 A148478

Adjacent sequences: A331948 A331949 A331950 * A331952 A331953 A331954

Keyword

nonn,easy

Author

Marko Riedel, Mar 10 2020

Status

approved