$N$ choose $K$ with bounded repetitions Is there any way to calculate an asymptotic tight bound on the number $N$ choose $K$ with  repetitions allowed under the condition that no element is repeated more than $M$ times ?
Thanks
 A: The following is a plausible heuristic that, with any luck, is correct and could be turned into a proof.
You're trying to count the number of $c$-tuples $(x_1,\dots,x_c)$, with each $0\le x_j\le2c$, such that $x_1+\cdots+x_c=c^2$. Subtracting $c$ from each variable, this is equivalent to counting the number of $c$-tuples $(x_1,\dots,x_c)$, with each $-c\le x_j\le c$, such that $x_1+\cdots+x_c=0$. Dividing by $c$, this is equivalent to counting the number of $c$-tuples $(x_1,\dots,x_c)$, with each $x_j\in\{-1,-1+\frac1c,\dots,1-\frac1c,1\}$, such that $x_1+\cdots+x_c=0$.
Let's approximate this by a continuous version: if each $x_j$ is an independent random variable uniformly distributed on $[-1,1]$, we want the probability that $|x_1+\cdots+x_c| \le \frac1{2c}$.
As $c$ tends to infinity, the random variable $\frac1c(x_1+\cdots+x_c)$ approaches a normal distribution with mean $0$ and variance $\frac13$. The probability that this random variable lies in the interval $[-\frac1{2c^2},\frac1{2c^2}]$ is approximately $\frac1{c^2}$ times the value of the corresponding density function, which is $\sqrt{3/2\pi}$.
Since the original sample space had $(2c+1)^c \sim (2c)^c e^{1/2}$ possible $c$-tuples, I predict that the count you're originally interested in is asymptotic to
$$
\sqrt{\frac{3e}{2\pi}} 2^c c^{c-2}.
$$
A: I am unable to find an asymptotic for $(n,m,k)=(c,2c,c^2)$ as $c\to\infty$, but I have found an asymptotic for $n\to\infty$ with $m$ and $k$ held fixed. This probably isn't useful for you then, but it at least seems worth posting.
You're counting multisets of natural numbers between $1$ and $n$ for which the total number of elements counted with multiplicitiy is $k$ and the multiplicity of each element doesn't exceed $m$.
These multisets can be encoded by membership functions $\{1,\cdots,n\}\to\{0,\cdots,m\}$ satisfying the sum $f(1)+f(2)+\cdots+f(n)=k$. Consider the following generating function:
$$\left(1+q_1t+q_1^2t^2+\cdots+q_1^mt^m\right)\cdots\cdots\left(1+q_nt+q_nt^2+\cdots+q_n^mt^m\right).$$
The $t^k$ coefficient will be a polynomial in $q_1,\cdots,q_n$. This polynomial will be a sum of monomials of the form $q_1^{f(1)}\cdots q_n^{f(n)}$, corresponding to aformentioned membership functions $i\mapsto f(i)$. To count the number of functions, we merely set $q_1=\cdots=q_n=1$. This gives
$$\begin{array}{ll} [t^k]\left((1-t^{m+1})^n\cdot(1-t)^{-n}\right) & =\sum_{i+j=k}\left([t^i](1-t^{m+1})^n\right)\left([t^j](1-t)^{-n}\right) \\ 
& = \sum_{i+j=k}\left([t^i]\sum_{u\ge0}\binom{n}{u}(-t^{m+1})^u\right)\left([t^j]\sum_{v\ge0}\binom{-n}{v}(-t)^v\right) \\
& = \sum_{i+j=k}[(m+1)\mid i]\binom{n}{i/(m+1)}(-1)^i\binom{-n}{j}(-1)^j \\
& = (-1)^k\sum_{w=0}^{\lfloor k/(m+1)\rfloor}\binom{n}{w}\binom{-n}{k-(m+1)w}.\end{array}$$
Note that this is a polynomial in $n$, since binomials $\binom{n}{l}:=\frac{n(n-1)\cdots(n-(l-1))}{l!}$ are. The degree of the $w$th summand as a polynomial in $n$ is $w+k-(m+1)w=k-mw$ which is maximized precisely when $w=0$ when the degree is $k$ and the leading coefficient is $1/k!$. Therefore, we have an exact formula as a polynomial in $n$, and in particular we see the count is $\sim n^k/k!$ asymptotically.
