Difference between revisions of "Partition"
m (Reverted edits by Inscrutableroot (Inscrutableroot); changed back to last version by JBL) |
|||
| Line 5: | Line 5: | ||
A more fruitful way of studying partition numbers is through [[generating function]]s. The generating function for the partitions is given by <math>P(x)=\prod_{n=1}^\infty \frac{1}{1-x^n}</math>. Partitions can also be studied by using the [[Jacobi theta function]], in particular the [[triple product]]. The generating function approach and the theta function approach can be used to study many variants of the partition function, such as the number of ways to write a number ''n'' as the sum of odd parts, or of distinct parts, or of parts congruent to <math> 1\pmod 3</math>, etc. | A more fruitful way of studying partition numbers is through [[generating function]]s. The generating function for the partitions is given by <math>P(x)=\prod_{n=1}^\infty \frac{1}{1-x^n}</math>. Partitions can also be studied by using the [[Jacobi theta function]], in particular the [[triple product]]. The generating function approach and the theta function approach can be used to study many variants of the partition function, such as the number of ways to write a number ''n'' as the sum of odd parts, or of distinct parts, or of parts congruent to <math> 1\pmod 3</math>, etc. | ||
| + | == Ferrers Diagrams == | ||
| + | A [[Ferrers Diagram]] is a way to represent a certain partition of a number. The diagram consists of rows of dots. Each row represents a different addend in the partition. The rows are ordered in non-increasing order so that that the row with the most dots is on the top and the row with the least dots is on the bottom. | ||
| + | |||
| + | For example, 9 can be partitioned into 4 + 3 + 1 + 1 which would be represented by the following Ferrers Diagram: | ||
| + | |||
| + | {| style="margin: 1em auto 1em auto" | ||
| + | |- | ||
| + | | 4 | ||
| + | | <math> \bullet </math> | ||
| + | | <math> \bullet </math> | ||
| + | | <math> \bullet </math> | ||
| + | | <math> \bullet </math> | ||
| + | |- | ||
| + | | 3 | ||
| + | | <math> \bullet </math> | ||
| + | | <math> \bullet </math> | ||
| + | | <math> \bullet </math> | ||
| + | |- | ||
| + | | 1 | ||
| + | | <math> \bullet </math> | ||
| + | |- | ||
| + | | 1 | ||
| + | | <math> \bullet </math> | ||
| + | |} | ||
| + | |||
| + | === The Conjugate === | ||
| + | The '''conjugate''' of a Ferrers Diagram is formed by reflecting the diagram across its diagonal (the one starting in the top left of the diagram). This can also be interpreted as exchanging the rows for the columns. For example, consider our example from before but this time let's count the number of dots in each column: | ||
| + | |||
| + | {| style="margin: 1em auto 1em auto" | ||
| + | |- | ||
| + | | | ||
| + | |4 | ||
| + | |2 | ||
| + | |2 | ||
| + | |1 | ||
| + | |- | ||
| + | | 4 | ||
| + | | <math> \bullet </math> | ||
| + | | <math> \bullet </math> | ||
| + | | <math> \bullet </math> | ||
| + | | <math> \bullet </math> | ||
| + | |- | ||
| + | | 3 | ||
| + | | <math> \bullet </math> | ||
| + | | <math> \bullet </math> | ||
| + | | <math> \bullet </math> | ||
| + | |- | ||
| + | | 1 | ||
| + | | <math> \bullet </math> | ||
| + | |- | ||
| + | | 1 | ||
| + | | <math> \bullet </math> | ||
| + | |} | ||
| + | |||
| + | The original partition is 4 + 3 + 1 + 1 and the conjugate is 4 + 2 + 2 + 1. | ||
| + | |||
| + | == Generating Functions == | ||
| + | |||
| + | == Formulas == | ||
== Resources == | == Resources == | ||
* [http://www.artofproblemsolving.com/Resources/Papers/LaurendiPartitions.pdf Partitions of Integers by Joseph Laurendi] | * [http://www.artofproblemsolving.com/Resources/Papers/LaurendiPartitions.pdf Partitions of Integers by Joseph Laurendi] | ||
* [http://www.albanyconsort.com/JacobiTheta/JacobiTheta.pdf The Jacobi Theta Function by Simon Rubinstein-Salzedo] | * [http://www.albanyconsort.com/JacobiTheta/JacobiTheta.pdf The Jacobi Theta Function by Simon Rubinstein-Salzedo] | ||
Revision as of 16:53, 3 July 2006
A partition of a positive integer is a way of expressing it as the sum of other positive integers. Typically, one disregards the order of the summands. For example, there are three partitions of 3: 
.
There is no known, simple formula that gives the number of partitions of a number. There is, however, a rather ugly formula discovered by G. H. Hardy, J. E. Littlewood, and Srinivasa Ramanujan. However, this formula is rather unwieldy: it is not even known for which values of 
the number of partitions of is even, despite the presence of a formula!
A more fruitful way of studying partition numbers is through generating functions. The generating function for the partitions is given by 
. Partitions can also be studied by using the Jacobi theta function, in particular the triple product. The generating function approach and the theta function approach can be used to study many variants of the partition function, such as the number of ways to write a number n as the sum of odd parts, or of distinct parts, or of parts congruent to 
, etc.
Ferrers Diagrams
A Ferrers Diagram is a way to represent a certain partition of a number. The diagram consists of rows of dots. Each row represents a different addend in the partition. The rows are ordered in non-increasing order so that that the row with the most dots is on the top and the row with the least dots is on the bottom.
For example, 9 can be partitioned into 4 + 3 + 1 + 1 which would be represented by the following Ferrers Diagram:
| 4 | 
|
|
|
|
| 3 |
|
|
| |
| 1 |
| |||
| 1 |
|
The Conjugate
The conjugate of a Ferrers Diagram is formed by reflecting the diagram across its diagonal (the one starting in the top left of the diagram). This can also be interpreted as exchanging the rows for the columns. For example, consider our example from before but this time let's count the number of dots in each column:
| 4 | 2 | 2 | 1 | |
| 4 |
|
|
|
|
| 3 |
|
|
| |
| 1 |
| |||
| 1 |
|
The original partition is 4 + 3 + 1 + 1 and the conjugate is 4 + 2 + 2 + 1.
