How many ways are there to count binary trees with "superleaves"

Question

From what I read, the number of binary trees can be counted with respect to their internal nodes using the Catalan numbers:

$$ T(z) = \frac{1-\sqrt{1-4z}}{2z} $$

Taking the Taylor series of $T(z)$ at $z=0$, we get the series:

$$ 1 + z + 2z^2 + 5z^3 + 14z^4+.... $$

If we let $a_n$ denote the coefficients of the series, we have one binary tree with no internal node ($a_0=1$ at $z^0$), one binary tree with one internal node ($a_1=1$ at $z^1$) and two binary trees with two internal nodes ($a_2=2$ at $z^2$) and five binary trees with three internal nodes ($a_3=5$ at $z^3$) and so on and so forth ...

I came across this problem that asks how many binary trees have "superleaves". I will state the definition of "superleaf" below as best as I can. The definition may be a bit confusing since a "superleaf" is not really a leaf, but a subtree of a binary tree.

A superleaf is a subtree in a binary tree. The superleaf subtree has three internal nodes and four external nodes.

The root of the superleaf subtree is an internal node whose immediate children are two internal nodes. The two child internal nodes in turn are connected to the four external nodes (where the external nodes are leaves of the binary tree and are not connected with any node below them).

Counting binary trees in terms of their internal nodes, the number of superleaves is:

$$ a_0 = 0 \text{ for $z_0$, i.e. no binary tree with superleaf for binary trees with $0$ internal nodes} $$ $$ a_1 = 0 \text{ for $z_1$, i.e. no binary tree with superleaf for binary trees with $1$ internal nodes} $$ $$ a_2 = 0 \text{ for $z_2$, i.e. no binary tree with superleaf for binary trees with $2$ internal nodes} $$ $$ a_3 = 1 \text{ for $z_3$, i.e. $1$ binary tree with superleaf for binary trees with $3$ internal nodes} $$ $$ a_4 = 2 \text{ for $z_4$, i.e. $2$ binary trees with superleaves for binary trees with $4$ internal nodes} $$ $$ a_5 = 6 \text{ for $z_5$, i.e. $6$ binary trees with superleaves for binary trees with $5$ internal nodes} $$

But I could not find out a generating function for binary trees with superleaves... Any help?

Answer 1

We start with the case of counting binary trees that have no superleaves. This is from first principles

$$T(z) = 1 + z \times (T(z)-z^3)^2.$$

Here we observe that the recursive construction generates the superleaf at depth two, so it must be removed. We then have for the generating function the closed form

$$T(z) - z^3 = \frac{1-\sqrt{1-4z+4z^4}}{2z}.$$

Now recall the OGF of the Catalan numbers

$$C(z) = \frac{1-\sqrt{1-4z}}{2z}.$$

It follows that the desired generating function $Q(z)$ of binary trees containing superleaves is the difference of these two, i.e.

$$\bbox[5px,border:2px solid #00A000]{ Q(z) = \frac{\sqrt{1-4z+4z^4}-\sqrt{1-4z}}{2z}.}$$

Starting at $n=1$ we obtain the sequence

$$0, 0, 1, 2, 6, 20, 69, 246, 894, 3292, 12242, 45868, \\ 172884, 654792, 2489981, \ldots$$

which is not in the OEIS, and that's why we have some Maple code to verify these numbers by enumeration, which is shown below.

BINTREE :=
proc(n)
option remember;
local left, right, m, res;

    if n=0 then return [U] fi;

    res := [];

    for m from 0 to n-1 do
        for left in BINTREE(m) do
            for right in BINTREE(n-1-m) do
                res := [op(res), [Z, left,right]];
            od;
        od;
    od;

    res;
end;

FIND_SL :=
proc(tree)

    if tree = U then return false fi;

    if tree = [Z, [Z, U, U], [Z, U, U]] then
        return true;
    fi;

    return (FIND_SL(op(2, tree)) or FIND_SL(op(3, tree)));
end;

COUNT :=
proc(n)
option remember;
local idx;

    idx := map(FIND_SL, BINTREE(n));
    numboccur(idx, true);
end;

T := op(2, [solve(TF = 1 + z*(TF-z^3)^2, TF)]);

C := op(2, [solve(TF = 1 + z*TF^2, TF)]);

COUNTX := n -> coeftayl(C-(T-z^3), z=0, n);