combinatoricsgraph theorytrees
I am interested how one can count all the trees with $n$ vertices from all $n^{n-2}$ trees, that have at most $k$ degree of a vertex. Is there a way to do it for any $k$?
All trees with degree at most $k$ can be encoded to Prufer sequence with at most $kâ1$ repetition of number of the vertex. Therefore we could count all possible ways to create permutation with repetition of each element at most $kâ1$ times. Honestly, I don't know how one could do that.
Any suggestons would be welcomed.
If we denote the number of vertices as $n$, from the hand shaking lemma and the fact that the number of edges in a tree is $n-1$, we have $$\sum_{v \in V} d_n = 2 \vert E \vert = 2(n-1)$$ If $s_k$ vertices have degree at-least $k$, then we have $$2(n-1) = \sum_{v \in V} d_n \geq s_k \times k +(n-s_k)$$ Hence, we get that $$s_k(k-1) \leq n-2 \implies s_k \leq \dfrac{n-2}{k-1} \implies s_k \leq \left\lfloor\dfrac{n-2}{k-1} \right\rfloor$$ This bound is tight, i.e., you can construct a tree with exactly $\left\lfloor\dfrac{n-2}{k-1} \right\rfloor$ vertices of degree $k$.
Hence, in the case of $k=3$, we have $s_3 \leq \left\lfloor\dfrac{n}2 \right\rfloor - 1$.
I hope I understood your question correctly.
Here's a way to find the number. It looks like it might not be the best (Sloane's A055315 has other formulas), but it works.
Let $n$ be the number of vertices and $e=n-1$ be the number of edges.
Claim: There is exactly one vertex of degree $3$, all others have degree $2$ or $1$. (Assume otherwise, and we violate the Handshaking Lemma, which stipulates the sum of degrees is $2e=2(n-1)$.)
So, the trees look like this:
If we delete the degree-$3$ vertex, we obtain three components. These three components only have vertices of degree $1$ and $2$, and so must be paths. Suppose the paths have $a$, $b$ and $c$ vertices. Then $a+b+c=n-1$ and $a,b,c$ are all positive integers. Conversely, given three paths of lengths $a \geq 1$, $b \geq 1$ and $c \geq 1$ and $a+b+c=n-1$, we can join their endpoints to a new vertex to create an $n$-vertex tree with exactly three $3$ leaves.
Let $a(n)$ be the number of partitions of $n-1$ into $3$ non-zero parts; this is equivalent to Sloane's A001399 which includes the formula $$a(n)=1+\left\lfloor\frac{(n-1)^2+6(n-1)}{12}\right\rfloor$$ among others.
Given an unlabeled tree, we can label the vertices in $n!$ (not necessarily distinct) ways. In this way, we generate $a(n)\ n!$ labeled trees.
In some cases (not many), there are symmetries which need to be accounted for. Because of symmetry, in this case
we count every labeling twice. This happens whenever $\{a,b,c\}$ have two parts of the same size.
And in this case
we count every labeling six times. This happens when $\{a,b,c\}$ has all three parts of the same size.
In these cases, we'll need to add a correction.
In the first case: we subtract $$\sum_{a \geq 1:n-1-a \text{ is even and } \geq 2} \tfrac{1}{2}n!=\frac{\lfloor (n-2)/2 \rfloor\ n!}{2}$$ since we have double-counted the $\frac{1}{2} n!$ graphs with $b=c=\tfrac{n-1-a}{2}$.
In the second case: if $n-1 \equiv 0 \pmod 3$, we first "uncorrect" the first correction, so we add back in $\tfrac{1}{2}n!$ and then subtract $\frac{5}{6}n!$ since we originally counted six times the $\frac{1}{6} n!$ graphs with $a=b=c$.
This gives $$\begin{cases} a(n)\ n!-\tfrac{\lfloor (n-2)/2 \rfloor\ n!}{2} & \text{if } n-1 \not\equiv 0 \pmod 3 \\ a(n)\ n!-\tfrac{\lfloor (n-2)/2 \rfloor\ n!}{2}+\tfrac{1}{2}n!-\tfrac{1}{6} n! & \text{if } n-1 \equiv 0 \pmod 3. \end{cases}$$ in agreement with Sloane's A055315.
Best Answer
There is no "closed form" solution in terms of elementary functions. However, the number of lists of length $n-2$ with entries in $\{1,2,\dots,n\}$ where each element appears at most $k-1$ times can be written as $$ (n-2)!\cdot[x^{n-2}]\Big(1+x^1/1!+x^2/2!+\dots+x^{k-1}/(k-1)!\Big)^n $$ Here, $[x^m]f(x)$ refers to the coefficient of $x^m$ in the polynomial (or power series) $f(x)$. This can be computed efficiently using Fourier transform polynomial multiplication.