Counting trees with bounded degree

Question

I need to calculate the number of unlabelled trees with bounded maximal out-degree. I interested in both exact solution and asymptotic estimate. Can you suggest some papers about this topic or any other related materials?

Answer 1

I suggest to compute some of these numbers and consult the OEIS for more information. (See below for links containing a considerable number of references.) Since the bound is on outdegree, call it $k$, these unlabeled trees are rooted. We thus have from first principles and using the Polya Enumeration Theorem the species equation

$$\mathcal{T} = \mathcal{Z} + \mathcal{Z} \sum_{q=1}^k \mathfrak{M}_{=q}(\mathcal{T}) = \mathcal{Z} + \mathcal{Z} \mathfrak{M}_{\le k}(\mathcal{T}).$$

We thus obtain the functional equation

$$T(z) = z + z \sum_{q=1}^k Z(S_q)(T(z))$$

where $Z(S_q)$ is the cycle index of the symmetric group which may be computed from the recurrence

$$Z(S_q) = \frac{1}{q} \sum_{l=1}^q a_l Z(S_{q-l}) \quad\text{where}\quad Z(S_0) = 1.$$

The cycle indices are evaluated with the usual substitution $a_l = T(z^l).$ Extracting coefficients then yields

$$T_n = [[n=1]] + [z^{n-1}] \sum_{q=1}^k Z(S_q)(T(z)).$$

This is sufficient to compute these. We present a Maple program (which the reader is free to optimize) that gave the following results.

• $k=1$, paths (sanity check for boundary values): $$1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,\ldots$$
• $k=2$ OEIS A001190, $$1, 1, 2, 3, 6, 11, 23, 46, 98, 207, 451, 983, 2179, \\ 4850, 10905, 24631,\ldots$$
• $k=3$ OEIS A000598, $$1, 1, 2, 4, 8, 17, 39, 89, 211, 507, 1238, 3057, 7639, \\ 19241, 48865, 124906,\ldots$$
• $k=4$ OEIS A036718, $$1, 1, 2, 4, 9, 19, 45, 106, 260, 643, 1624, 4138, 10683, \\ 27790, 72917, 192548,\ldots$$
• $k=5$ OEIS A036721, $$1, 1, 2, 4, 9, 20, 47, 112, 277, 693, 1766, 4547, 11852, \\ 31146, 82534, 220149,\ldots$$
• $k=6$ OEIS A036722, $$1, 1, 2, 4, 9, 20, 48, 114, 283, 710, 1816, 4690, 12267, \\ 32338, 85978, 230080,\ldots$$
• $k=7$ OEIS A182378, $$1, 1, 2, 4, 9, 20, 48, 115, 285, 716, 1833, 4740, 12410, \\ 32754, 87176, 233547,\ldots$$
• $k=8$ (OEIS ends here). $$1, 1, 2, 4, 9, 20, 48, 115, 286, 718, 1839, 4757, 12460, \\ 32897, 87592, 234746,\ldots$$

The Maple code was as follows (another version may be implemented which is faster at the expense of more memory).

pet_cycleind_symm :=
proc(n)
option remember;

    if n=0 then return 1; fi;

    expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;


pet_flatten_term :=
proc(varp)
local terml, d, cf, v;

    terml := [];

    cf := varp;
    for v in indets(varp) do
        d := degree(varp, v);
        terml := [op(terml), seq(v, k=1..d)];
        cf := cf/v^d;
    od;

    [cf, terml];
end;

T :=
proc(n, k)
option remember;
local q, idx, recurse, contrib, term, flat,
    res, sols, sol;

    if n = 1 then return 1 fi;

    recurse :=
    proc(l, m, sofar, pos)
    local fact, mult;
        fact := op(1, l[pos]);

        if pos = nops(l)  then
            if m mod fact = 0 then
                contrib := contrib +
                sofar * T(m/fact, k);
            fi;

            return;
        fi;

        for mult to floor(m/fact) do
            if m-mult*fact > 0 then
                recurse(l, m-mult*fact,
                        sofar * T(mult, k),
                        pos + 1);
            fi;
        od;
    end;

    res := T(n-1, k);

    for q from 2 to k do
        idx := pet_cycleind_symm(q);

        for term in idx do
            flat := pet_flatten_term(term);

            contrib := 0;
            recurse(flat[2], n-1, 1, 1);
            res := res + flat[1]*contrib;
        od;
    od;

    res;
end;

Addendum. An alternative species to use which has the feature that it includes leaves that do not contribute to the count of nodes in the tree is

$$\mathcal{T} = \epsilon + \mathcal{Z} \mathfrak{M}_{= k}(\mathcal{T}).$$

and gives the functional equation

$$T(z) = 1 + z Z(S_k)(T(z)).$$

While this version may perhaps be considered a more elegant encapsulation of the givens of this problem it must be pointed out that experiments indicate a poorer complexity by a considerable indeed quite significant factor compared to the first version. What we gain from the reduction in the number of recursive terms is more than offset by the contribution from the constant in $T(z^l)$, requiring value zero entries in the partitions of the exponents (which sum to $n-1$ and are computed in the routine recurse).

The modified Maple routine goes as follows.

T :=
proc(n, k)
option remember;
local q, idx, recurse, contrib, term, flat,
    res, sols, sol;

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

    recurse :=
    proc(l, m, sofar, pos)
    local fact, mult;
        fact := op(1, l[pos]);

        if pos = nops(l)  then
            if m mod fact = 0 then
                contrib := contrib +
                sofar * T(m/fact, k);
            fi;

            return;
        fi;

        for mult from 0 to floor(m/fact) do
            recurse(l, m-mult*fact,
                    sofar * T(mult, k),
                    pos + 1);
        od;
    end;

    idx := pet_cycleind_symm(k);
    res := 0;

    for term in idx do
        flat := pet_flatten_term(term);

        contrib := 0;
        recurse(flat[2], n-1, 1, 1);
        res := res + flat[1]*contrib;
    od;

    res;
end;

A remarkable optimization. The following simple concept combined with memoization and the second functional equation makes for an algorithm that produces instant results including for very large $n.$ This concept is that we do not compute the cycle indices separately but extract the coefficients from the recurrence given above. The Maple code here is quite straightforward and is included below.

recurse :=
proc(n, q, k)
option remember;
local res, l, m;

    if q = 0 then
        if n = 0 then
            return 1
        else
            return 0;
        fi;
    fi;

    if q = 1 then return T(n, k) fi;

    res := 0;

    for l to q do
        for m from 0 to floor(n/l) do
            res :=
            res +
            1/q*T(m, k)*
            recurse(n-m*l, q-l, k);
        od;
    od;

    res;
end;


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

    if n <= 1 then return 1 fi;
    if k = 1 then return 1 fi;

    recurse(n-1, k, k);
end;

With this code we can answer questions like, what is the number of unlabeled rooted trees with maximum outdegree $20$ on $100$ nodes? The answer is

$$51384326061583754822835604490295332437941545.$$