[AMOF] [GENERATE] [Schoolnet Icon]

Information on Partitions

[Description | Example | History | Applications | Implementation | Classroom | Links]


Description of the Problem

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 p1 >= p2 >= · · · >= pk > 0, such that p1+p2+· · · +pk = n. Each pi 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

p(n,k) = p(n-1,k-1) + p(n-k,k)

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

One might suppose that coin-changing problems arose shortly after the advent of currency. Coins were invented sometime around 700 B.C. (link), but the number of ways to make change was not of great importance, either financially or mathematically, except as a way to motivate the study of numerical partitions, as we do here.

The concept of a numerical partition undoubtedly originates much further in time than what is recorded in written history. Many famous mathematicians have worked with numerical partitions, and their study is an important part of what is know as "number theory".

An algorithm for generating numerical partitions was provided by Carl Friedrich Hindenburg in 1778. Perhaps the most intriguing person to work on the partition recurrence was Ramanujan, who stimulated work on the subject with a fairly close approximation to the sequence of numbers. Ramanujan's approximation function from 1913 was very similar to the problem's exact solution, which came in 1937. What is interesting about Ramanujan was that he had no mathematical training, living as a clerk in India. When G.H. Hardy, a mathematician in England, received a letter from him discussing some mathematical topics, Hardy was impressed. Ramanujan was then brought to Cambridge University in England, where he and Hardy collaborated on several results.

A number of researchers have developed algorithms for generating numerical partitions of various types since the 1960's.


Applications to Mathematics and other Areas

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.


Explanation of AMOF Implementation

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

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.


In the Classroom

The idea of a numerical partition can be used in the younger grades to develop and test students' number concept. Several activities which are related to numerical partitions are mentioned in a reference book produced by NCTM given in the links section of this page. For example, students can glue groups of toothpicks on a file card, writing the number of toothpicks beneath each group and writing the total number of toothpicks at the bottom of the card.

AMOF will allow students to test their understanding of coin changing and breaking a number into parts with the added appeal of showing them diagrams of the results. They might try to list the partitions in lexicographic order (or reverse lexicographic for coins) and use AMOF to check their answers.

For high school students, the topics of partitions and recurrence relations can be covered to prepare them for postsecondary education. In [NCTM], both partitions and recurrence relations are reported to be combinatorics topics in at least half of college and university math and computer science courses. This is mentioned in the chapter entitled "The Roles of Finite and Discrete Mathematics in College and High School Mathematics"


Links to Other Relevant Sites and Sources of Information


[AMOF] [GENERATE] [Schoolnet Icon]


This page created by
Frank Ruskey and Scott Lausch, March 1998. ©Frank Ruskey and Scott Lausch, 1998.
The coin images used on this page are courtesy of the Royal Canadian Mint.