Number of labelled trees on $n$ vertices containing $2$ fixed non-adjacent edges

Question

Let $n\in \mathbb{N}$. Choose $e,f$ two disjoint pairs of integers in $1,...,n$. How many labelled trees on $n$ vertices ($1, 2, ..., n$) are there such that $e,f$ are edges of the tree?

I could not proceed in any way which made any significant progress. Any hints/ideas ?

Answer 1

Such problems can generally be solved by using Prüfer codes, which let us count trees with a prescribed degree for some specific vertices.

Take your tree on vertices $\{1,2,\dots,n\}$ containing edges $e$ and $f$, and contract these two edges. This gives us a tree on $n-2$ labeled vertices, two of which are the contracted vertices $x_e$ and $x_f$. (At this point we know that there are $(n-2)^{n-4}$ such trees, but that doesn't help us yet.

Each such tree can be expanded to an $n$-vertex tree in $2^{\deg(x_e) + \deg(x_f)}$ ways: for each edge incident to $x_e$ (respectively, to $x_f$) we have to choose an endpoint of $e$ (respectively, of $f$) it will connect to in the expanded tree.

The number of trees on $n-2$ vertices in which $\deg(x_e) = i+1$ and $\deg(x_f) = j+1$ is $\frac{(n-4)!}{i!\,j!\,(n-4-i-j)!} (n-4)^{n-4-i-j}$: this is just the number of Prüfer codes in which $x_e$ appears $i$ times and $x_f$ appears $j$ times. So we can count the number of trees we want by $$ \sum_{i,j\ge 0}^{i+j \le n-4} 2^{(i+1)+(j+1)} \cdot \frac{(n-4)!}{i!\,j!\,(n-4-i-j)!} (n-4)^{n-4-i-j}. $$ By the multinomial theorem, this is just $$ 4 \sum_{i,j \ge 0}^{i+j \le n-4} \binom{n-4}{i,j,n-4-i-j} 2^i 2^j (n-4)^{n-4-i-j} = 4 (2 + 2 + (n-4))^{n-4} = 4n^{n-4}. $$

Answer 2

The reader is asked to consult the following MSE link for references and additional documentation.

We will provide a closed form of the exponential generating function of the quantities that are involved.

The species of labelled trees has the specification $$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}}\mathcal{T} = \mathcal{Z} \times \textsc{SET}(\mathcal{T})$$ which gives the functional equation $$T(z) = z \exp T(z).$$

We have by Cayley that
$$T(z) = \sum_{n\ge 1} n^{n-1} \frac{z^n}{n!}.$$

We get from the functional equation $$T'(z) = \exp(T(z)) + z \exp(T(z)) T'(z)$$ so that $$T'(z) = \frac{\exp(T(z))}{1-z\exp(T(z))} = \frac{T(z)/z}{1-zT(z)/z} = \frac{1}{z} \frac{T(z)}{1-T(z)}$$

With these preliminaries we can answer the question. We may assume from symmetry considerations that the two edges are $\{1,2\}$ and $\{3,4\}.$ We now attach the tree to a horizontal line by straightening the unique path containing the two edges and placing it on the line. There are four possibilities for the ordering of the four nodes on the line. Let $\mathcal{S}$ be the combinatorial class of trees with two nodes marked which includes two marks on the same node, so that

$$S(z) = \sum_{n\ge 1} n^2 n^{n-2} \frac{z^n}{n!} = \sum_{n\ge 1} n n^{n-1} \frac{z^n}{n!} = z \frac{d}{dz} T(z) = \frac{T(z)}{1-T(z)}.$$

Observe that the tree matched to the line has five components. There are sets of trees, possibly empty, attached to the four distinguished nodes. The fifth component is a tree at the center that has two nodes marked where the trees sustained by the two special edges are attached to it. The latter may be empty which is the case of an edge between the two special ones. This is where we use the fact that the marks in $\mathcal{S}$ are ordered, which enforces the distinction between the attachment locations of the first and the second special edge.

We get the specification

$$\mathcal{Q} = \textsc{SET}(\mathcal{T}) \textsc{SET}(\mathcal{T}) \times (\epsilon + \mathcal{S}) \times \textsc{SET}(\mathcal{T}) \textsc{SET}(\mathcal{T})$$

This yields for the EGF the closed form

$$G(z) = \exp(T(z))\exp(T(z)) \times \left(1 + \frac{T(z)}{1-T(z)} \right) \times \exp(T(z))\exp(T(z))$$

which simplifies to

$$G(z) = \frac{\exp(4T(z))}{1-T(z)} = \frac{T(z)^4}{z^4 (1-T(z))}.$$

Extracting coefficients via Lagrange inversion we have $$Q_n = n! [z^n] G(z) = n! \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{T(z)^4}{z^4 (1-T(z))} \; dz.$$

Put $T(z)=w$ so that $z=w/\exp(w) = w\exp(-w)$ and $dz = \exp(-w) - w\exp(-w)$ to get $$n! \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{\exp(w(n+5))}{w^{n+5}} \frac{w^4}{1-w} (\exp(-w) - w\exp(-w)) \; dw \\ = n! \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{\exp(w(n+4))}{w^{n+1}} \; dw \\ = n! [w^n] \exp(w(n+4)) = (n+4)^n.$$

Now these are the nodes that do not include the four special ones. A target tree is obtained from an element of $Q$ by adding four to the labels of all nodes, which together with the special ones constitute the set of $n$ unique labels. Making the appropriate adjustments and taking into account the four possible orientations of the pair of special edges we obtain the closed form

$$\bbox[5px,border:2px solid #00A000]{ 4 \times n^{n-4}.}$$

and zero for $n\lt 4.$ The sequence starting at $n=4$ goes like this:

$$4, 20, 144, 1372, 16384, 236196, 4000000, 77948684, \\ 1719926784, 42417997492, 1157018619904, \ldots$$

The first five entries were verified by enumeration through the following Maple routine.

with(combinat);

pruef2tree :=
proc(a)
local deg, tree, u, v, p, q, n;

    n := nops(a) + 2;

    deg := [seq(1, q=1..n)];

    for q to n-2 do
        deg[a[q]] := deg[a[q]] + 1;
    od;

    tree := [];

    for q to n-2 do
        p := 1;

        while deg[p] <> 1 do
            p := p + 1;
        od;

        tree := [op(tree), {p, a[q]}];

        deg[p] := deg[p] - 1;
        deg[a[q]] := deg[a[q]] - 1;
    od;

    for u to n do
        if deg[u] = 1 then break fi;
    od;

    for v from u+1 to n do
        if deg[v] = 1 then break fi;
    od;

    [op(tree), {u, v}];
end;

trees_12_34 :=
proc(n)
option remember;
local ind, d, a, edges, q, res;

    if n = 1 then return 0 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)];

        edges := pruef2tree(a);

        if {1,2} in edges and {3,4} in edges
        then
            res := res + 1;
        fi;
    od;

    res;
end;

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

X1 := n ->
`if`(n<4, 0, 4*(n-4)! * coeftayl(exp(4*T)/(1-T), z=0, n-4));

X2 := n ->
`if`(n<4, 0, 4*(n-4)! * coeftayl(T^4/(1-T)/z^4, z=0, n-4));

XX := n -> `if`(n<4, 0, 4*n^(n-4));

Answer 3

Here's a low-tech answer using Prüfer codes. Let's start by answering a couple of related questions.

How many trees are there containing $e$? Without loss of generality, we can assume $e = \{n, n - 1\}$. Then trees containing $e$ correspond exactly to Prüfer codes that end in either $n - 1$ or $n$. So there are $2n^{n - 3}$ of them.

How many trees are there containing adjacent edges $e$ and $f$? Without loss of generality, we can assume $e = \{n, n - 1\}$ and $f = \{n, n - 2\}$. Then these trees correspond exactly to Prüfer codes that end in $n$ and whose next-to-last entry is one of $\{n - 2, n - 1, n\}$. So there are $3n^{n - 4}$ of them.

Now for some counting. Suppose that if $e$ and $f$ are disjoint then there are $k$ trees containing both. If we list out every tree containing $e$, then this consists of $2n^{n - 2} \cdot (n - 2)$ non-$e$ edges. All the $2( n -2)$ edges adjacent to $e$ show up on this list $3n^{n - 4}$ times, and all the $\binom{n}{2} - 2( n - 2) - 1$ edges not adjacent to $e$ show up $k$ times. This is true by the symmetry of $K_n$. So $$2n^{n - 3} \cdot (n - 2) = 2( n -2) \cdot 3n^{n - 4} + \left(\binom{n}{2} - 2( n - 2) - 1 \right) \cdot k$$

which means

$$ \begin{align} k &= \frac{2 n^{n - 3} \cdot (n - 2) - 2( n -2) \cdot 3n^{n - 4} }{\binom{n}{2} - 2( n - 2) - 1} \\ &= 4 n^{n - 4} \end{align} $$ as required.