Partitions of Integers: Practice Problems and Solutions - Part I

Combinatorics Problems and Solutions - Section 5

This is a part of Mr. Stolyarov's compilation of Free Combinatorics Problems and Solutions.

Problem 5a (Source:Brualdi, Richard A. Introductory Combinatorics. First Edition. 1977): "A partition of a positive integer n is a representation of n as the sum of positive integers. The order of the integers in the sum is not taken into account. For instance, 6 = 3 + 3, 6 = 6, and 6 = 1 + 1 + 2 + 2 are partitions of 6. Let p_n equal the number of partitions of n. Define p₀ = 1."

"Show that p_n equals the number of partitions of the multiset S = {n∙a} into unordered multisets whose number is not specified."

Solution 5a by Mr. Stolyarov. We consider some partition of n where n = b₁ + b₂ + ... + b_k.

Such a partition corresponds to a partition of S = {n∙a} into the following k subsets:
{b₁∙a},{b₂∙a},..., {b_k∙a}.

Likewise, any partition of S = {n∙a} into the m subsets
{c₁∙a},{c₂∙a},..., {c_m∙a} will correspond to a partition of n where n = c₁ + c₂ + ... + c_m.

So there is a one-to-one correspondence between partitions of S = {n∙a} into unordered multisets and partitions of n. So p_n = the number of partitions of S = {n∙a} into unordered multisets. Q. E. D.

Problem 5b (Source:Brualdi, Richard A. Introductory Combinatorics. First Edition. 1977): "Show that p_n equals the number of solutions to the equation n = 1x₁ + 2x₂ + ... + nx_n in the nonnegative integers x₁, x₂, ... , x_n."

Solution 5b by Mr. Stolyarov. A partition of n can contain some nonzero quantity of any of the numbers 1 through n but no nonzero quantity of any of the numbers greater than n. For any particular partition, the value of x₁ is how many 1's are contained in the partition (at most n), the value of x₂ is how many 2's are contained in the partition (at most n/2),..., the value of x_n is how many n's are contained in the partition (at most 1). So any solution of the given equation in nonnegative integers (x₁, x₂,..., x_n) is equivalent to a partition with x₁ 1's, x₂ 2's,..., and x_n n's. Thus, the number of solutions to the given equation in nonnegative integers is equal to the number of partitions of n = p_n. Q. E. D.