Number Partitions

In mathematics, a partition of a natural number $ N $ is a writing of $ N $ as a sum of non-zero natural numbers (less than or equal to $ N $).

The partition counting function $ p(N) $ counts the number of partitions of an integer $ N $.

In 1918, G.H. Hardy and Srinivasa Ramanujan established an asymptotic formula describing the rapid growth of the partition function for large integers $ N $:

$$ p(n) \sim \frac{1}{4N \sqrt{3}} ~ e^{\pi \sqrt{\frac{2N}{3}}} $$

This formula shows that the number of partitions grows almost exponentially and allows us to estimate $ p(N) $ when the exact calculation becomes difficult.

The problem of giving change can be formulated as a partition problem with constraints: calculating the partitions of a given sum using only a fixed set of coins or bills.

Distinct partitions of an integer are partitions where the integers in the sum are all distinct from each other.

Non-distinct partitions include repeated numbers.

Ferrers diagrams are graphical representations of the partitions of a number using dots or boxes in rows.

Each row represents a number in the partition sum. Ferrers diagrams are a visual way to study the partitions of a number and understand their structure.

The Ramanujan congruences, discovered by the mathematician Srinivasa Ramanujan, are particularly remarkable congruences that concern the partition function $ p(N) $.

$$ \begin{align} p(5k+4) & \equiv 0 \pmod{5} \\ p(7k+5) & \equiv 0 \pmod{7} \\ p(11k+6) & \equiv 0 \pmod{11} \end{align} $$

— Partitions into even parts: All the terms of the partition are even.

— Partitions into odd parts: All the terms of the partition are odd.

This is a partition where all terms are identical.

These partitions are predictable by knowing the list of divisors of the number.