Given $N$ boxes with the same capacity $C$, I toss coins into the boxes uniformly, one by one. When any one of the boxes is full, the sum of the coins in all boxes is denoted $S$. How to compute the probability density function of $S(N,C)$? 



The probability density function of the number of coins to first fill one box of $N$
(I change notation from $N,C$ to $n,c$ since I use capitals throughout to denote rvs).


Let $X\_i$ be the random variable "number of the box the $i$-th coin", then $X\_1,X\_2,\ldots$ is an i.i.d. sequence of random variables 
(each uniformly distributed on $\{1,\ldots,n\}$) and  

you are asking for the distribution of the time of the first $c$-fold repeat in this sequence.  

(The capacity of the boxes is immaterial here, since the process
is stopped when the first box is filled to its capacity. In the sequel I assume that the boxes have unlimited capacity.) 


Variants of this problem are well studied.


Let $Y\_1(k),\ldots,Y\_n(k)$ be the random variables $Y\_i(k):=$ "number of coins in box $i$" that have been filled in
 at "time" $k$. Clearly the joint distribution of ($Y\_1(k),\ldots,Y\_n(k)$) is multinomial with parameters $k$ and $p\_1=\ldots=p\_n={1\over n}$.
We therefore have


**Proposition**
The generating function of (the joint distribution of)
$Y\_1(k),\ldots,Y\_n(k)$ is given by:
\begin{equation\*}
\mathbb{E}\, t\_1^{Y\_1(k)}\ldots t\_n^{Y\_n(k)}=\frac{k!} {n^k}[t^k] e^{t(t\_1+\ldots +t\_n)}
\end{equation\*}


(**I**) The distribution of $S(n,c)$ 


Let $p\_c(t):=\sum\_{i=0}^{c-1} {t^i \over i!}$ be the $c-$th partial sum of $\exp(t)$. Since $\{\,S(n,c) > k\}=\{\,Y\_1(k)\leq c-1,\ldots,Y\_n(k)\leq c-1\,\}$ the above gives 
\begin{equation\*}
\mathbb{P}(S(n,c)> k) =\frac{k!}{n^k}[t^k] \big(p\_c(t))^n
\end{equation\*}


(**II**) The expectation of $S(n,c)$


Further, using $\mathbb{E} S=\sum\_{k\geq 0} \mathbb{P}(S>k)$ and writing ${k! \over n^k} = n\,\int\_0^\infty s^k e^{-ns}\,ds$ leads to
$$\mathbb{E}(S(n,c))=n\int\_0^\infty \big(p\_c(s)e^{-s}\big)^n\,ds$$
This goes back to Klamkin and Newman [1]


(**III**) The asymptotic distribution of $S(n,c)$


In the situation above let $j\in\{0,\ldots,k\}$ and denote by $U\_j^{k,n}$ the random variable "no. of boxes which contain exactly $j$ coins at time $k$".


The asymptotic distribution of $S(n,c)$ can be deduced from the following result of von Mises [2]:


**Theorem** (von Mises) 
 Let $j\in\{0,\ldots,k\}$ be fixed and $\alpha=\frac{k}{n}$. Then


(a) $\mathbb{E}(U\_j^{k,n})=n{k \choose j}(\frac{1}{n})^j(1-\frac{1}{n})^{k-j}\;,$


(b) If $k,n\longrightarrow \infty$ s.th. $n\frac{\alpha^j}{j!} e^{-\alpha}$ tends to a finite positive limit $a\_j$, then asymptotically $U\_j^{k,n}$ is Poisson distributed with parameter
$a\_j$.


The random variable $N\_c^{k,n}:=\sum\_{i=c}^n {i \choose c}\,U\_i^{k,n}$ gives the number of $c-$fold repetitions at time $k$ (because if a box has $i$ coins, each $c$-subset of these coins balls defines an $c$-fold repetition). Using $(a)$ we find that
$\mathbb{E}(N\_c^{k,n})=\frac{1}{n^{c-1}}{k \choose c}$.


The first $c$-fold repetitions will thus appear at times of order $t\_{c,n}:=(c!\,n^{c-1})^{1/c}$.
Clearly 
$\{S(c,n)>k\}=\{N\_c^{k,n}=0\}$. Therefore the theorem above has the following corollary:


**Corollary** Let $c\geq 2$ be fixed and $x>0$. Then
$\mathbb{P}(S(c,n)> t\_{c,n} x)\longrightarrow e^{-x^c}\;\;\;(n\longrightarrow \infty) $


**Proof:**
 Let $x>0$ and in the sequel $k=k(x,n):=\lceil x\,t\_{c,n}\rceil$ and $n\longrightarrow \infty$. Then $0\leq N\_c^{k,n} -U\_c^{k,n}\longrightarrow 0$
(since $\mathbb{E}(S\_c^{k,n}-U\_c^{k,n})=\frac{1}{n^{c-1}}{k \choose c}\left(1-(1-\frac{1}{m})^{k-c}\right)\longrightarrow 0$). Thus $N\_c^{k,n}$ and $U\_c^{k,n}$ have the same limit distribution.
The conditions of (b) are fulfilled with $a\_c=x^c$. Thus
$\mathbb{P}(S(c,n)>k(x,m))=\mathbb{P}(N\_c^{k(x,n),n}=0)\longrightarrow e^{-x^c}$
**End of Proof**


Equivalently $\mathbb{P} (S(n,c) >n^{1-1/c}x)\longrightarrow e^{-{x^c \over c!}}$. (The particular case $c=2$ of this corollary is very well known from its appearance in the "birthday paradox".) So they are indeed asymptotically Weibull-distributed.


[1]
Klamkin, M.S. and Newman, D.J., *Extensions of the Birthday Surprise*,
 Journal of Combinatorial Theory **3** (1967), pp.~279--282.


[2]
von Mises, R., *Über Aufteilungs- und Besetzungswahrscheinlichkeiten*,
 Revue de la Facult$\acute e$ des Sciences de l' Universit$\acute e$
 d'Istanbul **4** (1939), pp.~145--163.


