Find a decomposition and then an equation for the generating function for the class of rooted trees where each node has 0, 1, or 2 children.

Question

Find a decomposition and then an equation for the generating function for the class of rooted trees where each node has 0, 1, or 2 children.

how do you approach this problem?

Answer 1

The combinatorial species here seems to be $$\mathcal{T} = \mathcal{Z} + \mathcal{Z}(\mathfrak{M}_1(\mathcal{T}) + \mathfrak{M}_2(\mathcal{T})).$$ This is one of several interpretations of the question. The one we chose here is that the trees are not labelled and two trees that differ only in the left and right children being exchanged are considered the same.

Translating to generating functions we thus obtain $$T(z) = z \left(1 + T(z) + \frac{1}{2} T(z)^2 + \frac{1}{2} T(z^2) \right).$$

Here we have used two simple cycle indices namely $$Z(S_1) = a_1 \quad\text{and}\quad Z(S_2) = \frac{1}{2} a_1^2 + \frac{1}{2} a_2.$$ Solving this recurrence produces the sequence $$1, 1, 2, 3, 6, 11, 23, 46, 98, 207, 451, 983, 2179, 4850, 10905, \ldots$$

which points us to the OEIS entry A036656 and to the MathWorld entry for weakly binary trees, where an amazing variety of additional material may be found. Remark. It appears that these links impose an additional condition which is that the root has exactly one outgoing edge. There is however clearly a bijection between what we have calculated and those trees, which is obtained by adding / removing the root node with outdegree one. This simply means that the sequence index in the linked pages starts at two instead of one, because we must add that one root node.

The code for calculating the sequence is this:

vals :=
proc(mx)
        local T, rec, sol, vars;

        vars := [seq(cat(`a`,k),k=1..mx)];
        T := add(cat(`a`, k)*z^k, k=1..mx);

        rec := expand(z*(1+T+1/2*T^2+1/2*subs(z=z^2, T)));
        sol := solve([seq(cat(`a`, k)=
        coeftayl(rec, z=0, k), k=1..mx)], vars); 

        subs(op(1, sol), vars);
end;

Addendum. A better way to calculate $t_n = [z^n] T(z)$ is to use $t_1= 1$ and turn the defining relation for the generating function into a recurrence which gives for $n\ge 2$ that $$t_n = t_{n-1} + \frac{1}{2}\sum_{k=1}^{n-2} t_k t_{n-1-k} + [n-1\bmod 2=0] \times \frac{1}{2} t_{(n-1)/2}.$$ This lets us quickly extend the sequence e.g. to $$1, 1, 2, 3, 6, 11, 23, 46, 98, 207, 451, 983, 2179, 4850, 10905, 24631, 56011, 127912, 293547,\ldots $$ Here is an implementation of this recursive formula.

vals_rec :=
proc(n)
        option remember;
        local s, a;

        if n=1 then return 1 fi;

        s := vals_rec(n-1);

        for a to n-2 do
            s := s + 1/2*vals_rec(a)*vals_rec(n-1-a) 
        od; 

        if type(n-1, even) then
           s := s + 1/2*vals_rec((n-1)/2);
        fi;

        s;
end;