on counting the number of trees on Kn (case)

Question

During my reasearch I have stumbled across a problem that can be presented in such way:

"How many are there spanning trees on Kn such that every tree contains v: deg(v) = k, for a given k"

The vertices are labelled.

Answer 1

First I'll give a fairly useless exact formula. The number of labelled trees with vertices of degree $d_1,\ldots,d_n$ is $$\binom{n-2}{d_1-1,\ldots,d_n-1}.$$ Therefore the number with $d_1=\cdots=d_t=k$ is $$T(n; k,t)=\frac{(n-2)!\,(n-t)^{n-2-tk+t}}{(k-1)!^t\,(n-2-tk+t)!},$$ where we agree that $T(n;k,t)=0$ if $n-2-tk+t<0$. Thus, by inclusion-exclusion, the number of trees with no vertices of degree $k$ is $$\sum_{t\ge 0} (-1)^t\binom nt T(n;k,t).$$

Next I'll indicate how the asymptotic value can be obtained. Fix any $\mu>0$. Let $\boldsymbol{D}=(D_1,\ldots,D_n)$ be a random variable whose components are iid Poisson variables with mean $\mu$. Then the conditional distribution of $\boldsymbol{D}$ subject to $\sum_{i=1}^n D_i=n-2$ is (exactly) the same as the distribution of $(d_1-1,\ldots,d_n-1)$ for a random tree. Note that this is independent of $\mu$.

We want to compute the conditional probability of $A$, which is the event that $D_i\ne k-1$ for $1\le i\le n$. By Bayes' Theorem (twice) we have $$P(A\mid {\textstyle\sum_i D_i=n-2}) = \frac{P(A)\,P(\sum_i D_i=n-2\mid A)}{P(\sum_i D_i=n-2)},$$ where the quantity on the left is the probability we need. On the right, $P(A)$ is easy: $P(A)=P(D_i\ne k-1)^n$ since the $D_i$s are independent. Also $P(\sum_i D_i=n-2)$ is easy since $\sum_i D_i$ has a Poisson distribution with mean $n\mu$. The only slightly tricky part is $P(\sum_i D_i=n-2\mid A)$.

Consider $X_1,\ldots,X_n$ to be iid random variables whose distribution is like Poisson with mean $\mu$ except that the value $k-1$ is omitted. Then $P(\sum_i D_i=n-2\mid A)$ is the probability that $\sum_i X_i = n-2$. To estimate this, adjust $\mu$ so that $\mathbb{E} X_i\approx (n-2)/n$ and apply a local central limit theorem.

Answer 2

I assume that you mean the following: fix $k>1$. You want to count all (labelled) trees on $n$ vertices with at least a vertex of degree $k$.

I will sketch the strategy, which requires some (long) manipulations. This counting can be done at least theoretically by generating functions, and then use Lagrange inversion formula to get the desired result. Let $T(x)$ be the generating function for rooted labelled trees. Then it is well known that it satisfies the following equation:

$$T(x)=x \exp(T(x))=x \sum_{j\geq 0} \frac{T(x)^j}{j!}.$$ This joint with Cayley formula gives Cayley formula for rooted trees, and then multiplying by $n$ of general labelled trees on $n$ vertices (n^{n-2}).

Now, we only need to count trees without vertices of degree $k$ (Note that necessarily $k>1$: when $k=1$ we always have vertices of degree $1$).

In order to do so, we refine the previous counting. When rooting we have to be careful with the degree of the root vertex. So:

1.- We count first (rooted) trees where any vertex different from the root vertex has degree different from $k$. This is counted by the generating function:

$$T_k(x)=x \left(\exp(T_k(x))-\frac{T_k(x)^{k-1}}{(k-1)!}\right)$$

2.- The problem for $T_k(x)$ is that the root vertex could have degree $k$ (from the specification it does not have degree $k-1$). So we can now define the rooted family we want as:

$U_k(x)=x\left(\exp(T_k(x))-\frac{T_k(x)^k}{k!}\right)$

3.- Now we need to unroot the tree. IN the labelled case is straightforward and gives $U_k(x)-U_k(x)^2/2$.

4.- Finally, we want to have $T(x)-T(x)^2/2-(U_k(x)-U_k(x)^2/2)$ in order to have the GF of labelled trees with some vertex of degree $k$ (Notice that $T(x)-T(x)^2/2$ is the GF of unrooted labelled trees)