P(5, 1) = 1, [5]
P(5, 2) = 2, [4, 1], [3, 2]
P(5, 3) = 2, [3, 1, 1], [2, 2, 1]
P(5, 4) = 1, [2, 1, 1, 1]
P(5, 5) = 1, [1, 1, 1, 1, 1]

P(n, k) = P(n, 1) + P(n, 2) + P(n, 3) + \cdots + P(n, k - 1) + P(n, k)

P(n, 1) = 1, P(n, n) = 1

P(n, k) = P(n -1, k-1) + P(n-k, k)

P(n, k) = P(n-k, 1) + P(n-k, 2) + \cdots + P(n-k, k)