Triangle of partition numbers explained

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 n th row gives the partition numbers p _{1(n),} p _{2(n),} ... , p _{n(n)} :^[1]

	1	2	3	4	5	6	7	8	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$$p\_k(n)=p\_(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

n th row is the partition number p(n) . These numbers form the sequenceomitting 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.

Notes and References

1. cs2.