Partition (number Theory) - Restricted Partitions

Restricted Partitions

A restricted partition is a partition in which the parts are constrained in some way.

For example, we could count partitions which contain only odd numbers. Among the 22 partitions of the number 8, there are 6 that contain only odd parts:

• 7 + 1
• 5 + 3
• 5 + 1 + 1 + 1
• 3 + 3 + 1 + 1
• 3 + 1 + 1 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

Alternatively, we could count partitions in which no number occurs more than once. If we count the partitions of 8 with distinct parts, we also obtain 6:

• 8
• 7 + 1
• 6 + 2
• 5 + 3
• 5 + 2 + 1
• 4 + 3 + 1

It is true for all positive numbers that the number of partitions with odd parts always equals the number of partitions with distinct parts. This result was proved by Leonhard Euler in 1748 and is a special case of Glaisher's theorem.

Some similar results about restricted partitions can be obtained by the aid of a visual tool, a Ferrers graph (also called Ferrers diagram, since it is not a graph in the graph-theoretical sense, or sometimes Young diagram, alluding to the Young tableau).

Some results concerning restricted partitions are:

• The number of partitions of n in which the greatest part is m is equal to the number of partitions of n into m parts.
• The number of partitions of n in which each part is less than or equal to m is equal to the number of partitions of n into m or fewer parts.
• The number of partitions of n in which all parts are equal is the number of divisors of n.
• The number of partitions of n in which all parts are 1 or 2 (or, equivalently, the number of partitions of n into 1 or 2 parts) is

• The number of partitions of n in which all parts are 1, 2 or 3 (or, equivalently, the number of partitions of n into 1, 2 or 3 parts) is the nearest integer to (n + 3)2 / 12.