Partition of a Positive Integer
Partition of a Positive Integer
Rewriting a positive integer as the sum of smaller positive integers.
Worked Example
Problem: Find all partitions of the positive integer 5.
Step 1: Start with the partition that uses the number itself (one part).
5
Step 2: List partitions with largest part equal to 4.
4+1
Step 3: List partitions with largest part equal to 3. Make sure the remaining parts are less than or equal to 3.
3+2,3+1+1
Step 4: List partitions with largest part equal to 2. The remaining parts must each be at most 2.
2+2+1,2+1+1+1
Step 5: List partitions with largest part equal to 1.
1+1+1+1+1
Answer: The 7 partitions of 5 are: 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, and 1+1+1+1+1.
Another Example
Problem: How many partitions does the number 4 have?
Step 1: Start with the number itself as one part.
4
Step 2: Largest part 3.
3+1
Step 3: Largest part 2.
2+2,2+1+1
Step 4: Largest part 1.
1+1+1+1
Answer: The number 4 has exactly 5 partitions: 4, 3+1, 2+2, 2+1+1, and 1+1+1+1.
Frequently Asked Questions
What is the difference between a partition and a composition of an integer?
In a partition, order does not matter: 3+1 and 1+3 count as the same partition. In a composition, order matters: 3+1 and 1+3 are considered different compositions. So a given integer always has at least as many compositions as partitions.
Is there a formula for the number of partitions of n?
There is no simple closed-form formula. The number of partitions of n, written p(n), grows rapidly. For small values you can list them by hand: p(1)=1, p(2)=2, p(3)=3, p(4)=5, p(5)=7, p(6)=11. For larger values, mathematicians use generating functions or the Hardy–Ramanujan asymptotic formula to compute or approximate p(n).
Partition vs. Composition
A partition treats order as irrelevant (3+1 = 1+3), so it is a multiset of parts. A composition treats order as significant (3+1 ≠ 1+3), so it is a sequence of parts. The integer 4 has 5 partitions but 8 compositions.
Why It Matters
Integer partitions appear throughout combinatorics, algebra, and number theory. They are used to count arrangements, classify symmetric functions, and analyze probability distributions. The legendary mathematician Ramanujan discovered remarkable patterns in partition numbers, spurring deep results that continue to influence modern mathematics.
Common Mistakes
Mistake: Counting different orderings as separate partitions (e.g., treating 3+1 and 1+3 as two distinct partitions of 4).
Correction: In a partition, order does not matter. By convention, write parts in non-increasing order (e.g., 3+1, not 1+3) to avoid double-counting.
Mistake: Forgetting to include the number itself as a partition (e.g., listing partitions of 5 but omitting the single-part partition '5').
Correction: The number n by itself is always one of the partitions of n. It is the partition with exactly one part.
Related Terms
- Positive Number — Partitions are defined for positive integers
- Integers — The objects being partitioned
- Sum — A partition expresses a number as a sum
- Combinations — Related counting technique in combinatorics
- Combinatorics — Branch of math where partitions are studied
- Number Theory — Partition functions arise in number theory
- Factorial — Another fundamental counting concept