3
$\begingroup$

I was wondering about that one:

A "varied Tree" T is a tree where for each 2 distinct vertices (non-leaves) u,v $ deg(u) \neq deg(v)$. How many varied trees are there for the set of vertices $\{1,2,3...11\} $

Well, I thought about using Prufer code, but I am confused with all the possible cases there are.

Thanks.

$\endgroup$
2
$\begingroup$

Suppose we seek to enumerate "labeled varied trees" i.e. trees where the degrees of non-leaves in the tree are unique. We use Pruefer codes. The degree of a node in the tree corresponding to a given code is one more than the number of times it appears in the code. Leaves do not appear. The problem thus reduces to counting the Pruefer codes where the number of times a value between $1$ and $n$ appears is unique.

This calculation is very similar to the material at the following MSE link.

Recall the species of set partitions $$\mathfrak{P}(\mathcal{U}\mathfrak{P}_{\ge 1}(\mathcal{Z}))$$

which immediately gives the generating function

$$G(z, u) = \exp(u(\exp(z)-1)).$$

Now in the present case we seek to limit the number of appearances of a set to zero or one. Therefore we introduce

$$G(z, u) = \exp\left(\sum_{q\ge 1} u v_q \frac{z^q}{q!}\right).$$

Starting with $v_1$ and extracting the coefficients on $v_1^0$ and $v_1^1$ we get

$$\exp\left(\sum_{q\ge 2} u v_q \frac{z^q}{q!}\right) + \exp\left(\sum_{q\ge 2} u v_q \frac{z^q}{q!}\right) u \frac{z}{1} \\ = \exp\left(\sum_{q\ge 2} u v_q \frac{z^q}{q!}\right) \left(1+u\frac{z}{1}\right).$$

The same procedure for $v_2^0$ and $v_2^1$ yields

$$\exp\left(\sum_{q\ge 3} u v_q \frac{z^q}{q!}\right) \left(1+u\frac{z}{1}\right) \left(1+u\frac{z^2}{2}\right).$$

We get for $v_3^0$ and $v_3^1$

$$\exp\left(\sum_{q\ge 4} u v_q \frac{z^q}{q!}\right) \left(1+u\frac{z}{1}\right) \left(1+u\frac{z^2}{2}\right) \left(1+u\frac{z^3}{6}\right).$$

The pattern should be clear. The conclusion is that the generating function for set partitions with unique sizes and sizes at most $n-2$ is

$$H(z, u) = \prod_{q=1}^{n-2} \left(1+u\frac{z^q}{q!}\right).$$

Let me point out that this can be derived by inspection without going through the species of set partitions. Each term in the product is a chooser type gadget that we must pass through and which enforces a choice of either taking a set of size $q$ or not taking it.

The desired count is then given by

$$(n-2)! \sum_{k=1}^{n-2} {n\choose k} \times k! \times [u^k] [z^{n-2}] H(z, u).$$

This will produce the following sequence, which starts at $n=1:$

$$1, 1, 3, 4, 65, 126, 637, 21344, 57465, 330850, 2023901, \\ 156312432, 502733101, 3464645380, 21505493115, 194182086016, \ldots $$

The answer for eleven vertices is

$$\bbox[5px,border:2px solid #00A000] {\Large 2023901.}$$

The Maple code for this including enumeration was as follows.

with(combinat);

trees_varied :=
proc(n)
option remember;
local ind, d, a, mset, deg, res;

    if n=1 then return 1 fi;

    res := 0;

    for ind from n^(n-2) to 2*n^(n-2)-1 do
        d := convert(ind, base, n);
        a := [seq(d[q]+1, q=1..n-2)];

        mset := convert(a, `multiset`);
        deg := map(ent -> ent[2]+1, mset);

        if nops(deg) = nops(convert(deg, `set`))
        then
            res := res + 1;
        fi;
    od;

    res;
end;


X :=
proc(n)
option remember;
local H;

    if n=1 or n=2 then return 1 fi;

    H :=
    coeff(expand((n-2)!*mul(1+u*z^q/q!, q=1..n-2)), z, n-2);

    add(binomial(n,k)*k!*coeff(H, u, k), k=1..n-2);
end;
$\endgroup$

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.