5
$\begingroup$

Define $t(n)$ to be the number of (unlabeled, unrooted) trees on n vertices such that each vertex has odd degree. For example, $t(2) = t(4) = 1$. Every finite nontrivial tree has endpoints and therefore at least has some vertices of odd degree. However, the global parity restriction considerably cuts down on the range of possibilities. For example, out of $23$ trees on $8$ vertices, only $t(8)=3$ satisfy the requirements.

Questions: (1) Is it possible to generate a table of values for $t(n)$?

(2) Is anything known or conjectured about the growth rate of $t(n)$?

Remarks: (a) Note that $t(2n+1)=0$ since the sum of degrees must be even.

(b) All the trees counted by $t(n)$ are, in particular, series reduced (i.e. no vertices of degree two).

(c) The labeled cousins of the $t(n)$ appear as sequence $A007106$ in OEIS.

$\endgroup$
  • $\begingroup$ I am not sure that this has been done, but the standard approach to counting isomorphism classes of trees is quite flexible and will very likely work in this case. The obvious starting point is Harary and Palmer "Graphical Enumeration". $\endgroup$ – Chris Godsil Jan 14 '15 at 17:41
5
$\begingroup$

First compute the OGF $T_1(z)$ for rooted unlabeled tree with all vertices of odd degree except for the root. This has the species equation $$\mathcal{T}_1 = \mathcal{Z} + \mathcal{Z} (\mathfrak{M}_{=2}(\mathcal{T}_1) +\mathfrak{M}_{=4}(\mathcal{T}_1) +\mathfrak{M}_{=6}(\mathcal{T}_1) +\cdots)$$ which is $$\mathcal{T}_1 = \mathcal{Z} (\mathfrak{M}_{=0}(\mathcal{T}_1) +\mathfrak{M}_{=2}(\mathcal{T}_1) +\mathfrak{M}_{=4}(\mathcal{T}_1) +\mathfrak{M}_{=6}(\mathcal{T}_1) +\cdots)$$

Now the OGF of the cycle index of the symmetric group $S_n$ is $$\exp \left(a_1 w + a_2 \frac{w^2}{2} + a_3 \frac{w^3}{3} + \cdots\right).$$

It follows that the operator $\mathfrak{M}_{\mathrm{even}}$ applied to $T_1(z)$ is given by $$\frac{1}{2}\exp \left( T_1(z) + \frac{T_1(z^2)}{2} + \frac{T_1(z^3)}{3} +\cdots\right) \\+ \frac{1}{2}\exp \left( -T_1(z) + \frac{T_1(z^2)}{2} - \frac{T_1(z^3)}{3} +\cdots\right)$$ or $$\frac{1}{2}\exp \left(\sum_{q\ge 1} \frac{T_1(z^q)}{q}\right) + \frac{1}{2}\exp \left(\sum_{q\ge 1} (-1)^q \frac{T_1(z^q)}{q}\right).$$

This gives the functional equation $$T_1(z) = \frac{z}{2}\exp \left(\sum_{q\ge 1} \frac{T_1(z^q)}{q}\right) + \frac{z}{2}\exp \left(\sum_{q\ge 1} (-1)^q \frac{T_1(z^q)}{q}\right).$$

To extract coefficients from this start by observing that if $$A(z) = \sum_{n\ge 1} A_n z^n = \sum_{q\ge 1} \frac{T(z^q)}{q} \quad\text{and}\quad B(z) = \sum_{n\ge 1} B_n z^n = \sum_{q\ge 1} (-1)^q \frac{T(z^q)}{q}$$ then $$A_n = \sum_{q|n} \frac{T_{n/q}}{q} \quad\text{and}\quad B_n = \sum_{q|n} (-1)^q \frac{T_{n/q}}{q}.$$

The functional equation now becomes $$T_1(z) = \frac{z}{2} \exp A_1(z) + \frac{z}{2} \exp B_1(z)$$ and coefficient extraction produces $$[z^n] T_1(z) = \frac{1}{2} \sum_{\lambda\vdash n-1} \frac{1}{l(\lambda)!} {l(\lambda) \choose f} \prod_{\lambda_i\in\lambda} A_{1,\lambda_i} +\frac{1}{2} \sum_{\lambda\vdash n-1} \frac{1}{l(\lambda)!} {l(\lambda) \choose f} \prod_{\lambda_i\in\lambda} B_{1,\lambda_i}$$ where the $f_i$ are the multiplicities of the partition i.e. $\lambda = 1^{f_1} 2^{f_2} 3^{f_3}\cdots$

This recurrence gives a serviceable but not excellent recurrence to compute $T_{1,n}.$

Now observe that the species $\mathcal{T}_2$ of rooted unlabeled trees with odd vertex degree throughout is given by $$\mathcal{T}_2 = \mathcal{Z} \mathfrak{M}_{\mathrm{odd}} (\mathcal{T}_1).$$

This gives the functional equation $$T_2(z) = \frac{z}{2}\exp \left(\sum_{q\ge 1} \frac{T_1(z^q)}{q}\right) - \frac{z}{2}\exp \left(\sum_{q\ge 1} (-1)^q \frac{T_1(z^q)}{q}\right).$$

Proceeding as before we extract coefficients to obtain $$[z^n] T_2(z) = \frac{1}{2} \sum_{\lambda\vdash n-1} \frac{1}{l(\lambda)!} {l(\lambda) \choose f} \prod_{\lambda_i\in\lambda} A_{1,\lambda_i} -\frac{1}{2} \sum_{\lambda\vdash n-1} \frac{1}{l(\lambda)!} {l(\lambda) \choose f} \prod_{\lambda_i\in\lambda} B_{1,\lambda_i}$$

Finally use the dissimilarity characteristic theorem for trees as presented by Harary and Palmer (section 3.2) to obtain for the generating function $T(z)$ of unrooted unlabeled trees with odd vertex degree the relation

$$T(z) = T_2(z) - \frac{1}{2}(T_1(z)^2-T_1(z^2)).$$

Since $T_1(z)$ only has non-zero coefficients $T_{1,n}$ at odd values of $n$ we obtain $$[z^{2n}] T(z) = T_{2,2n} - \frac{1}{2} \left(\sum_{q=0}^{n-1} T_{1,2q+1} T_{1, 2n-2q-1} -T_{1,n}\right).$$

This gives the sequence $$0, 1, 0, 1, 0, 2, 0, 3, 0, 7, 0, 13, 0, 32, 0, 74, 0, 192, 0, 497, \\ 0, 1379, 0, 3844, 0, 11111, 0, 32500, 0, 96977,\ldots$$

The first two generating functions were verified with Maple's combstruct package as follows.

with(combstruct);
with(combinat);
with(numtheory);

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;


T1or2 :=
proc(n, what)
    option remember;
    local Apart, Bpart, A, B, p, cf;

    if n=1 then return 1 fi;

    A := n -> add(T1(n/q)/q, q in divisors(n));
    B := n -> add((-1)^q*T1(n/q)/q, q in divisors(n));

    Apart := 0;
    Bpart := 0;

    p := firstpart(n-1);
    while type(p, `list`) do
        cf := 1/
        mul(q!, q in map(ent->ent[2],
                         convert(p, `multiset`)));

        Apart := Apart + cf*mul(A(q), q in p);
        Bpart := Bpart + cf*mul(B(q), q in p);

        p := nextpart(p);
    od;

    if what = T1 then
        return (Apart+Bpart)/2;
    else
        return (Apart-Bpart)/2;
    fi;
end;


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

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

    gf := add(u^evens(t),
              t in allstructs([T1, trees, unlabeled], size=n));
    coeff(gf, u, n);
end;


T1 :=
proc(n)
    option remember;
    local Apart, Bpart, A, B, p, cf;

    if n=1 then return 1 fi;

    T1or2(n, T1);
end;

T2_basic :=
proc(n)
    option remember;
    local trees, gf, t, st;

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

    gf := 0;
    for t in allstructs([T2, trees, unlabeled], size=n) do
        st := op(2, t);
        if type(nops(st), odd) then
            gf := gf + u^evens(st);
        fi;
    od;

    coeff(gf, u, n-1);
end;

T2 :=
proc(n)
    option remember;
    local Apart, Bpart, A, B, p, cf;

    if n=1 then return 1 fi;

    T1or2(n, T2);
end;

T :=
proc(m)
    local n;

    if type(m, odd) then return 0 fi;

    n := m/2;

    T2(2*n)
    -1/2*(add(T1(2*q+1)*T1(2*n-2*q-1), q=0..n-1)- T1(n));
end;

The last sequence required more work to verify. I used the NAUTY package to generate the trees and a Perl script to check for odd degrees as shown below. This confirmed the values from the recurrence for $n$ up to $20.$ No claims are made regarding proficiency in Perl.

#! /usr/bin/perl -w
#

sub decode_graph {
    my ($str) = @_;

    sub R {
        my (@args) = map {
            sprintf "%06b", $_;
        } @_;
        join '', @args;
    }

    my (@ents) = map {
        ord($_) - 63 
    } split //, $str;

    my $n = shift @ents;
    my @adj_data = split //, R(@ents);

    my $adj = []; my $pos = 0;
    for(my $ind2 = 1; $ind2 < $n; $ind2++){
        for(my $ind1 = 0; $ind1 < $ind2; $ind1++){
            $adj->[$ind1]->[$ind2] = $adj_data[$pos];
            $adj->[$ind2]->[$ind1] = $adj_data[$pos];

            $pos++;
        }
    }

    return $adj;
}

MAIN: {
    my $mx = shift || 2;
    die "out of range for GENG: $mx" 
        if $mx < 2 || $mx > 32;

    for(my $n=2; $n <= $mx; $n+=2){
        my $cmd = sprintf "./geng -c %d %d",
        $n, $n-1;

        my $count = 0;

        open GENG, "$cmd 2>/dev/null|";
        while(my $tree = <GENG>){
            chomp $tree; my $adj = decode_graph $tree;

            my $v;
            for($v = 0; $v < $n; $v++){
                my $deg = 0;
                for(my $w = 0; $w < $n; $w++){
                    my $ent = $adj->[$v]->[$w];
                    $deg++ if defined($ent) && $ent == 1;
                }

                last if $deg % 2 == 0;
            }

            $count++ if $v == $n;
        }
        close GENG;

        print "$count\n";
    }
}

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

Addendum. For the sake of completeness we treat the labeled case as well (labeled unrooted trees with odd vertex degree).

The species $\mathcal{T}_1$ of labeled rooted trees with odd vertex degree except at the root has the specification $$\mathcal{T}_1 = \mathcal{Z}+\mathcal{Z} \left(\mathfrak{P}_{=2}(\mathcal{T}_1) + \mathfrak{P}_{=4}(\mathcal{T}_1) + \mathfrak{P}_{=6}(\mathcal{T}_1) + \cdots\right).$$ This is $$\mathcal{T}_1 = \mathcal{Z} \left(\mathfrak{P}_{=0}(\mathcal{T}_1) + \mathfrak{P}_{=2}(\mathcal{T}_1) + \mathfrak{P}_{=4}(\mathcal{T}_1) + \mathfrak{P}_{=6}(\mathcal{T}_1) + \cdots\right).$$

This gives the functional equation $$T_1(z) = z \sum_{k\ge 0} \frac{T_1(z)^{2k}}{(2k)!}$$ or $$T_1(z) = \frac{z}{2} \exp(T_1(z)) + \frac{z}{2} \exp(-T_1(z)).$$

We can extract coefficients from this by Lagrange inversion. We have $$[z^n] T_1(z) = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} T_1(z) \; dz.$$

Put $T_1(z) = w$ so that $$z = \frac{2w}{\exp(w)+\exp(-w)}$$ and $$dz = \frac{2}{\exp(w)+\exp(-w)} - \frac{2w}{(\exp(w)+\exp(-w))^2} (\exp(w)-\exp(-w)) \; dw.$$

This gives for the integral $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(\exp(w)+\exp(-w))^{n+1}}{(2w)^{n+1}} \times w \\ \times \left(\frac{2}{\exp(w)+\exp(-w)} - \frac{2w}{(\exp(w)+\exp(-w))^2} (\exp(w)-\exp(-w)) \right) \; dw.$$

This has three components, call them $A$, $B$ and $C$. Component $A$ is $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(\exp(w)+\exp(-w))^{n}}{(2w)^{n+1}} \times 2w \; dw.$$ Now we have $$(\exp(w)+\exp(-w))^{n} = \exp(nw)\sum_{q=0}^n {n\choose q} \exp(-2wq).$$

This gives for $A$ the value $$\frac{1}{2^n} \sum_{p=0}^{n-1} \frac{n^p}{p!} \sum_{q=0}^n {n\choose q} \frac{(-2q)^{n-1-p}}{(n-1-p)!}.$$

Component $B$ is $$- \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(\exp(w)+\exp(-w))^{n-1}}{(2w)^{n+1}} \times 2w^2 \times \exp(w) \; dw.$$ Now we have $$(\exp(w)+\exp(-w))^{n-1} \exp(w) = \exp(nw)\sum_{q=0}^{n-1} {n-1\choose q} \exp(-2wq).$$

This gives for $B$ the value $$- \frac{1}{2^n} \sum_{p=0}^{n-2} \frac{n^p}{p!} \sum_{q=0}^{n-1} {n-1\choose q} \frac{(-2q)^{n-2-p}}{(n-2-p)!}.$$

Using the same procedure we obtain for $C$ the value $$\frac{1}{2^n} \sum_{p=0}^{n-2} \frac{(n-2)^p}{p!} \sum_{q=0}^{n-1} {n-1\choose q} \frac{(-2q)^{n-2-p}}{(n-2-p)!}.$$

This gives for the enumeration of the labeled species $\mathcal{T}_1$ the form $$n! [z^n] T_1(z) \\ = \frac{n!}{2^n} \left(\sum_{p=0}^{n-1} \frac{n^p}{p!} \sum_{q=0}^n {n\choose q} \frac{(-2q)^{n-1-p}}{(n-1-p)!} - \sum_{p=0}^{n-2} \frac{n^p-(n-2)^p}{p!} \sum_{q=0}^{n-1} {n-1\choose q} \frac{(-2q)^{n-2-p}}{(n-2-p)!} \right).$$

This gives at odd indices the sequence $$1, 3, 65, 3787, 427905, 79549811, 22036379521, 8513206310715, \\ 4374455745966593, 2885264091484122979, 2376040584184726335681, \ldots$$ which is OEIS A036778 where we find confirmation of these computations.

Continuing we find that the species $\mathcal{T}_2$ of rooted labeled trees with odd vertex degree including at the root is given by $$\mathcal{T}_2 = \mathcal{Z} \mathfrak{P}_{\mathrm{odd}}(\mathcal{T}_1)$$ and has the functional equation $$T_2(z) = z \sum_{k\ge 0} \frac{T_1(z)^{2k+1}}{(2k+1)!} = \frac{z}{2} \exp (T_1(z)) - \frac{z}{2} \exp (-T_1(z)).$$

We could treat this by Lagrange inversion as above but we choose a different path. Pause for a moment to differentiate the functional equation for $T_1(z)$ to get

$$T_1(z)' = \frac{1}{2} \exp (T_1(z)) + \frac{1}{2} \exp (-T_1(z)) \\ + \frac{z}{2} \exp (T_1(z)) T_1(z)' - \frac{z}{2} \exp (-T_1(z)) T_1(z)'.$$

This implies that $$T_1(z)' = \frac{1}{z} T_1(z) + T_1(z)' T_2(z).$$

Extracting coefficients from this we get $$T_{1,n+1} = \frac{T_{1,n+1}}{n+1} + \sum_{q=0}^n {n\choose q} T_{2,q} T_{1, n-q+1}.$$

As $T_{2,q} = 0$ this becomes $$\frac{n}{n+1} T_{1,n+1} = \sum_{q=1}^n {n\choose q} T_{2,q} T_{1, n-q+1}$$ or $$T_{2,n} = \frac{n}{n+1} T_{1,n+1} - \sum_{q=1}^{n-1} {n\choose q} T_{2,q} T_{1, n-q+1}$$ where $T_{2,0} = T_{2, 1} = 0.$

The even indices of this give the sequence $$2, 16, 576, 47104, 6860800, 1562148864, 512260833280, \\ 228646878969856, 133296779352342528, 98349146136012390400,\ldots$$ which points us to OEIS A060279 where the calculation is confirmed.

As we are working in the labeled universe the count of unrooted labeled trees with odd vertex degree throughout is given by $$\frac{T_{2,n}}{n}$$ which gives the sequence (even indices) $$1, 4, 96, 5888, 686080, 130179072, 36590059520, 14290429935616, \\ 7405376630685696, 4917457306800619520,\ldots$$ which is indeed OEIS A007106 as observed by the OP.

$\endgroup$
  • $\begingroup$ impressive - many thanks $\endgroup$ – user2052 Jan 19 '15 at 20:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.