Combinatorics distribution problem indistinguishable items in distinguishable boxes

Question

In how many ways can you put $10$ identical gold coins into four colored boxes so that at least $1$ goes into the blue box, at least $1$ into yellow, at most $2$ into red and at least $3$ into green?

The way I solved this was by writing down all the restrictions, $$B \geq 1, \space G \geq 3, \space Y \geq 1, \space R \leq 2$$ Where each letter corresponds to the first letter of each colour box.

Dividing the problem into 3 cases where there's no coin in red box, 1 coin and 2 coins in red box seems to be the most logical, giving the following results using bars and stars:

C1: R box has zero coins

$\binom{3 + 5-1}{5} = \binom{7}{5}$

C2: R box has one coins

$\binom{3 + 4 - 1}{4} = \binom{6}{4}$

C3: R box has two coins

$\binom{3 + 3 - 1}{3} = \binom{5}{3}$

Giving us a final result of $$\binom{7}{5}+\binom{6}{4}+\binom{5}{3}$$

I wanted to know if this is the correct way of solving a problem like this? What if we had bigger numbers including a box having at most say a 1000 coins, would we need to make a 10000 cases? what if there's multiple at most restrictions? like 2 boxes have to have at most 3 gold coins?

Answer 1

This type of question can be more easily done with generating functions. Say we have some series $a_n$; we can encode $a_n$ as a generating function $\sum_{n=0}^\infty a_nx^n$. The values we want to keep track of are hidden in the generating function as the coefficients of $x^n$. In combinatorics, $a_n$ is used to count the number of ways we can do something to a set of $n$ elements. When you multiply two generating functions, they have a useful combinatorial interpretation.

Consider the product $\sum_{n=0}^\infty a_n\sum_{n=0}^\infty b_n$, where we think of $a_n$ and $b_n$ each as counting ways to do something to a set of $n$ elements. The coefficient of $x^n$ in the product is $\sum_{i=0}^n a_ib_{n-i}$. We can think of this as the number of ways to do what $a_i$ does to $i$ elements in an $n$-element set and do what $b_{n-i}$ does to the other $n-i$ elements in our $n$-element set. Note that we don't choose what $a_i$ acts on or what $b_{n-i}$ acts on, so we say that $a_i$ acts on the first $i$ elements. In the particular case of identical gold coins, it doesn't matter.

I realize that this sounds arcane, so here's an example. Let $b_n$ count the number of ways we can put $n$ coins in the blue box such that we put in at least one. Ignore the other three boxes for now. Then $b_0=0$ (putting in $0$ coins doesn't satisfy the condition of putting in at least one), and $b_i=1$ for all $i\geq 1$. Then the generating function for putting coins into the blue box is $\sum_{n=0}^\infty b_nx^n=x+x^2+x^3+\ldots$ and since $1+x+x^2+\ldots=\frac{1}{1-x}$, we can write the generating function as $\frac{1}{1-x}-1$.

Now let $y_n$ count the number of ways to put $n$ coins into the yellow box such that we put in at least one. The generating function for the yellow box will also be $\frac{1}{1-x}-1$ by the same reasoning. Now consider the product of the generating function for the blue box and the generating function for the yellow box, $(\frac{1}{1-x}-1)^2$. If we look at its series expansion, we see that it's $x^2+2x^3+3x^4+\ldots$. I claim that this is the generating function for putting $n$ coins into the yellow or blue box such that each box gets at least one coin. For $n<2$, we can't satisfy that each box has at least one coin, so there are $0$ ways to do it. For $n\geq 2$, we can put $i$ coins into the blue box, where $1\leq i\leq n-1$, and $n-i$ into the yellow box. Since $i\geq 1$ and $n-i\geq 1$, this satisfies the condition, so there are $n-1$ ways to do this and my claim holds.

To do the full problem, we just need the generating functions for red and green. For red, it's $1+x+x^2$, to show that we can only put in $0, 1$, or $2$ coins. For green, it's $\frac{1}{1-x}-1-x-x^2$, to show that we can't put in $0, 1$, or $2$ coins. Then, if we look at the series expansion of the product of all four generating functions, $(\frac{1}{1-x}-1)^2(1+x+x^2)(\frac{1}{1-x}-1-x-x^2)$, we get $46$ as the coefficient of $x^10$, which is the same as your answer. You can verify that this works for all of the other coefficients listed as well. For a generalized version of this problem, as long as you can find the generating functions for each individual box, which should be easy as long as they're of the form, "at least $n$ coins" or "at most $n$ coins", then you find their product and get the generating function for putting the coins into all of the boxes.

Answer 2

Place a gold coin in the blue box, a gold coin in the yellow box, and three gold coins in the green box. That leaves us with five gold coins to distribute the four boxes. Let $x_b$, $x_g$, $x_r$, and $x_y$ be the number of remaining coins that are placed, respectively, in the blue, green, red, and yellow boxes. Then $$x_b + x_g + x_r + x_y = 5 \tag{1}$$ which is an equation in the nonnegative integers. We must find the number of solutions of equation 1 subject to the restriction that $x_r \leq 2$.

We first find the number of solutions without considering the restriction, then subtract the number of solutions that violate the restriction.

A particular solution of equation 1 corresponds to the placement of three addition signs in a row of five ones. For instance, $$1 + + 1 1 1 + 1$$ corresponds to the (prohibited) solution $x_b = 1$, $x_g = 0$, $x_r = 3$, and $x_y = 1$. Therefore, the number of solutions of equation 1 is the number of ways we can place three addition signs in a row of five ones, which is $$\binom{5 + 4 - 1}{4 - 1} = \binom{8}{3}$$ since we must choose which three of the eight positions required for five ones and three addition signs will be filled with addition signs.

From these, we must subtract those solutions in which $x_r \geq 3$. Suppose $x_r \geq 3$. Then $x_r' = x_r - 3$ is a nonnegative integer. Substituting $x_r' + 3$ for $x_r$ in equation 1 yields \begin{align*} x_b + x_g + x_r' + 3 + x_y & = 5\\ x_b + x_g + x_r' + x_y & = 2 \tag{2} \end{align*} which is an equation in the nonnegative integers with $$\binom{2 + 4 - 1}{4 - 1} = \binom{5}{3}$$ solutions.

Hence, the number of ways ten identical coins can be distributed to four boxes so that there is at least one gold coin in the blue box, at least one gold coin in the yellow box, at least three gold coins in the green box, and at most two gold coins in the red box is $$\binom{8}{3} - \binom{5}{3} = 56 - 10 = 46$$ which agrees with your answer.

Answer 3

There is an easier way to solve this problem which generalizes better to when there are several boxes which may have at most $N$ coins, where $N$ is large. I will illustrate with your example.

First, count the number of ways to put all the coins into the boxes without the $R\le 2$ restriction. This is $\binom{5+4-1}5$, beacuse you are putting $5$ coins into $4$ boxes. Next, subtract out the "bad" distributions where the $R$ box has more than $2$ coins. This is equivalent to counting distributions satisfying $\{B\ge 1,G\ge 3, Y\ge 1, R\ge 3\}$, the number of which is $\binom{2+4-1}2$. The final answer is $\binom{8}5-\binom{5}2$.

What if you had two boxes with an upper limit? Say you have $15$ balls, and you still have all four boxes with their restrictions from before, but now there is also a purple box which can have at most $5$ balls.

• Start by ignoring both the upper limit restriction, counting $\{B\ge 1,G\ge 3,Y\ge 1\}$. The number is $\binom{10+5-1}{10}$.

• Subtract out the distributions where the $R$ box has more than $2$ balls. This is counting $\{B\ge 1,G\ge 3,Y\ge 1, R\ge 3\}$ The count is $\binom{7+5-1}{7}$

• Subtract out the distributions where the $P$ box has more than $5$ balls. This is counting $\{B\ge 1,G\ge 3,Y\ge 1, P\ge 6\}$ The count is $\binom{4+5-1}{4}$

• Now, the cases where both the $R$ and $P$ boxes have been subtracted out twice, so these cases must be added back in. We are adding back in placements satisfying $\{B\ge 1,G\ge 3,Y\ge 1, R\ge 3,P\ge 6\}$, the number of which is $\binom{1+5-1}{1}$.

The final answer is $$ \binom{14}{10}-\binom{11}{7}-\binom{8}{4}+\binom{5}1 $$

In general, if there are many boxes with an upper limit, you have to use the Principle of Inclusion-Exclusion to subtract out the bad distributions.