A partition of a positive integer is an expression of as the sum of one or more positive integers (or parts). The order of the integers in the sum "does not matter": that is, two expressions that contain the same integers in a different order are considered to be the same partition.
The number of different partitions of is denoted . This function is called the partition function.
The partitions of are as follows:
Combinatorial functions such as often lend themselves to recursions that make them easier to compute. For instance, consider the number of decompositions of as the sum of positive integers in which order does matter (sometimes called compositions). Let be the number of compositions of . For instance, because .
Then there is a recursion for : if the first term of a composition of is , the remaining terms are a composition of . So the number of such compositions is . This leads to the recursive formula Solving this recursion is not hard: note that , and , so . (Exercise for the reader: there are direct, non-recursive proofs of this formula as well.)
However, proceeding in the same way for the partition function is not as straightforward, because of the possibility of over-counting partitions. For instance, a partition of that starts with is , which corresponds to the partition of , and a partition of that starts with is , which corresponds to the partition of ; but these are the same partition, so any recursive formula must avoid counting them twice.
In fact, there is no closed-form formula for in any meaningful sense. Many down-to-earth questions about the partition function are quite difficult and mysterious: for instance, it is not even known whether there are infinitely many such that is divisible by .
Partitions are represented pictorially in Ferrers diagrams: each part of the permutation is represented by a row of dots, where the number of dots equals the part. The rows, like the parts, are laid out in descending order of size:
This diagram represents the partition .
Young diagrams are similar, but use squares instead of dots. Here is the Young diagram for :
One concept that is most easily understood from diagrams of partitions is the notion of conjugacy.
Let be a partition of , and let be the number of parts of that are . Suppose the largest part is . Then the conjugate of is the partition
There is something to prove in the definition, namely that the sum of the actually equals . To see this, note that a part of size is counted once in . So, a part of size contributes to the sum, and therefore the sum is the same as the sum of the parts of .
This is not the easiest way to think about conjugate partitions. They are most simply described in terms of Ferrers diagrams: the Ferrers diagram of the conjugate partition is obtained from the Ferrers diagram of the original partition via reflection along the top-left to bottom-right diagonal. The operation is similar to a matrix transpose; the columns of the diagram change to rows and the rows change to columns.
The partition has the following Ferrers diagram:
Its conjugate has the following Ferrers diagram:
So, it is .
Note that the description via Ferrers diagrams shows without any work that conjugating twice returns the original partition, which was not necessarily immediately clear from the definition of conjugation.
Conjugate partitions are used in many bijective proofs of results about partitions; here is one basic example.
Show that the number of partitions of a positive integer into exactly parts equals the number of partitions of whose largest part equals . For instance, and , so .
Let be the set of partitions of into parts and let be the set of partitions of whose largest part equals . Then there is a bijection defined by the conjugate of . This is because the Ferrers diagram of a partition in has a first column of length , so its conjugate has top row of length . And is a bijection because it has an inverse map, namely conjugation. So the two sets have the same size.
For example, for , the function is
Other examples are given in the wiki on bijective proofs.
Main Article: Generating Functions
Many theorems about partitions that have complicated combinatorial proofs are easier and more accessible via generating functions. It is often the case that formal power series of the form , where the count certain types of partitions, can be expressed as infinite products in useful ways.
Express as an infinite product of power series.
Consider the product The coefficient of in this expansion is : suppose a partition of has 1s, 2s, and so on. Then , and this corresponds to the term in the expansion of the infinite product given by from the first sum, times from the second sum, and so on.
Rewriting this using geometric series gives
Euler's Pentagonal Number Theorem
The product equals
Note: Numbers of the form are called pentagonal numbers.
The theorem can be proved using partitions as well: the coefficient of in the product counts the number of partitions of with an even number of parts minus the partitions of with an odd number of parts. It can be shown (using Ferrers diagrams) that there is a bijection between these two sets of partitions unless is a pentagonal number, in which case there is a bijection between the sets with one specific partition removed.
Euler's pentagonal number theorem implies the following beautiful recurrence relation for : where the sign of is the opposite of the sign of in the sum expansion in Euler's pentagonal number theorem.