How to Find the Partition of a Number?

Finding the partition of a number involves identifying the different ways a positive integer can be written as a sum of positive integers. This concept is fundamental in number theory.

Finding the "partition" of a number can refer to two related tasks: listing all possible partitions or finding the total number of partitions.

In number theory, the partition function p(n) represents the number of possible partitions of a non-negative integer n.

Let's explore both aspects.

Listing All Partitions of a Number

To list all the partitions of a positive integer n, you systematically break down n into sums of positive integers. The order of the summands doesn't matter (e.g., 3+1 is the same partition as 1+3). Typically, partitions are written with the summands in non-increasing order for consistency.

Methodical Approach:

You can list partitions by starting with the number itself, then decreasing the largest summand and adjusting the remaining sum.

1. Start with the number n itself (this is one partition: n).
2. Next, try n-1 as the largest summand, and find all partitions of the remaining 1.
3. Then, try n-2 as the largest summand, and find all partitions of the remaining 2, and so on.
4. Continue this process until the largest summand is 1.

Example: Listing Partitions for n = 4

Let's list the partitions for the number 4 using this method:

• Largest summand is 4: 4
• Largest summand is 3: 3 + 1 (remaining sum is 1, partition of 1 is just 1)
• Largest summand is 2:
  • Remaining sum is 2. Partitions of 2 are 2 and 1+1. So, we get 2 + 2 and 2 + 1 + 1.
• Largest summand is 1:
  • Remaining sum is 3. Partitions of 3 are 3, 2+1, 1+1+1. Since the largest summand must be 1, the only valid partition starting with 1 is 1 + 1 + 1 + 1.

Combining these, the five partitions of 4 are:

• 4
• 3 + 1
• 2 + 2
• 2 + 1 + 1
• 1 + 1 + 1 + 1

This matches the example provided in the reference: p(4) = 5 because the integer 4 has the five partitions 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 3, 2 + 2, and 4 (note the different order in the reference, but the set of partitions is the same).

Table of Partitions for n=4:

Partition
4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

Listing partitions can become complex for larger numbers and is often done with the help of algorithms.

Finding the Number of Partitions p(n)

The question "How to find the partition of a number?" might also imply finding the total count of distinct partitions, which is given by the partition function p(n). Calculating p(n) for larger numbers is a significant problem in number theory.

While there is no simple closed-form formula for p(n), there are various methods and formulas to calculate it:

• Generating Functions: The generating function for p(n) is infinite product:
  $$ \sum{n=0}^\infty p(n)x^n = \prod{k=1}^\infty \frac{1}{1-x^k} $$
  The coefficients of the powers of x in the expansion of this product give the values of p(n) (with p(0)=1).
• Recurrence Relations: p(n) can be calculated using recurrence relations, such as the one derived from Euler's pentagonal number theorem:
  $$ p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-12) + p(n-15) - \dots $$
  The numbers subtracted or added to n are the generalized pentagonal numbers $g_k = \frac{k(3k-1)}{2}$ for k = ±1, ±2, ±3, ... (1, 2, 5, 7, 12, 15, ...). The signs alternate in pairs (+, +, -, -, +, +, ...). The recurrence holds for n > 0, with p(0)=1 and p(k)=0 for k < 0.
• Asymptotic Formulas: For very large values of n, there are asymptotic formulas (like the Hardy-Ramanujan formula) that provide close approximations for p(n).

Example: Calculating p(4) using Recurrence

Let's check the recurrence for p(4):
p(4) = p(4-1) + p(4-2) - p(4-5) - p(4-7) + ...
p(4) = p(3) + p(2) - p(-1) - p(-3) + ...

We need values for p(1), p(2), p(3).

• p(1): 1 (partition: 1)
• p(2): 2 (partitions: 2, 1+1)
• p(3): 3 (partitions: 3, 2+1, 1+1+1)

Using the recurrence:
p(4) = p(3) + p(2) - p(-1)
p(4) = 3 + 2 - 0 (since p(k)=0 for k<0)
p(4) = 5

This confirms p(4) = 5, matching the reference example and the list we generated.

In summary, finding the partition of a number can mean either listing its unique representations as a sum of positive integers or calculating the count of such representations using the partition function p(n).