Information on Partitions

Coin-Changing

What are the different ways a cashier could give out 30¢ in change to a customer? The simplest way would be to give a quarter and a nickel. But the cashier could also choose two dimes and two nickels, a quarter and ten pennies, or even 30 pennies. Three of the possibilities are listed below.

30¢ =	+     +     +
30¢ =	+
30¢ =	+     +     +     +     +
30¢ =	$·\; ·\; ·$

There are many other possibilities as well. Each possibility is called a coin changing. Coin changings are are special cases of what mathematicians call numerical partitions. All the coin-changings in AMOF use only existing Canadian coin values (1,5,10,25 cent coins, and 1 and 2 dollar coins). In a numerical parition, all coin values are present (1,2,3,... cent coins). AMOF can list all coin-changings and all numerical partitions. When counting different coin-changings (or numerical partitions), the order in which the coins appear does not matter; a dime and and nickel is exactly the same as a nickel and a dime. In our output we will arrange the coins in decreasing order; largest coin first, smallest coin last.

Numerical Partitions

Here's how a mathematician would define a numerical partition:

A numerical partition of an integer n is a sequence $$p₁ >= p₂ >= · · · >= p_k > 0, such that $$p₁+p₂+· · · +p_k = n. Each $$p_i is called a part. For example, 7+4+4+1+1+1 is a partition of 18 into 6 parts. AMOF allows you to specify both n and k. The number of partitions of n is denoted p(n) and the number of partitions of n into k parts is denoted p(n, k).

p(n, k) obeys the recurrence relation

The problem of coin changing is simply a special case of the numerical partition problem, since the different ways in which to make change for an amount of money is simply a type of numerical partition. For example, the ways to make change for 12¢ are exactly the ways to partition the number 12 if you may only use the numbers 1, 5 and 10 in the parts.

Every numerical partition of a number n corresponds to a unique "Ferrer's diagram." A Ferrer's diagram of a partition is an arrangement of n dots on a square grid where a part i in the partition is represented by placing $$p _i dots in a row. An example of a Ferrer's diagram for the numerical partition 7+4+4+1+1+1 is pictured below; 7 dots in the first row, 4 dots in the second row, etc.

Example

A few examples of numerical partitions have been given in the above paragraphs.

As another example, below is the output of the coin changing version of numerical partitions in AMOF where $$n = 12. In this example, a pictorial representation of the coins is also displayed.

Numbers	Pictures
10 + 1 + 1
5 + 5 + 1 + 1
5 + 1 + 1 + 1 + 1 + 1 + 1 + 1	:
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1	:

Here is another example, where the input is $$n = 200. Only the first 5 values of the output are shown.

Numbers	Pictures
200
100 + 100
100 + 25 + 25 + 25 + 25
100 + 25 + 25 + 25 + 10 + 10 + 5
100 + 25 + 25 + 25 + 10 + 10 + 1 + 1 + 1 + 1 + 1	:

A Brief History

The number of partitions of n, p(n) and the number of partitions of n into k parts, p(n, k), are studied extensively in both number theory and combinatorics.

The algorithm used by AMOF to produce numerical partitions uses a technique called recursive backtracking. This general technique is used in the solution to the 8 Queens problem and the Pentominoes problem. Even more generally, recursion is an important concept in computer programming, and is usually taught in the introductory university course in Computer Science.

One of the problems that involves numerical partitions is that of making change, as is demonstrated on AMOF. This can also be applied to placing stamps on a letter.

In the generation page, you will have the choice of listing:

• Coin changing partitions
• Regular numerical partitions

You choose the input value for n in either case, and can specify either, both or neither of the other two parameters k and m.

If you choose to list the regular type of numerical partitions, n will represent the number, k will represent the number of parts, and m will represent the size of the largest part. For example, if you choose to list all numerical partitions of 8, with input values $$n = 8, and $$k = 3, then AMOF will return all five partitions with 3 parts as follows:

$6\; +\; 1\; +\; 1,\; \; 5\; +\; 2\; +\; 1,\; \; 4\; +\; 2\; +\; 2,\; \; 4\; +\; 3\; +\; 1,\; \; 3\; +\; 3\; +\; 2$

As a second example, if you choose to list all numerical partitions of 9 with input value $$n = 9, and $$m = 5, then AMOF will return all five partitions with largest part 5 as follows:

$5\; +\; 1\; +\; 1\; +\; 1\; +\; 1,\; \; 5\; +\; 2\; +\; 1\; +\; 1,\; \; 5\; +\; 2\; +\; 2,\; \; 5\; +\; 3\; +\; 1,\; \; 5\; +\; 4$

Finally, if you choose to list all numerical partitions of 8 with input value $$n = 9$,$ $$k = 3, and $$m = 5, then AMOF will return two of the partitions listed above:

$5\; +\; 2\; +\; 2,\; \; 5\; +\; 3\; +\; 1$

If you choose to list the coin changing type of numerical partitions, n will represent the value in cents, and m will represent the largest part. If the value you provide for m is not a valid coin value, the next smallest valid coin value will be used. For example, if you choose to list all coin changing partitions of 16 with input value $$n = 16 and $$m = 12, then AMOF will return the two partitions with largest part 10 as follows:

$10\; +\; 5\; +\; 1,\; \; 10\; +\; 1\; +\; 1\; +\; 1\; +\; 1\; +\; 1\; +\; 1$

The two output options available are Numbers and Pictures. The appearance for the Numbers option has been shown in the many examples. The Pictures output will produce a Ferrer's diagram for regular types of partitions or an arrangement of coins for the coin-changing option. The appearance of the coin arrangement is shown in the Example section above. If you select the coin changing option and specify a value for k, AMOF will restrict the number of pennies generated in the output. If you choose $$k < 4, AMOF will use 4 as the maximum number of pennies. This restriction affects both numbers and pictures for coin changing because it affects what is generated.

Regardless of the input you give, AMOF will also restrict the number of pennies output in any coin diagram to 4 automatically. This restriction only affects the appearance of the Pictures for coin-changing, but not the numbers. When the penny output has been cut off, a few dots below the last penny will indicate this. This restriction is included to prevent extremely long output lists.