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.

Answer: Given in solution.

Advertisements

About mvtrinh

Retired high school math teacher.
This entry was posted in Problem solving and tagged , , , , . Bookmark the permalink.

One Response to Twelve Pennies

  1. wittylaila says:

    im so confused!! lol..

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s