## Twelve Pennies

In how many ways can 12 pennies be put in 5 purses? What if none of the purses can be empty?
Source: http://www.mathcircles.org

SOLUTION
Because pennies are pennies, it is easy to accept that pennies are non-distinguishable objects. However, purses are a different matter. They can be distinguishable or not and so we need to investigate two cases: distinguishable and indistinguishable purses.

Distinguishable Purses
SOME PURSES CAN BE EMPTY
Imagine that the 12 pennies (represented by 12 letters $P's$) are laid out in a row on a table and that we use 4 sticks to divide them into 5 purses. For example,
$PPP|PPPP||PPP|PP$ describes the distribution of
3 pennies in the first purse,
4 in the second purse,
0 in the third purse, (some purse can be empty)
3 in the fourth purse,
2 in the fifth purse.

How many ways can we arrange the 16 objects: $PPP\cdots P||||$ (12 $P's$ and 4 sticks)?
We can accomplish the task by selecting 4 positions for the 4 sticks and that can be done in $\binom{16}{4}$ ways. After we placed the 4 sticks the 12 letters $P's$ can go into the 12 remaining positions. The number of ways of distributing 12 pennies to 5 purses equals
$\binom{16}{4}=1820$.

NO PURSE CAN BE EMPTY
First we place one penny in each purse to ensure that no purse is empty. Then, we proceed as before but now with only 7 pennies left to distribute to 5 purses.

How many ways can we select 11 objects: $PPP\cdots P||||$ (7 $P's$ and 4 sticks)?
The number of ways of distributing 7 pennies to 5 purses equals
$\binom{11}{4}=330$.

Indistinguishable Purses
NO PURSE CAN BE EMPTY
Suppose for a moment that the purses are distinguishable and labeled as $A_1,A_2,A_3,A_4,A_5$. The following two examples show how we may place the 12 pennies
$A_1\quad A_2\quad A_3\quad A_4\quad A_5$
$8\quad\;\; 1\quad\;\; 1\quad\;\; 1\quad\;\; 1$

$A_1\quad A_2\quad A_3\quad A_4\quad A_5$
$1\quad\;\;\; 8\quad\;\;\; 1\quad\;\; 1\quad\;\; 1$

Since the purses are identical we remove the labels and notice that the two results look identical. One purse has 8 pennies and the rest has 1 each.
$A\quad A\quad A\quad A\quad A$
$8\quad\; 1\quad\; 1\quad\; 1\quad\; 1$

$A\quad A\quad A\quad A\quad A$
$1\quad\; 8\quad\; 1\quad\; 1\quad\; 1$

The examples lead us to an approach to find a solution: find the number of partitions of 12 into exactly 5 positive integers. There are 13 ways to do that
1) $8+1+1+1+1$
2) $7+2+1+1+1$
3) $6+3+1+1+1$
4) $6+2+2+1+1$
5) $5+4+1+1+1$
6) $5+3+2+1+1$
7) $5+2+2+2+1$
8) $4+4+2+1+1$
9) $4+3+3+1+1$
10) $4+3+2+2+1$
11) $4+2+2+2+2$
12) $3+3+2+2+2$
13) $3+3+3+2+1$

There are 13 ways to distribute 12 pennies to 5 indistinguishable purses such that no purse can be empty.

SOME PURSES CAN BE EMPTY
Examples:
$12+0+0+0+0=12$
$7+5+0+0+0=12$
$6+4+2+0+0=12$
$4+4+2+2+0=12$
$4+3+3+1+1=12$
This time we need to find the number of partitions of 12 into 1, 2, 3, 4, and 5 positive integers and sum the numbers to get the total. The different partitions are listed below

One integer: 1 partition
$12$
Two integers: 6 partitions
1) $11+1$
2) $10+2$
3) $9+3$
4) $8+4$
5) $7+5$
6) $6+6$
Three integers: 12 partitions
1) $10+1+1$
2) $9+2+1$
3) $8+3+1$
4) $8+2+2$
5) $7+4+1$
6) $7+3+2$
7) $6+5+1$
8) $6+4+2$
9) $6+3+3$
10) $5+5+2$
11) $5+4+3$
12) $4+4+4$
Four integers: 15 partitions
1) $9+1+1+1$
2) $8+2+1+1$
3) $7+3+1+1$
4) $7+2+2+1$
5) $6+4+1+1$
6) $6+3+2+1$
7) $6+2+2+2$
8) $5+5+1+1$
9) $5+4+2+1$
10) $5+3+2+2$
11) $5+3+3+1$
12) $4+4+3+1$
13) $4+4+2+2$
14) $4+3+3+2$
15) $3+3+3+3$
Five integers: 13 partitions
See the list in the “NO PURSE CAN BE EMPTY” section.
Refer to the list http://oeis.org/A008284 to make sure that you have found all the partitions.

Total number of partitions = $1+6+12+15+13=47$
There are 47 ways to distribute 12 pennies to 5 indistinguishable purses such that some purses can be empty.