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 ) are laid out in a row on a table and that we use 4 sticks to divide them into 5 purses. For example,

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: (12 and 4 sticks)?

We can accomplish the task by selecting 4 positions for the 4 sticks and that can be done in ways. After we placed the 4 sticks the 12 letters can go into the 12 remaining positions. The number of ways of distributing 12 pennies to 5 purses equals

.

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: (7 and 4 sticks)?

The number of ways of distributing 7 pennies to 5 purses equals

.

**Indistinguishable Purses
**NO PURSE CAN BE EMPTY

Suppose for a moment that the purses are distinguishable and labeled as . The following two examples show how we may place the 12 pennies

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.

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)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

13)

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:

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

Two integers: 6 partitions

1)

2)

3)

4)

5)

6)

Three integers: 12 partitions

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

Four integers: 15 partitions

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

13)

14)

15)

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 =

There are 47 ways to distribute 12 pennies to 5 indistinguishable purses such that some purses can be empty.

**Answer**: Given in solution.

im so confused!! lol..