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.
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.