Counting restricted ordered rooted trees by the number of leaves and non-leaves

786 Views Asked by At

I have proved that the number of ordered rooted unlabeled trees on $n+1$ vertices with $j$ leaves is $\dfrac{1}{n+1}\binom{n+1}{j}\binom{n-1}{j}$. I did this by writing a recurrence using that fact that removing a leaf gives either a tree with the same number of leaves and one fewer vertex or a tree with one fewer vertex and one fewer leaf.

I want to "extend" this to count trees with $n+k-1$ vertices, $n-1$ leaves, and the property that no vertex has exactly one child.

I tried setting up a recurrence for this, where when I delete a leaf, I either get a good tree with one fewer leaf and vertex, or I get a bad tree with exactly one vertex with one child, and I can count bad trees by just counting the edges of the bad tree with the vertex deleted and the two edges on it joined into a single edge. However, this fails when the bad vertex is the root, since then it does not have degree $2$, and I can't seem to fix the recurrence to get the correct answer, which is supposed to be $\dfrac{1}{n+k-1}\binom{n+k-1}{n-1}\binom{n-3}{n-k-2}$. Is there a better way to form the recurrence?

1

There are 1 best solutions below

9
On

Here is a contribution using basic complex variables.

The species equation for ordered rooted trees where no vertex has exactly one child with leaves marked is $$\mathcal{T} = \mathcal{Z}\mathcal{U} + \mathcal{Z} \mathfrak{S}_{\ge 2}(\mathcal{T}) \quad\text{or}\quad \mathcal{T} = \mathcal{Z}\mathcal{U} + \mathcal{Z} \frac{\mathcal{T}^2}{1-\mathcal{T}}.$$

This yields the functional equation for the generating function $T(z)$ $$T(z) = zu + z\frac{T^2(z)}{1-T(z)}$$ or $$z = \frac{T(z)}{u+T^2(z)/(1-T(z))} = \frac{T(z)(1-T(z))}{T^2(z)+u(1-T(z))}.$$

We seek $$T_n(u) = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} T(z) \; dz.$$ and will compute this by Lagrange inversion.

Put $w=T(z)$ so that $$dz = \left(\frac{1-2w}{w^2+u(1-w)} -\frac{w(1-w)}{(w^2+u(1-w))^2}(2w-u)\right) dw.$$

to get the two integrals $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(w^2+u(1-w))^{n+1}}{w^{n+1}(1-w)^{n+1}} \times w\times \frac{1-2w}{w^2+u(1-w)} \; dw.$$ and $$-\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(w^2+u(1-w))^{n+1}}{w^{n+1}(1-w)^{n+1}} \times w\times \frac{w(1-w)}{(w^2+u(1-w))^2}(2w-u) \; dw.$$

This simplifies to give four pieces, piece $A_1$ is (write $1-2w = -w + (1-w)$) $$- \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(w^2+u(1-w))^{n}}{w^{n-1}(1-w)^{n+1}} \; dw$$ and piece $A_2$ is $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(w^2+u(1-w))^{n}}{w^{n}(1-w)^{n}} \; dw.$$

Piece $B$ is $$-\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(w^2+u(1-w))^{n-1}}{w^{n-1}(1-w)^{n}} (2w-u) \; dw.$$

This gives piece $B_1$ $$-2\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(w^2+u(1-w))^{n-1}}{w^{n-2}(1-w)^{n}} \; dw$$ and piece $B_2$ $$u\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(w^2+u(1-w))^{n-1}}{w^{n-1}(1-w)^{n}}\; dw.$$

Recall that the leaves are also marked with $z$ in addition to $u$ so that we may have up to $q=n-1$ leaves. Extracting the coefficient from $A_1$ yields $$- {n\choose q}\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{w^{2n-2q} (1-w)^q}{w^{n-1}(1-w)^{n+1}} \; dw$$ and piece $A_2$ yields $${n\choose q}\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{w^{2n-2q} (1-w)^q}{w^{n}(1-w)^{n}} \; dw.$$

This simplifies to $$-{n\choose q}\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{2q-n-1}(1-w)^{n-q+1}} \; dw = -{n\choose q} {q-2\choose n-q}$$ and $${n\choose q}\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{2q-n}(1-w)^{n-q}} \; dw = {n\choose q} {q-2\choose n-q-1}.$$

Extracting the coefficient from $B_1$ yields $$-2{n-1\choose q}\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{w^{2n-2q-2} (1-w)^q}{w^{n-2}(1-w)^{n}} \; dw$$ and piece $B_2$ yields $${n-1\choose q-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{w^{2n-2q}(1-w)^{q-1}}{w^{n-1}(1-w)^{n}}\; dw.$$

This simplifies to $$-2{n-1\choose q}\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{2q-n}(1-w)^{n-q}} \; dw = -2{n-1\choose q} {q-2\choose n-q-1}$$ and piece $B_2$ yields $${n-1\choose q-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{2q-n-1}(1-w)^{n-q+1}}\; dw = {n-1\choose q-1} {q-2\choose n-q}.$$

Collecting everything we obtain the formula

$${n-1\choose q-1} {q-2\choose n-q} \left(1-2\frac{n-q}{q}\frac{n-q}{2q-n-1} +\frac{n}{q}\frac{n-q}{2q-n-1}-\frac{n}{q}\right)$$ which is $$\frac{1}{2q-n-1} \frac{n-q}{q}{n-1\choose q-1} {q-2\choose n-q}$$ or $$\frac{1}{2q-n-1} {n-1\choose q} {q-2\choose n-q}.$$

In the question from the OP we have $n=n'+k'-1$ and $q=n'-1$ which yields $$\frac{1}{2n'-2-n'-k'+1-1} {n'+k'-2\choose n'-1} {n'-1-2\choose k'}$$ or $$\frac{1}{n'-k'-2} {n'+k'-2\choose n'-1} {n'-3 \choose n'-k'-3}$$ which is $$\frac{1}{k'} {n'+k'-2\choose n'-1} {n'-3 \choose n'-k'-2}$$ which finally yields $$\frac{1}{n'+k'-1} {n'+k'-1\choose n'-1} {n'-3 \choose n'-k'-2},$$ confirming the result conjectured by the OP.

Addendum. The formula $$\frac{1}{2q-n-1} {n-1\choose q} {q-2\choose n-q}$$

has the problem that when $n$ is odd and $q=\lfloor n/2\rfloor+1$ we get a singularity because $2q-n-1=0$ but this value of $q$ is included in the generating function. Therefore it is best to do some hypergeometric refactoring (same as above), obtaining

$$\frac{1}{2q-n-1} {n-1\choose q} \frac{(q-2)!}{(2q-n-2)! (n-q)!} = {n-1\choose q} \frac{(q-2)!}{(2q-n-1)! (n-q)!} \\ = \frac{1}{n-q} {n-1\choose q} {q-2\choose n-q-1}.$$

Now because $q$ ranges from $\lfloor n/2\rfloor+1$ to $n-1$ we have that for $n\ge 2$ $$T_n(u) = \sum_{q=\lfloor n/2\rfloor+1}^{n-1} \frac{1}{n-q} {n-1\choose q} {q-2\choose n-q-1} u^q.$$

This gives e.g. for $n=8$ the generating function $$T_8(u) = {u}^{7}+14\,{u}^{6}+21\,{u}^{5}$$ and for $n=9$ $$T_9(u) = {u}^{8}+20\,{u}^{7}+56\,{u}^{6}+14\,{u}^{5}.$$

The sequence $T_n(1)$ removes the classification according to the number of leaves and simply counts ordered rooted trees with no vertex with one child, giving $$0, 1, 1, 3, 6, 15, 36, 91, 232, 603, 1585, \ldots$$ which is OEIS A005043 where additional reference material awaits. (This sequence would appear to be one of the more important ones in combinatorics.)

Observe that for small $n$ e.g. $n\le 12$ the generating function $T_n(u)$ can be computed with Maple's combstruct package. This gives e.g. $$T_{12}(u) = {u}^{11}+44\,{u}^{10}+385\,{u}^{9}+825\,{u}^{8}+330\,{u}^{7}.$$

This is the Maple code.

with(combstruct);

gf_cs :=
proc(n)
    option remember;
    local trees, leaves;

    trees := { T=Union(Prod(Z, U),
                       Prod(Z, Sequence(T, 2<= card))),
               Z=Atom, U=Epsilon };

    leaves :=
    proc(struct)
        if type(struct, function) then
            return add(leaves(op(q, struct)), q=1..nops(struct));
        fi;

        if struct = Z then return 0 fi;
        return 1;
    end;

    add(u^leaves(t), t in allstructs([T, trees], size=n));
end;

The command

> seq(count([T, trees], size=n), n=1..12);

will instantly produce the sequence $T_n(1)$ from above. Another method to compute the $T_n(u)$ with Maple is to solve the functional equation which is only a quadratic and compute the coefficients of the Taylor series.

Addendum II. Another hypergeometric refactoring will produce the formula $$T_n(u) = \frac{1}{n} \sum_{q=\lfloor n/2\rfloor+1}^{n-1} {n\choose q} {q-2\choose n-q-1} u^q,$$ also for $n \ge 2,$ which incidentally suggest differentiating the functional equation.