3
$\begingroup$

I've been working on a combinatorics assignment, and while the last few questions had clever solutions which didn't involve functional equations and the use LIFT, I fear I'm at my end.

Given a Planted Tree $\ T$ with $n$ nodes let $h(T)$ be the number of nodes in $T$ with an even number of children. In particular, this includes the leaves. Find the average value of $h(T)$ among all PTs with $n$ nodes.

So far I've tried computing the value of $h(T)$ summed over PTs with $n$ nodes and sticking that into OEIS. While it seems to follow an exponential generating function, we haven't done those yet in class. Moreover the value I got for trees with 6 nodes differs, being 158 instead of 166, though that might easily be human error. Though I don't see how this will help me, even if it's true.

I then tried to write out a functional equation from a recursive formula. I ran into trouble when defining the weight function $h(T)$ recursively. I tried

$$ h(T) = \frac{1}{2}(1+(-1)^d) + \sum_{i=1}^{d}h(T_{d}) $$ It's not hard to see where the fails. The sum

$$ \sum_{T\in PT_{n}}x^{h(T)} $$

Won't even converge when you substitute $T=\{root, T_{1}, ... ,T_{d}\}$

So I'm stuck. Any help would be appreciated.

EDIT: I already know the number of PTs with n nodes. Which is why I'm so focused on finding the number of nodes with an even number of children across all PTs with n nodes.

$\endgroup$

1 Answer 1

1
$\begingroup$

Here is some enrichment material to complete this calculation. I assume you are working with labeled trees since you mention an exponential generating function. First note that these planted trees correspond to ordinary rooted trees with an extra node attached at the root.

The combinatorial class equation here is $$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}}\mathcal{T} = \mathcal{Z} \times \textsc{SET}(\mathcal{T}).$$

This gives the functional equation $$T(z) = z \exp T(z)$$ from which Lagrange inversion produces $$n! [z^n] T(z) = n^{n-1}.$$

Now if we wish to mark nodes with an even number of children we get $$\mathcal{T} = \mathcal{Z} \times \mathcal{U} \times \textsc{SET}_\mathrm{even}(\mathcal{T}) + \mathcal{Z} \times \textsc{SET}_\mathrm{odd}(\mathcal{T}).$$

Introduce $Q(z, u)$ for this specification so that $Q(z,1) = T(z).$ We obtain the functional equation $$Q(z) = uz \sum_{k\ge 0} \frac{Q(z)^{2k}}{(2k)!} + z \sum_{k\ge 0} \frac{Q(z)^{2k+1}}{(2k+1)!}.$$

Now to count the number of nodes with an even number of children introduce $$G(z) = \left. \frac{\partial}{\partial u} Q(z, u) \right|_{u=1}.$$

Differentiate the functional equation with respect to $u$ and put $u=1$ to obtain

$$G(z) = z \sum_{k\ge 0} \frac{T(z)^{2k}}{(2k)!} + z \sum_{k\ge 1} \frac{T(z)^{2k-1}}{(2k-1)!} G(z) + z \sum_{k\ge 0} \frac{T(z)^{2k}}{(2k)!} G(z).$$

This yields $$G(z) = z \sum_{k\ge 0} \frac{T(z)^{2k}}{(2k)!} + z \times G(z)\exp T(z)$$ which is $$G(z) = \frac{1}{2} z (\exp T(z) + \exp(-T(z)) + G(z) T(z)$$ or $$G(z) = \frac{1}{2} T(z) + \frac{1}{2} \frac{z^2}{T(z)} + G(z) T(z).$$

This finally produces $$G(z) = \frac{T(z)^2+z^2}{2T(z)(1-T(z))}.$$

Now to extract coefficiets from this we use the Cauchy Coefficient Formula. Start from $$n! [z^n] G(z) = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{T(z)^2+z^2}{2T(z)(1-T(z))} \; dz.$$

There are two components here.

First component. Put $T(z)=w$ so that $z=w/\exp(w) = w\exp(-w)$ and $dz = (\exp(-w) - w\exp(-w)) \; dw$ to get

$$\frac{n!}{2\pi i} \int_{|w|=\epsilon} \frac{\exp(w(n+1))}{w^{n+1}} \times \frac{w^2}{2w(1-w)} \times (\exp(-w) - w\exp(-w)) \; dw \\ = \frac{1}{2} \frac{n!}{2\pi i} \int_{|w|=\epsilon} \frac{\exp(wn)}{w^n} \; dw = \frac{1}{2} n! \frac{n^{n-1}}{(n-1)!} = \frac{1}{2} n^n.$$

Second component. Using the same substitution we obtain $$\frac{n!}{2\pi i} \int_{|w|=\epsilon} \frac{\exp(w(n+1))}{w^{n+1}} \times \frac{w^2\times \exp(-2w)}{2w(1-w)} \times (\exp(-w) - w\exp(-w)) \; dw \\ = \frac{1}{2} \frac{n!}{2\pi i} \int_{|w|=\epsilon} \frac{\exp(w(n-2))}{w^n} \; dw = \frac{1}{2} n! \frac{(n-2)^{n-1}}{(n-1)!} = \frac{1}{2} n\times (n-2)^{n-1}.$$

This gives the following sequence: $$1, 2, 15, 144, 1765, 26400, 466459, 9508352, \\ 219651849, 5671088640, \ldots $$

Conclusion. The average number of even outdegree nodes among the labeled trees on $n$ nodes is $$\frac{1}{n^{n-1}} \times \frac{1}{2} \left(n^n + n \times (n-2)^{n-1}\right)$$ which yields $$\frac{1}{2} n + \frac{1}{2} \frac{(n-2)^{n-1}}{n^{n-2}}.$$

To get the asymptotics re-write this like so: $$\frac{1}{2} n + \frac{1}{2} \times n \times \frac{(n-2)^{n-1}}{n^{n-1}} = \frac{1}{2} n + \frac{1}{2} \times n \times \left(1-\frac{2}{n}\right)^{n-1}.$$

This gives $$\frac{1}{2} \times n \times \left(1+\frac{1}{e^2}\right).$$ There is a bias towards even-degree nodes. This was also seen at this MSE link where unlabeled trees were studied.

Remark. These data were verified for small $n$ with the combstruct package.

with(combstruct);

gf :=
proc(n)
    option remember;
    local trees, evens;

    trees := { T= Union(Z, Prod(Z, Set(T, card >=1 ))),
               Z=Atom };

    evens :=
    proc(struct)
        local rval;

        if type(struct, function) then
            if op(0, struct) = Prod then
                return evens(op(2, struct))
            else
                rval := add(evens(op(q, struct)),
                            q=1..nops(struct));

                if type(nops(struct), even) then
                    return 1+rval;
                fi;

                return rval;
            fi;
        fi;

        return 1;
    end;

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

TGF := solve(T=z*exp(T), T);

q :=
proc(n)
    option remember;

    n!*coeftayl((TGF^2+z^2)/2/TGF/(1-TGF), z=0, n);
end;
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .