Login
Login

Triangle of partition numbers

In the number theory of integer partitions, the numbers p_k(n) denote both the number of partitions of n into exactly k parts (that is, sums of k positive integers that add to n), and the number of partitions of n into parts of maximum size exactly k. These two types of partition are in bijection with each other, by a diagonal reflection of their Young diagrams. Their numbers can be arranged into a triangle, the triangle of partition numbers, in which the nth row gives the partition numbers p_1(n), p_2(n), \dots, p_n(n):{{cite OEIS|A008284|Triangle of partition numbers|mode=cs2}}

class="wikitable" style="margin-left:1.6em"
{{diagonal split header|n | k}}

! width="50" | 1

! width="50" | 2

! width="50" | 3

! width="50" | 4

! width="50" | 5

! width="50" | 6

! width="50" | 7

! width="50" | 8

! width="50" | 9

1

| 1 || || || || || || || ||

2

| 1 || 1 || || || || || || ||

3

| 1 || 1 || 1 || || || || || ||

4

| 1 || 2 || 1 || 1 || || || || ||

5

| 1 || 2 || 2 || 1 || 1 || || || ||

6

| 1 || 3 || 3 || 2 || 1 || 1 || || ||

7

| 1 || 3 || 4 || 3 || 2 || 1 || 1 || ||

8

| 1 || 4 || 5 || 5 || 3 || 2 || 1 || 1 ||

9

| 1 || 4 || 7 || 6 || 5 || 3 || 2 || 1 || 1

Recurrence relation

Analogously to Pascal's triangle, these numbers may be calculated using the recurrence relation{{citation

| last = Arndt | first = Jörg

| contribution = 16.4.1: Unrestricted partitions and partitions into m parts

| pages = 345–348

| publisher = Springer

| title = Matters Computational: Ideas, Algorithms, Source Code

| url = https://jjj.de/fxt/fxtbook.pdf

| year = 2011}}

p_k(n)=p_{k-1}(n-1)+p_k(n-k).

As base cases, p_1(1)=1, and any value on the right hand side of the recurrence that would be outside the triangle can be taken as zero. This equation can be explained by noting that each partition of n into k pieces, counted by p_k(n), can be formed either by adding a piece of size one to a partition of n-1 into k-1 pieces, counted by p_{k-1}(n-1), or by increasing by one each piece in a partition of n-k into k pieces, counted by p_k(n-k).

Row sums and diagonals

In the triangle of partition numbers, the sum of the numbers in the nth row is the partition number p(n). These numbers form the sequence

{{bi|left=1.6|1, 2, 3, 5, 7, 11, 15, 22, ...,}}

omitting the initial value p(0)=1 of the partition numbers.

Each diagonal from upper left to lower right is eventually constant, with the constant parts of these diagonals extending approximately from halfway across each row to its end. The values of these constants are the partition numbers 1, 1, 2, 3, 5, 7, ... again.{{citation

| last = Hopkins | first = Brian

| issue = Supplement

| journal = Integers

| mr = 2521954

| pages = A6:1–A6:11

| title = Column-to-row operations on partitions: the envelopes

| url = https://math.colgate.edu/~integers/j6proc/j6proc.pdf

| volume = 9

| year = 2009}}

References

{{reflist}}

Category:Triangles of numbers

Category:Integer partitions