Distinct Balls and distict Urns with constraint maximum I'm looking for a some help with a general expression.  I'm trying to put $k$ distinct balls into $n$ distinct urns, but each urn can only hold up to $c$ balls, with $cn \geq k$.
I know there are $n^k$ permutations, but how do I enforce the constraint?
 A: The number of ways to put $k$ balls in $n$ bins where each bin can only hold up to $c$ balls is the coefficient of $z^k$ in the $n^{\text{th}}$ power of the ordinary generating function $1+x+\dots+x^c$, i.e., $$[z^k]\left(\sum_{i=0}^c z^i\right)^n.$$
The finite geometric series is equivalent to $\frac{1-z^{c+1}}{1-z}$. Expanding the numerator with the binomial theorem, this is equivalent to $$[z^k]\frac{\sum_{i=0}^n\binom ni(-1)^i z^{i(c+1)}}{(1-z)^n}.$$
The generating function for the denominator is $\sum_{i\ge0}\binom{n-1+i}{n-1}z^i$. Multiplying these together gives an explicit formula for the desired count, namely $$\sum_{i=0}^n \binom ni(-1)^i\binom{n-1+k-i(c+1)}{n-1}.$$
A: I assume by "distinct" you mean distinguishable.
In that case, the desired result if empty bins are allowed is 
$\text{balls}! \left[z^{\text{balls}}\right] \left(\sum _{k=0}^{\text{capacity}} \frac{z^k}{k!}\right){}^{\text{bins}}$
and if no empty bins are allowed
$\text{balls}! \left[z^{\text{balls}}\right] \left(\sum _{k=1}^{\text{capacity}} \frac{z^k}{k!}\right){}^{\text{bins}}$
In both, $\left[z^{\text{balls}}\right]$ is the coefficient extraction, e.g. the coefficient of $z$ for exponent $balls$ in the subsequent factors.
A: Let me derive @Rus May's formula, using the method proposed in this post.
We want to know in how many ways $C^{(s)}_{n,g}$ we can put $n\ge0$ undistinguishable spheres into $g\ge0$ urns, with at most $s\ge1$ spheres in a given urn. We proceed by induction; consider the first urn: we can put into it a number $i$ of balls from zero (no spheres) to either $s$ or, if we have fewer than $s$ spheres in total, $n$. Once we have done this, we are back to the starting problem, but with $n-i$ spheres and $g-1$ boxes. 
As a consequence we get the following recurrence relation:
$$
C^{(s)}_{n,g}=\sum_{i=0}^{\mathrm{min}(n,s)}C^{(s)}_{n-i,g-1}\,.
$$
The boundary terms are $C^{(s)}_{0,g}=1$ for all $g\ge0$ and $C^{(s)}_{n,0}=0$ if $n\ge1$. We define the generating functions
$$
f_g^{(s)}(x)=\sum_{n=0}^\infty C^{(s)}_{n,g} x^n\,,
$$
namely,
$$
C^{(s)}_{n,g} = [z^n]f_g^{(s)}(x)\,.
$$
By the above boundary relations, the $g=0$ function also satifies $f_0^{(s)}(x)=1$. Next we multiply the recurrence relaition for $C^{(s)}_{n,g}$ by $x^n$ and sum over $n$ from 0 to infinity: we adopt the conventions that whenever a $C^{(s)}_{n,g}$ is evaluated outside its range of validity (its ''support'') it gives zero, thus
$$
\begin{aligned}
\sum_{n=0}^\infty C^{(s)}_{n,g} x^{n} &= \sum_{n=0}^s\sum_{i=0}^{n}C^{(s)}_{n-i,g-1} x^n + \left(\sum_{i=0}^s x^i\right) \sum_{n=s+1}^\infty C^{(s)}_{n-i,g} x^{n-i}\\
f_g^{(s)}(x) &= \left(\sum_{n=0}^s\sum_{i=0}^{n} -  \sum_{i=0}^{s} \sum_{n=0}^s\right)C^{(s)}_{n-i,g-1} x^n + \frac{1-x^{s+1}}{1-x} f_{g-1}^{(s)}(x)\,,
\end{aligned}
$$
where we used that $\sum_{i=0}^s x^i=(1-x^{s+1})/(1-x)$.
The summations on the right-hand side cancel out, because they differ only by terms for which $C_{n,s}^{(s)}$ are outside their support, and hence
$$
f_g^{(s)}(x) = \frac{1-x^{s+1}}{1-x} f_{g-1}^{(s)}(x) \implies \boxed{f_g^{(s)}(x) = \left( \frac{1-x^{s+1}}{1-x} \right)^g}
$$
on account of $f_0^{(s)}=0$. We can extract the $x^n$ coefficient using Newton's binomial formula and the Taylor expansion of the denominator, obtaining
$$
C^{(s)}_{n,g}= \sum_{k=0}^g (-1)^k \binom{g}{k}\binom{n-1+n-k(s-1)}{g-1}\,.
$$
If instead we are interested in the analogous combinatorics $D_{n,g}^{(s)}$ for distinguishable spheres, taking into account the fact that we can choose the first $i$ spheres in $\binom{n}{i}$ ways, we need to start from the recurrence relation
$$
D_{n,g}^{(s)} = \sum_{i=0}^{\mathrm{min}(n,s)} \binom{n}{i} D^{(s)}_{n-i, g-1}\,.
$$
Again, $D_{0,g}^{(s)}=1$ for $g\ge0$ and $D_{n,0}^{(s)}=0$ if $n\ge1$. In this case it is more convenient to employ the exponential generating functions
$$
F_g^{(s)}(x)=\sum_{n=0}^\infty D_{n,g}^{(s)} \frac{x^n}{n!}\,,
$$
which satisfy
$$
D_{n,g}^{(s)} = n! [z^n] F_g^{(s)}(x)\,.
$$
Also, $F_0^{(s)}=1$. Multiplying the recurrence relation by $x^n/n!$ and summing over $n$, as we did above, we get, after the analogous cancellations of low-$n$ terms,
$$
F_g^{(s)}(x)=\sum_{i=0}^s\frac{x^i}{i!}\sum_{n=0}^\infty D^{(s)}_{n-i, g-1} \frac{x^{n-i}}{(n-i)!}= \left(\sum_{i=0}^s\frac{x^i}{i!}\right) F_{g-1}^{(s)}(x)\,,
$$
hence, as already pointed out by @HammyTheGreek,
$$
\boxed{F_g^{(s)}(x) = \left(\sum_{i=0}^s\frac{x^i}{i!}\right)^g\,.}
$$
Using the multinomial coefficient, the answer can therefore be written as
$$
D^{(s)}_{n,g}=n! \sum_{\substack{\sum l_i=g\\\sum_i i l_i=n}} \binom{g}{l_1,l_2,\ldots,l_s}\frac{1}{\prod_i (i!)^{l_i}}\,.
$$
In the following particular cases, the generating functions give the ordinary combinations and $n$-permutations without repetitions or with an arbitrary number of repetitions:
$$
f_{g}^{(1)}=(1+x)^g\,,\qquad
f_{g}^{(\infty)}=(1-x)^{-g}\,,\qquad
F_{g}^{(1)}=(1+x)^g\,,\qquad
F_g^{(\infty)}=e^{gx}\,;
$$
$$
C_{n,g}^{(1)}=\binom{g}{n}\,,\qquad
C_{n,g}^{(\infty)}=\binom{g+n-1}{n}\,,\qquad
D_{n,g}^{(1)}=\frac{g!}{(g-n)!}\,,\qquad
D_{n,g}^{(\infty)}=g^n\,.
$$
