Identical objects and identical boxes [duplicate]

Find the number of ways of distributing 999 identical balls into 3 identical boxes.

This number(999) is too huge to allow a case by case treatment.

Ans: 83667

marked as duplicate by rlartiga, Edward Jiang, 2012ssohn, user91500, ShaileshDec 7 '16 at 6:40

• Note: stars and bars gives the answer for non-identical boxes. – Mees de Vries Dec 6 '16 at 17:03
• @MeesdeVries thanks, deleted. Then we have a case of integer partition. – rlartiga Dec 6 '16 at 17:09

Hint: Break into 3 cases 1. all boxes have same num of balls 2. exactly 2 boxes have same num of balls 3. all boxes have different num of balls

Case 1 and 2 are trivial to solve Case 3: solve assuming boxes are different (this is a std combinatorics problem) . reduce that by number where you could permute the distribution across boxes across all the cases (as boxes are identical)

finally add the 3 cases off course

Let $n_1 \le n_2 \le n_3$ be the number of balls in the three boxes in sorted order. Since the balls and boxes are identical, the configuration is uniquely specified by the triple ($n_1,n_2,n_3$).

Let $m_1 = n_1$, $m_2 = n_2 - n_1$ and $m_3 = n_3 - n_2$. The condition $n_1 \le n_2 \le n_3$ becomes $m_1, m_2, m_3 \ge 0$. The problem at hand reduces to finding the number of solutions for

$$\color{red}{3m_1} + \color{green}{2m_2} + \color{blue}{m_3} = n_1 + n_2 + n_3 = N\quad\quad\text{ for }\quad m_1,m_2,m_3 \in \mathbb{N}^3$$ when $N = 999$.

Let $p_N$ be the number of ways of putting $N$ identical balls into $3$ identical boxes.
Above discussion tells us the OGF of $p_N$ equals to

$$f(z) \stackrel{def}{=} \sum_{N=0}^\infty p_N z^N = \frac{1}{ \color{red}{(1-z^3)} \color{green}{(1-z^2)} \color{blue}{(1-z)} }$$ With help of a CAS, we can partial fraction decompose RHS and get

\begin{align} f(z) &= \frac16\frac{1}{(1-z)^3} + \frac14 \frac{1}{(1-z)^2} + \frac{17}{72}\frac{1}{1-z} + \frac18\frac{1}{1+z} + \frac19\frac{2+z}{1+z+z^2}\\ &= \frac16\frac{1}{(1-z)^3} + \frac14 \frac{1}{(1-z)^2} + \frac{17}{72}\frac{1}{1-z} + \frac18\frac{1-z}{1-z^2} + \frac19\frac{2-z-z^2}{1-z^3} \end{align}

Notice \begin{align} \frac{1-z}{1-z^2} &= \sum_{k=0}^\infty d_k z^k\quad\text{ where }\quad d_k = \begin{cases} +1, & k \equiv 0 \pmod 2\\ -1, & k \equiv 1 \pmod 2\\ \end{cases}\\ \frac{2-z-z^2}{1-z^3} &= \sum_{k=0}^\infty e_k z^k\quad\text{ where }\quad e_k = \begin{cases} 2, & k \equiv 0 \pmod 2\\ -1, & \text{otherwise} \end{cases} \end{align} Together with followings expansions for any $m \ge 1$, $$\frac{1}{(1-z)^m} = \sum_{k=0}^\infty \binom{k+m-1}{m-1} z^k$$

We get

$$p_N = \frac16\binom{N+2}{2} + \frac14\binom{N+1}{1} + \frac{17}{72} + \frac18 d_N + \frac19 e_N = \frac{(N+1)(N+5) + f_N}{12}$$ where $\quad f_N = 12\left(\frac{17}{72} + \frac18 d_N + \frac19 e_N\right) = \begin{cases} 7, & N \equiv 0 \pmod 6,\\ 0, & N \equiv 1,5 \pmod 6\\ 3, & N \equiv 2,4 \pmod 6\\ 4, & N \equiv 3\pmod 6\\ \end{cases}$

Notice $0 \le \frac{f_N}{12} < 1$ and $p_N$ is an integer, we can simplify above formula to

$$p_N = \left\lceil\frac{(N+1)(N+5)}{12}\right\rceil$$

Substitute $N = 999$ in this formula, the number of ways of placing $999$ identical balls into $3$ identical boxes equals to:

$$p_{999} = \left\lceil\frac{1000 \times 1004}{12}\right\rceil = 83667$$