Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Partition (combinatorics)"

(New page: 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 t...)
 
m (→‎A Variation)
 
(10 intermediate revisions by 8 users not shown)
Line 1: Line 1:
−
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: <math>3 = 2+1 =1+1+1</math>.  
+
A '''partition''' of a [[nonnegative]] [[integer]] is a way of expressing it as the unordered sum of other [[positive integer]]s.  For example, there are three partitions of 3: <math>3 = 2+1 =1+1+1</math>.  Each of the [[summand]]s is a ''part'' of the partition.
  
−
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 <math>{n}</math> the number of partitions of <math>{n}</math> is [[even integer | even]], despite the presence of a formula!
+
The '''partition function''' <math>P(n)</math> gives the number of partitions of <math>n</math>. There is an exact formula for <math>P(n)</math>, discovered by [[G. H. Hardy]], [[J. E. Littlewood]], and [[Srinivasa Ramanujan]]. However, this formula is unwieldy: it is not even known for which values of <math>{n}</math> the number of partitions of <math>{n}</math> is [[even integer | even]], despite the presence of a formula! No simpler formula is known, and the existence of such a formula is doubtful.
  
−
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 integer | odd]] parts, or of distinct parts, or of parts [[equivalent]] to <math> 1\pmod 3</math>, etc.
+
A fruitful way of studying partition numbers is through [[generating function]]s. The generating function for the sequence <math>\{P(n)\}_{n \geq 0}</math> is given by <math>F(x)= \sum_{n \geq 0}P(n) x^n = \prod_{n=1}^\infty \frac{1}{1-x^n}</math>. Partitions can also be studied by using the [[Jacobi theta function]], in particular the [[Jacobi 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 <math>n</math> as the sum of [[odd integer | odd]] parts, or of distinct parts, or of parts [[modular arithmetic | equivalent]] to <math> 1\pmod 3</math>, etc.
 +
 
 +
== List of Partitions and Values of the Partition Function for Small <math>n</math>==
 +
The ''empty partition'' (with no parts) is the unique partition of <math>0</math>, so <math>P(0) = 1</math>.
 +
 
 +
The unique partition of <math>1</math> is <math>1</math>, so <math>P(1) = 1</math>.
 +
 
 +
<math>2 = 1 + 1</math>, so <math>P(2) = 2</math>.
 +
 
 +
<math>3 = 2 + 1 = 1 + 1 + 1</math>, so <math>P(3) = 3</math>.
 +
 
 +
<math>4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1</math>, so <math>P(4) = 5</math>.
 +
 
 +
<math>5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1</math>, so <math>P(5) = 7</math>.
 +
 
 +
Partitions are often written in ''tuple notation'', so we might denote the partitions of <math>4</math> by <math>(4), (3, 1), (2, 2), (2, 1, 1)</math> and <math>(1, 1, 1, 1)</math>.  This notation is often further abbreviated to ''word notation'' (by dropping the parentheses and commas, so <math>(3, 1, 1)</math> becomes <math>311</math>) or by indicating multiplicities with exponential notation (so <math>(3, 1, 1)</math> becomes <math>(3, 1^2)</math>). 
 +
 
 +
Using this last notation, the partitions of <math>6</math> are <math>(6), (5, 1), (4, 2), (4, 1^2), (3^2), (3, 2, 1), (3, 1^3), (2^3), (2^2, 1^2), (2, 1^4)</math> and <math>(1^6)</math>, so <math>P(6) = 11</math>.  One could continue this computation to find that <math>P(7) = 15</math>, <math>P(8) = 22</math>, <math>P(9) = 30</math>, <math>P(10) = 42</math>, and so on.
  
 
== Ferrers Diagrams ==
 
== 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.
+
A [[Ferrers diagram]] is a way to represent partitions geometrically.  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:
+
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"
 
{| style="margin: 1em auto 1em auto"
Line 31: Line 48:
  
 
=== The Conjugate ===
 
=== 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:
+
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"
 
{| style="margin: 1em auto 1em auto"
Line 63: Line 80:
 
== Generating Functions ==
 
== Generating Functions ==
  
−
[[Generating Functions]] can be used to deal with problems involving partitions.  First we will find the generating function for the number of ways to partition an integer <math> n </math>.
+
[[Generating functions]] can be used to deal with some problems involving partitions.  Here we derive the generating function for the number of partitions of <math>n</math>.
  
−
Consider partitioning <math> n </math> into addends that are equal to just 1.  The generating function for this is <math> 1 + x + x^2 + \cdots </math> since there is only one way to represent <math> n </math> as the sum of 1's.
+
Consider partitioning <math>n</math> into addends that are equal to 1.  The generating function for this is <math>1\cdot x^0 + 1\cdot x + 1\cdot x^2 + \ldots </math> since there is only one way to represent <math>n</math> as the sum of 1s.
  
−
Consider partitioning numbers using just 2's as addends.  There's 1 way to partition 0 into 2's, 0 ways to partition 1 into 2's, 1 way to partition 2 into 2's and so forth.  Therefore, the generating function is <math> 1 + x^2 + x^4 +\cdots </math>.
+
Consider partitioning numbers using just 2s as addends.  There is one way to partition 0 into 2s, zero ways to partition 1 into 2s, one way to partition 2 into 2s, and so forth.  Therefore, the generating function for this type of partition is <math> 1 + x^2 + x^4 +\cdots </math>.
  
 
We can proceed in this manner to find that the generating function for the number of ways to partition <math> n </math> into addends equal to <math> k </math> is <math> 1 + x^k + x^{2k} + x^{3k} + \cdots </math>.
 
We can proceed in this manner to find that the generating function for the number of ways to partition <math> n </math> into addends equal to <math> k </math> is <math> 1 + x^k + x^{2k} + x^{3k} + \cdots </math>.
  
−
Now, multiplying each of these generating functions will give us the generating function for partitioning <math> n </math> in general which is
+
Now, we generate every partition of <math>n</math> by choosing some number of parts to be equal to 1, some other number of parts to be equal to 2, and so on.  Thus, we get the generating function for the partition function of <math>n</math> by multiplying the generating functions for partitions into just 1s, partitions into just 2s, and so on.  This gives us the expression
  
−
<center><math> (1 + x + x^2 + \cdots + )(1 + x^2 + x^4 + \cdots )(1 + x^3 + x^6 + \cdots)\cdots.</math></center>
+
<center><math> (1 + x + x^2 + \cdots + )(1 + x^2 + x^4 + \cdots )(1 + x^3 + x^6 + \cdots)\cdots</math>.</center>
  
−
Using the formula for the sum of an infinite [[geometric sequence]] we can express this in the more compact form:
+
Using the formula for the sum of an [[infinite]] [[geometric sequence]] we can express this in the more compact form
  
−
<center><math> \frac 1{1-x}\cdot \frac 1{1-x^2}\cdot \frac 1{1-x^3}\cdots </math></center>
+
<center><math> \frac 1{1-x}\cdot \frac 1{1-x^2}\cdot \frac 1{1-x^3}\cdots = \prod_{n \geq 1} \frac{1}{1 - x^n}</math>.</center>
  
  
  
−
== Formulas ==
+
== A Variation ==
−
An interesting theorem is that the numbers of partitions ''consisitng of only consecutive positive integers'' of n is the number of odd [[divisors]] of n.
+
An interesting theorem is that the number of partitions ''consisting of only consecutive positive integers'' of <math>n</math> is the number of odd [[divisor|divisors]] of <math>n</math>.
  
  
 
Proof:
 
Proof:
−
Let <math>a</math> be the smallest integer in such a partition, and <math>k</math> be the number of integers in this partition, then we have:
+
Let <math>a</math> be the smallest part in such a partition and let <math>k</math> be the number of parts.  Then we have
−
 
 
−
 
 
−
<math>n = a + (a+1) + (a+2) + \dots + (a+k-1)</math>
 
  
−
<math>n = ka + (1 + 2 + \dots + k-1)</math>
+
<math>n = a + (a+1) + (a+2) + \dots + (a+k-1)
−
 
+
= ka + (1 + 2 + \dots + k-1)  
−
<math>n = ka + \frac{k(k-1)}{2}</math>
+
= ka + \frac{k(k-1)}{2}
 +
</math>, so
  
 
<math>2n = 2ka + k(k-1)</math>
 
<math>2n = 2ka + k(k-1)</math>
Line 103: Line 118:
 
<math>a = \frac{2n-k^2 + k}{2k}</math>
 
<math>a = \frac{2n-k^2 + k}{2k}</math>
  
 +
and finally
  
−
and finally:
+
<math>a = \frac{n}{k} + \frac{1-k}{2}</math>.
−
 
 
−
 
 
−
<math>a = \frac{n}{k} + \frac{1-k}{2}</math>
 
  
  
Line 134: Line 147:
  
  
−
Since our count includes all the possible partitions, and the number of valid partitions is equal to the number of partitions that contain negative integers, the number of valid partitions must be exactly half of our original count.  Therefore, the total number of such partitions is <math>s</math>, which is the number of odd divisors of <math>n</math>.
+
Since our count includes all the possible partitions, and the number of valid partitions is equal to the number of partitions that contain negative integers, the number of valid partitions must be exactly half of our original count.  Therefore, the total number of such partitions is <math>s</math>, which is the number of odd divisors of <math>n</math>.
  
 
== 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]
−
 
+
* [http://www.research.att.com/~njas/sequences/A000041 Sequence A000041 in the OEIS -- the partition function]
 
== See also ==
 
== See also ==
 
* [[Combinatorics]]
 
* [[Combinatorics]]

Latest revision as of 13:24, 17 September 2017

A partition of a nonnegative integer is a way of expressing it as the unordered sum of other positive integers. For example, there are three partitions of 3: $3 = 2+1 =1+1+1$. Each of the summands is a part of the partition.

The partition function $P(n)$ gives the number of partitions of $n$. There is an exact formula for $P(n)$, discovered by G. H. Hardy, J. E. Littlewood, and Srinivasa Ramanujan. However, this formula is unwieldy: it is not even known for which values of ${n}$ the number of partitions of ${n}$ is even, despite the presence of a formula! No simpler formula is known, and the existence of such a formula is doubtful.

A fruitful way of studying partition numbers is through generating functions. The generating function for the sequence $\{P(n)\}_{n \geq 0}$ is given by $F(x)= \sum_{n \geq 0}P(n) x^n = \prod_{n=1}^\infty \frac{1}{1-x^n}$. Partitions can also be studied by using the Jacobi theta function, in particular the Jacobi 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 equivalent to $1\pmod 3$, etc.

List of Partitions and Values of the Partition Function for Small $n$

The empty partition (with no parts) is the unique partition of $0$, so $P(0) = 1$.

The unique partition of $1$ is $1$, so $P(1) = 1$.

$2 = 1 + 1$, so $P(2) = 2$.

$3 = 2 + 1 = 1 + 1 + 1$, so $P(3) = 3$.

$4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1$, so $P(4) = 5$.

$5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1$, so $P(5) = 7$.

Partitions are often written in tuple notation, so we might denote the partitions of $4$ by $(4), (3, 1), (2, 2), (2, 1, 1)$ and $(1, 1, 1, 1)$. This notation is often further abbreviated to word notation (by dropping the parentheses and commas, so $(3, 1, 1)$ becomes $311$) or by indicating multiplicities with exponential notation (so $(3, 1, 1)$ becomes $(3, 1^2)$).

Using this last notation, the partitions of $6$ are $(6), (5, 1), (4, 2), (4, 1^2), (3^2), (3, 2, 1), (3, 1^3), (2^3), (2^2, 1^2), (2, 1^4)$ and $(1^6)$, so $P(6) = 11$. One could continue this computation to find that $P(7) = 15$, $P(8) = 22$, $P(9) = 30$, $P(10) = 42$, and so on.

Ferrers Diagrams

A Ferrers diagram is a way to represent partitions geometrically. 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 $\bullet$ $\bullet$ $\bullet$ $\bullet$
3 $\bullet$ $\bullet$ $\bullet$
1 $\bullet$
1 $\bullet$

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 $\bullet$ $\bullet$ $\bullet$ $\bullet$
3 $\bullet$ $\bullet$ $\bullet$
1 $\bullet$
1 $\bullet$

The original partition is 4 + 3 + 1 + 1 and the conjugate is 4 + 2 + 2 + 1.

Generating Functions

Generating functions can be used to deal with some problems involving partitions. Here we derive the generating function for the number of partitions of $n$.

Consider partitioning $n$ into addends that are equal to 1. The generating function for this is $1\cdot x^0 + 1\cdot x + 1\cdot x^2 + \ldots$ since there is only one way to represent $n$ as the sum of 1s.

Consider partitioning numbers using just 2s as addends. There is one way to partition 0 into 2s, zero ways to partition 1 into 2s, one way to partition 2 into 2s, and so forth. Therefore, the generating function for this type of partition is $1 + x^2 + x^4 +\cdots$.

We can proceed in this manner to find that the generating function for the number of ways to partition $n$ into addends equal to $k$ is $1 + x^k + x^{2k} + x^{3k} + \cdots$.

Now, we generate every partition of $n$ by choosing some number of parts to be equal to 1, some other number of parts to be equal to 2, and so on. Thus, we get the generating function for the partition function of $n$ by multiplying the generating functions for partitions into just 1s, partitions into just 2s, and so on. This gives us the expression

$(1 + x + x^2 + \cdots + )(1 + x^2 + x^4 + \cdots )(1 + x^3 + x^6 + \cdots)\cdots$.

Using the formula for the sum of an infinite geometric sequence we can express this in the more compact form

$\frac 1{1-x}\cdot \frac 1{1-x^2}\cdot \frac 1{1-x^3}\cdots = \prod_{n \geq 1} \frac{1}{1 - x^n}$.


A Variation

An interesting theorem is that the number of partitions consisting of only consecutive positive integers of $n$ is the number of odd divisors of $n$.


Proof: Let $a$ be the smallest part in such a partition and let $k$ be the number of parts. Then we have

$n = a + (a+1) + (a+2) + \dots + (a+k-1) = ka + (1 + 2 + \dots + k-1) = ka + \frac{k(k-1)}{2}$, so

$2n = 2ka + k(k-1)$

$2ka = 2n-k(k-1)$

$2ka = 2n - k^2 + k$

$a = \frac{2n-k^2 + k}{2k}$

and finally

$a = \frac{n}{k} + \frac{1-k}{2}$.


Let's allow negative integers in our partition for a moment, and let $s$ denote the number of odd divisors of $n$. Now we consider the two possible cases:


Case 1: $\frac{1-k}{2}$ is an integer.


Since the expression on the right hand side must be an integer, this implies that $k | n$. Also, for $\frac{1-k}{2}$ to be an integer, $1-k$ must be divisible by 2, which implies that $k$ is odd. Therefore, as long as $k$ is an odd divisor of $n$, we can find $k$ consecutive integers starting with $a$ that adds up to $n$. Therefore, in this case the number of solutions is equal to $s$.


Case 2: $\frac{1-k}{2}$ is not an integer.


For the right hand side to still be an integer, we must have $\frac{n}{k} = \frac{t}{2}$ for some odd integer $t$. Since $\frac{1-k}{2}$ is not an integer, $1-k$ must be odd, and therefore $k$ must be even. expressing $n$ in the form $2^a\cdot b$ with $b$ being an odd integer, we see that $\frac{n}{k} = \frac{t}{2}$ if and only if $k = 2^{a+1} \cdot d$, where $d$ is any odd divisor of $n$. As the result, the number of solutions in this case is also equal to $s$.


The two cases combined gives us $2s$ solutions. However, this includes partitions with negative integers. However, since $n$ is positive, the partition with negative integers must be of the form:


$-a - (a-1) - (a-2) - \dots - 1 + 1 + 2 +\dots + a + a+1 + \dots + b$


Where $b > a$. As the result, we can cancel out the negative integers with the corresponding additive inverses to produce a valid partition. Similarity, we can go from a valid partition to one that contains negative integers by adding all the positive integers before the smallest member, along with the corresponding additive inverses. As the result, we established a bijection between valid partitions with the partitions containing negative integers.


Since our count includes all the possible partitions, and the number of valid partitions is equal to the number of partitions that contain negative integers, the number of valid partitions must be exactly half of our original count. Therefore, the total number of such partitions is $s$, which is the number of odd divisors of $n$.

Resources

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Partition_(combinatorics)&oldid=87543"