parity bias for trees?

Question

Let $t(n)$ denote the number of unlabeled unrooted trees on n vertices, e.g. $t(4)=2$ . Next denote by $\operatorname{even}(n)$ the number of such trees having an even number of endpoints.

Similarly, define $\operatorname{odd}(n)$ for an odd number of endpoints, e.g. $\operatorname{even}(4) = \operatorname{odd}(4) = 1$ .

Other examples are: $\operatorname{even}(8) = 12 > 11 = \operatorname{odd}(8)$ and $\operatorname{even}(9) = 25 > \operatorname{odd}(9) = 22$. In fact, for small number of vertices, it always seems to be the case that $\operatorname{even}(n)$ is at least as large as $\operatorname{odd}(n)$ .

Questions:

(1) Are there any values of $n$ for which $\operatorname{odd}(n) > \operatorname{even}(n)$ ?

(2) Is there a generating function $T(x,y)$ for unlabeled unrooted trees according to the number of endpoints?

Thanks.

Answer 1

Here is a solution to the rooted case while we wait for the experts to join in.

The species of rooted unlabelled trees with endpoints marked has specification $$\mathcal{T} = \mathcal{U}\mathcal{Z} + \mathcal{Z}\mathfrak{M}_{\ge 1}(\mathcal{T}).$$

This gives the functional equation for the generating function $$T(z, u) = uz+ z\left(-1+\exp\left(\sum_{l\ge 1} \frac{T(z^l, u^l)}{l} \right)\right).$$ An alternate form is $$T(z, u) = uz+ z\left(-1+\prod_{l\ge 1} \exp\left(\frac{T(z^l, u^l)}{l} \right)\right).$$

This gives the following recurrence for the coefficients $T_n.$ We have $T_1 = u$ and for $n\ge 2$ we have $$T_n = [z^{n-1}] \left(-1 + \exp\left(\sum_{l\ge 1} \frac{T(z^l, u^l)}{l}\right)\right).$$ These coeffients are polynomials in $u.$

Start by observing that if $$A(z, u) = \sum_{n\ge 1} A_n z^n = \sum_{l\ge 1} \frac{T(z^l, u^l)}{l}$$ then $$A_n = \sum_{l|n} \frac{\left.T_{n/l}\right|_{u=u^l}}{l}.$$

Re-writing the functional equation in terms of $A(z)$ yields $$T(z, u) = uz + z(-1 + \exp A(z, u))$$ and differentiating with respect to $z$ we get $$T'(z, u) = u-1 + \exp A(z, u) + z \exp A(z, u) A'(z, u)$$ which is $$T'(z, u) = u-1 + \frac{T(z,u)}{z} - u + 1 + (T(z, u)- uz + z) A'(z,u)$$ or $$z T'(z, u) = T(z, u) + z (T(z, u)- uz + z) A'(z,u).$$

Extracting cofficients we obtain $$n T_n = T_n + [z^{n-1}] (T(z, u)- uz + z) A'(z,u) \\ = T_n + (1-u) [z^{n-2}] A'(z, u) + \sum_{k=0}^{n-2} T_{n-1-k} (k+1) A_{k+1} \\ = T_n + (1-u) (n-1) A_{n-1} + \sum_{k=0}^{n-2} (k+1) A_{k+1} T_{n-1-k}.$$

This gives for $T_n$ with $n\ge 2$ the recurrence $$T_n = (1-u) A_{n-1} + \frac{1}{n-1} \sum_{k=0}^{n-2} (k+1) A_{k+1} T_{n-1-k}.$$

Note that the $A_n$ are defined recursively in terms of the $T_n$ as above.

Setting $u=1$ in the polynomials $T_n$ yields the sequence: $$1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, \\ 87811, 235381, 634847, 1721159, 4688676, 12826228,\ldots$$ which points us to OEIS A000081 where we learn that we indeed have the correct values.

Here are the first few distributions of the number of endpoints starting with the tree on one node: $$u \\u \\{u}^{2}+u \\{u}^{3}+2\,{u}^{2}+u \\{u}^{4}+3\,{u}^{3}+4\,{u}^{2}+u \\{u}^{5}+4\,{u}^{4}+8\,{u}^{3}+6\,{u}^{2}+u \\{u}^{6}+5\,{u}^{5}+14\,{u}^{4}+18\,{u}^{3}+9\,{u}^{2}+u$$

Now evidently the count of trees with an even number of endpoints is given by $$\frac{1}{2} \left(\left.T_n\right|_{u=1}+ \left.T_n\right|_{u=-1}\right)$$ and for odd number of endpoints $$\frac{1}{2} \left(\left.T_n\right|_{u=1}- \left.T_n\right|_{u=-1}\right).$$

This gives the following sequence of counts for even number of endpoints: $$0, 0, 1, 2, 5, 10, 24, 57, 144, 360, 923, 2382, 6246, 16486, 43917, \\ 117692, 317447, 860574, 2344396, 6413119, \ldots$$ and for odd number of endpoints $$1, 1, 1, 2, 4, 10, 24, 58, 142, 359, 919, 2384, 6240, 16487, 43894, \\ 117689, 317400, 860585, 2344280, 6413109, \ldots$$

The difference between these two goes like this: $$ -1, -1, 0, 0, 1, 0, 0, -1, 2, 1, 4, -2, 6, -1, 23, 3, 47, -11, 116, \\ 10, 340, 13, 783, -14, 2181, 248, 5811, 321, 15026, 1335, 41660, \\ 4938, 111237, 11384, 301857, 39610, 831896, 112673, 2263974, 315069, \\ 6252982, 962897, 17280616, 2699066, 47760078, 7830950, 132931348, \\ 22759720, 369884919, 64726655, 1032244936, 187331836, 2889218776, \\ 537613196, 8093813288, 1540657359, 22732097026, 4436185030, \\ 63945607606, 12718488294\ldots$$ so in the case of rooted unlabeled trees there would seem to be a bias towards even numbers of endpoints.

The following Maple code was used to compute these values. It includes a basic routine that can be used to verify the polynomials for small $n$ say $n\le 7.$

with(numtheory);

T_basic :=
proc(n)
    option remember;
    local gf, q, k, p, term;

    if n=0 then return 0 fi;
    if n=1 then return u fi;

    gf := 1;
    for q to n-1 do
        for k to q do
            term :=
            add((u^k*z^q)^m, m=0..floor((n-1)/q));

            p := coeff(T_basic(q), u, k);
            gf := gf*term^p;
        od;
    od;

    coeftayl(gf, z=0, n-1);
end;

T :=
proc(n)
    option remember;
    local k, s, A;

    if n=0 then return 0 fi;
    if n=1 then return u fi;

    A := n -> add(subs(u=u^l, T(n/l))/l,
                  l in divisors(n));

    s := (1-u)*A(n-1);

    s := s + 1/(n-1)*
    add((k+1)*A(k+1)*T(n-1-k), k=0..n-2);

    expand(s);
end;

T_all := n -> subs(u=1, T(n));

T_even := n -> 1/2*(subs(u=1, T(n)) + subs(u=-1, T(n)));
T_odd := n -> 1/2*(subs(u=1, T(n)) - subs(u=-1, T(n)));

This material is inspired by Harary and Palmer, Graphical Enumeration.

Addendum Sat Dec 27 2014. We can verify the above results with Maple's combstruct package. It will even compute the functional equation for you (univariate version).

The following Maple code will do the trick for values of $n$ at most twelve.

with(combstruct);

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

    trees := { T=Union(Prod(Z, U), Prod(Z, Set(T, 1<= 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;

This will compute the following generating function for trees on $11$ nodes: $${u}^{10}+9\,{u}^{9}+52\,{u}^{8}+185\,{u}^{7}+416\,{u}^{6}+563\,{u}^{5}+ 429\,{u}^{4}+161\,{u}^{3}+25\,{u}^{2}+u.$$ This matches the value from the recurrence.

The command

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

will produce the coefficients of the univariate generating function for this problem matching the values shown above.