tg

tg
tgt

Saturday, 22 September 2012

Partitions of integers


Partitions of integers


This paper explores partitions of integers, establishing four distinct theorems regarding the relationships between partitions of integers with different properties. Equivalence is shown between the number of partitions with distinct parts, with the number of partitions with only odd parts, and also between partitions with m parts and partitions with largest part m. A variety of techniques are used, amongst which generating functions and Ferrers diagrams have a central role. As such, the paper demonstrates the variation in the extent to which a technique is appropriate. There is also a brief discussion of some of the results in the field, in particular the work of Euler, Hardy and Ramanujan.
Section One

Introduction

Any natural number n can be expressed as the sum of smaller integers in a variety of different ways, any of which is a partition of n. For instance:
4 = 4
= 3 +1
= 2 + 2
= 1 + 1 + 2
= 1 + 1 + 1 + 1
More generally for any natural number n, a partition is a set of natural numbers {a1, ...., ak } greater than 0 such that
n = a1 +.... + ak .
where each of the addends is a part of the partition. Note that the order of addition is not important, and let the order of indices be chosen from the largest to the smallest elements. We can define the function p(n) on the natural numbers:

Definition 1

p(n) = s, where s is the number of distinct partitions of n.
It is possible to extend this function further, and choose partitions with particular properties.

Definition 2

p(n | Q) = s, where s is the number of partitions of n which have the property Q
For instance we may be interested in all the partitions of n where all the parts are odd, or the partitions in which all the parts are distinct.
There is a vast amount of work on partitions of integers in the literature, much of it based on the foundations set out by Euler. (HE) Euler established a generating function for p(n), which itself can be expressed as a recurrence relation (Skiena, 1990). The noted academics G.H.Hardy and Srinvasa Ramanujan also used these methods to produce a number of remarkable results, including a non-convergent solution to p(n) that enables it to be computed exactly (Hardy, 1999). This solution was later built upon by Rademacher, who demonstrated the existence of a convergent solution to p(n).
This report will establish four distinct results on partitions of integers, which use generating functions and Ferrer diagrams. In the next section these methods will be outlined, and some results obtained by others in the literature will be discussed. This will be followed by the proofs of the theorems themselves, and the paper will attempt to demonstrate clear links between different methods of proof. This will then be followed by a brief conclusion, where the results and proofs adopted will be discussed.

Section Two

The Partition of Integers

It is possible to represent a partition of an integer by the use of a Ferrers diagram (Rose, 2003). Each row in the diagram represents one part of partition, and the number of dots in each row is equal to the value of the part. For instance the partition of 7 into 3 + 2 + 2 can be denoted as follows:
The visual nature of Ferrers diagrams have allowed them to be used to prove a wide variety of theorems. For instance Laurendi (2005) makes use of them in order to provide an elegant proof of the theorem that the number of partitions of an integer n into parts with largest part j is the same as the number of partitions of n into precisely j parts. A slightly different approach is provided below, with the connection between the visual and entirely analytic proof made explicit. Ferrers diagrams have continued to be useful in combinatorics, and therefore provide a foundation to work in computer science (see Gazeau et al, 2007). Andrews and Erikkson (2004) demonstrate their role in visualisation, and proving a variety of facts regarding integers, including Euler's pentagonal number theorem.
It is also possible to approach the partitions of numbers in a slightly different way, which involves creating a generating function for p(n).

Definition 3 Generating function
A function f(x; an) is a generating function of a sequence (an) if it takes the following form:
Following Euler (cited in Andrews and Erikkson, 2004), consider the function
(1 + x + x2 + x3 ...)(1 + x2 + x4 ...)(1 +x3 + x6 ...)(1 + x4 + x8 ...)...
Given the fact that one can occur any number of times in the partition, we obtain the first term in the expansion. Similarly two can appear any number of times, providing the second term, and so on. Hence this must be the generating function for p(n). Indeed, as emphasised by Wilf (2000), this provides us with a separate way of representing a partition. For instance 20 = 1 + 1 + 2 + 2 + 4 + 10, which could be written as 20 = (2)1 + (2)2 + (1)4 + (1)10. In particular there exists a one to one correlation between the monomials with a product of xn and the partitions of n (see Wilf, 2000 for details).
Note however that the series in each parentheses is a geometric series, and therefore it is possible to write the equation as follows:
These functions are of particular use in deriving a variety of facts about partitions of integers, and one particular such theorem is outlined below. Wilf (2000) demonstrates how generating functions can be used to show that the number of partitions of n with no parts equal to 1 is equal to p(n) – p(n-1). Laurendi (2005) also outlined a proof of the fact that the number of partitions with each part occurring at most once, is equal to the number of partitions in which each part appears at most three times, a result which can be generalised.
This research will provide some proofs of some theorems that demonstrate the use of the various techniques described above. In particular four distinct theorems which will be proved, which are as follows:
Theorem 1. p(n | m parts) = p(n | largest part = m)
Theorem 2. p(n | at most m parts) = p(n + m | m parts)
Theorem 3. p(n | partitions are self conjugate) = p(n | all parts are distinct and odd)
Theorem 4.p(n | distinct parts) = p(n | odd parts)
Much of this work is extremely well covered in the literature, and these theorems are often established as part of an introduction to work on partitions of integers. This work will attempt to provide a relatively unique perspective through demonstrating the close connection between the visual and analytic techniques available, whilst offering clear and precise proofs.
Section Three

Results

Theorem 1. p(n | m parts) = p(n | largest part = m)

In order to prove this theorem it is helpful to consider a Ferrers diagram. Consider a partition of n where the smallest part is equal to m.
● ● ● ●.......● a dots
● ● ● .....● b dots
● ● ● ...● m dots
Now, convert the columns into rows and rows into columns.
● ● ● ... ●
● ● ● ... ●
● ● ... ● ●
m b a
Hence we have a partition of n into m different parts, and more generally it is possible to define a bijection between two sets of Ferrers diagrams and hence between p(n | m parts) and p(n | largest part = m). In order to demonstrate this more formally it is necessary to capture the intuitive concept highlighted by the Ferrers diagrams.

Definition 4. Conjugates

Partition {a1, ...., ak } is said to be a conjugate of partition {b1, ...., bj} if
n = a1 + ....+ ak
and n = b1 + .... + bj
where bi is the number of aj's at least as large as i.

Lemma 1.1. The conjugation operation ζ({a1, ...., ak }) = {b1, ...., bj} is a map from partitions of n with largest element r to partitions of n with j parts.

Proof
Let {a1, ...., ak } be such that a1, the largest element in the set, be r. Then for each i between 1 and r, there is more than 1 element of {a1, ...., ak } greater than or equal to ai. Thus bi is defined and greater than 0 whenever i is less than or equal to j.
If i is greater than j, bi is 0. Therefore {b1, ...., bj} is a partition with j parts.

Lemma 1.2. ζ is a bijection.

Proof
The operation of conjugation is clearly well defined.
Then let {a1, ...., ak } and {a'1, ...., a's} be partitions of n with largest element j. Let their conjugates be {b1, ...., bj} and {b'1, ...., b'j} respectively and assume that bi = b'i for all i = 1, ..., k.
Firstly, since bj = b'j there are precisely the same number of elements equal to j in {a1, ...., ak } as are equal to j in {a'1, ...., a'k}.
Let h be less than j. Then bh = b'h, and so there are exactly as many elements equal to or larger than h in {a1, ...., ak } as are equal to or larger than h in {a'1, ...., a'k}. However since bh+1 = b'h+1, there are exactly as many elements equal or larger than h+1 in {a1, ...., ak } as are equal to or larger than h+1 in {a'1, ...., a'k}. Hence there are exactly as many elements equal to or larger than h in {a1, ...., ak } as are equal to or larger than h in {a'1, ...., a'k}.
Thus {a1, ...., ak }={a'1, ...., a's}, and so ζ is injective.
Lastly let {b1, ...., bj} be a partition of n of j parts. Then construct a set as follows:
bj elements equal to j
bk - bk+1 elements equal to k
This set maps under ζ to {b1, ...., bj}, and hence ζ is onto.
Proof of theorem 1.
Follows immediately from lemma 1.1 and lemma 1.2.
Thus it can be seen that the intuitive concepts demonstrated by a Ferrers diagram can be used to derive formal theorems.

Theorem 2. p(n | at most m parts) = p(n + m | m parts)

Proof
Again this follows almost immediately from using Ferrers diagrams, since it is possible to generate maps between the two sets. Let {a1, ...., ak } be a partition of n with at most m parts. This partition has the following Ferrers diagram:
● ● ● ●.......● a1 dots
● ● ● .....● a2 dots
● ● ● ...● ak dots
Then add one dot to each of the k rows, and create m-k additional rows each with one dot to create the following Ferrers diagram.
○ ● ● ● ●.......● 1 + a1 dots
○ ● ● ● .....● 1 + a2 dots
○ ● ● ● ...● 1 + ak dots
○ 1 dot
○ 1 dot
m
This is a partition of n + m into m parts, and thus we have an injection from the partitions of n into at most m parts into partitions of n + m into m parts.
Conversely let {a1, ...., am} be a partition of n + m into m parts, producing the following Ferrers diagram:
● ● ● ●.......● a1 dots
● ● ● .....● a2 dots
● ● ● ...● am dots
Then removing one dot from each row produces a partition of n into at most m parts, and so the necessary bijection has been created. Thus by the Bernstein-Shroeder theorem there is a bijection between the two sets.
A further example of the possible uses of Ferrers diagrams is demonstrated by the proof of theorem 3 below. In order to state the theorem it is necessary to define the following term.

Definition 5 Self-conjugate

Partition {a1, ...., ak } of n is said to be a self conjugate if it is identical to its own conjugate

Theorem 3. p(n | partitions are self conjugate) = p(n | all parts are distinct and odd)

Proof
Let {a1, ...., ak } be a partition of n that is a self conjugate. Thus the Ferrers diagram of {a1, ...., ak } must be such that the ith row is equal in length to the ith column.
● ● ● ●.......● a1 dots
● ○ ○.....○ a2 dots
● ○
● ○
● ○ ● ...● ak dots
a1 a2 ak
Given this it is necessary to unfold the Ferrers diagram, which is to say that the outside column and row are combined to form a single row, followed by the remaining second row and column to form a second row and so on. This can be illustrated as follows:
● ● ● ●.......● ● ● ● 2a1 - 1 dots
○ ○ ○ ○.....○ 2a2 - 3 dots
The numbering of the first two rows is possible due to the fact that the partition is a self-conjugate. Indeed the ith row in the second Ferrers diagram has exactly 2(ai – (i + 1)) – 1 elements, and thus are odd. Moreover they are distinct since each ai is less than or equal to ai-1 , and so 2(ai -1– i) – 1 is distinctly greater than 2(ai – (i + 1)) – 1. Therefore we have the required injection.
Conversely, it is possible to provide the reverse operation on the Ferrers diagram of a partition with distinct and odd parts.
Hence the two sets must be of the same size, and sop(n | partitions are self conjugate) = p(n | all parts are distinct and odd).
As discussed above, there are a range of techniques available to prove facts about partitions of integers, of which one of the most useful are generating functions. This can be demonstrated by proving the following theorem.

Theorem 4 p(n | distinct parts) = p(n | odd parts)

Proof
Following the reasoning outlined in the section above, we can proceed as follows. In the generating function for p(n | distinct parts) each integer can appear 0 or 1 times, and therefore we have a generating factor of (1 + xn) for each integer n. Thus the overall generating function takes the form
(1 + x)(1 +x2)(1 +x3)(1 +x4)(1 +x5)(1 +x6)... (1)
In comparison the generating function for p(n | odd parts) is formed an identical way to that for p(n), with the even terms being removed:
It remains to show that 1 is identical to 2.
Multiplying each term n in 1 by (1 – xn)/(1 – xn) as follows gives us
However all terms in the nominator cancel out, which leaves 2. This completes the proof.

Section Four

Conclusion

The work above established four distinct theorems. The first three proofs demonstrated the use of Ferrers diagrams, with the connection between the analytical definitions and diagrammatic proof clarified in the first. It is clear that the Ferrers diagrams provided a distinct advantage in terms of brevity and intuition, and enable concise proofs to be given. The final theorem used generalising functions, and provided a straightforward proof of a deep theorem. Wilf (2000) also shows that the theorem can be proved by establishing bijections. It is important to note that this essay only touches on the surface of the work on partitions of integers, with a vast amount of fascinating results. Nonetheless it does make clear the fact that the most appropriate technique varies depending upon the problem that needs to be solved.


Post a Comment