In how many ways can we partition a set into smaller subsets so the sum of the numbers in each subset is equal?

Solution 1:

Here is the tedious method that @antkam mentioned:

Consider the sums adding to 9. You have:

The set that contains $9$. The set that contains $8$ must contain $1$. The set that contains $7$ must contain $2$. The set that contains $6$ must contain $3$ (Because it cannot contain $1$ and $2$, which are already used). The set that contains $5$ must contain $4$ (Because $1, 3$ are both used). There is but one way to distribute the numbers $1$ through $9$. All that is left is to choose where to put $0$. For that, there are $5$ ways (Any set can have $0$ in it).

Next, consider when the sum is $15$ ($3$ sets). We want to consider the most restrictive numbers first (As this will eliminate possibilities the fastest): Let's write out all possible ways of summing to $15$ that contain a $9$ in non-zero digits:

$1+2+3+9, 1+5+9, 2+4+9, 6+9$

Next, do the same for $8$:

$1+2+4+8, 1+6+8, 2+5+8, 3+4+8, 7+8$

We only need to pick the first two sets (one set containing 9, one set containing 8). The rest of the digits will be in the third set. And, we can place the zero into any of the three sets, so every valid partition of the nonzero elements can be turned into three distinct partitions when we add in the zero.

$\{1,2,3,9\}$ can only pair with $\{7,8\}$: $3$ ways

$\{1,5,9\}$ can pair with $\{3,4,8\}$ or $\{7,8\}$: $6$ ways

$\{2,4,9\}$ can pair with $\{1,6,8\}$ or $\{7,8\}$: $6$ ways

$\{6,9\}$ can pair with $\{1,2,4,8\}$, $\{2,5,8\}$, $\{3,4,8\}$, or $\{7,8\}$: $12$ ways

Adding it all up, that is $5+3+6+6+12=32$ ways.

Solution 2:

I think the key is understanding that $0$ can go wherever and that every number must go somewhere. Set aside $0$ for the moment.

When $n=5$ we have $s=9$. We can use an inductive reasoning as follows:

• $9$ must be alone, so we get $\{9\}$ and that leaves $\{1,2,3,4,5,6,7,8\}$.
• $8$ can only be paired with $1$ to reach $s=9$, so we get $\{1,8\}$ and that leaves $\{2,3,4,5,6,7\}$.
• $7$ can only be paired with $2$ to reach $s = 9$, so we get $\{2,7\}$ and that leaves $\{3,4,5,6\}$.
• Proceeding in this manner, we find that the subsets look like $\big\{\{9\}, \{1,8\}, \{2,7\}, \{3,6\}, \{4,5\}\big\}$.

All that remains is to assign $0$ to some subset, so we get $5$ possibilities for $s=9$.

When $n=3$ we have $s=15$ and things get slightly more complicated. We are still setting $0$ aside for this.

First, notice that $9$ and $8$ must go towards different subsets. We will then find how to fill up the $9$ subset, and for each such manner, we'll find out how to fill up the $8$ subset. The remaining numbers will form their own subset.

The idea behind this is that starting from the larger number is better because the remaining sum is smaller, so there are fewer options to consider.

So, we have $\{1,2,3,4,5,6,7\}$ and we have to figure out in how many ways we can pick elements from it to reach a sum of $6$. Now, proceeding as before, we find that the possibilities are $\big\{\{6\}, \{1,5\}, \{2,4\}, \{1,2,3\}\big\}$.

• If the $9$ susbset is $\{6,9\}$, we are left with $\{1,2,3,4,5,7\}$ and we have to figure out in how many ways we can pick elements from it to reach a sum of $7$ (in order to complete the $8$ subset). We proceed as before and arrive at $\big\{\{7\}, \{2,5\}, \{3,4\}, \{1,2,4\}\big\}$. This gives us $4$ additional possibilities before adding $0$.

• If the $9$ susbset is $\{1,5,9\}$, we are left with $\{2,3,4,6,7\}$ and we have to figure out in how many we can pick elements from it to reach a sum of $7$. We proceed as before and arrive at $\big\{\{7\}, \{3,4\}\big\}$. This gives us $2$ additional possibilities before adding $0$.

• If the $9$ susbset is $\{2,4,9\}$, we are left with $\{1,3,5,6,7\}$ and we have to figure out in how many we can pick elements from it to reach a sum of $7$. We proceed as before and arrive at $\big\{\{7\}, \{1,6\}\big\}$. This gives us $2$ additional possibilities before adding $0$.

• Finally if the $9$ susbset is $\{1,2,3,9\}$, we are left with $\{4,5,6,7\}$ and we have to figure out in how many we can pick elements from it to reach a sum of $7$. Clearly, the only way is picking a lone $7$ which gives us $1$ additional possibility before adding $0$.

So we have $9$ possibilities without $0$. For each such configuration, we have $3$ ways to assign $0$ to a subset, which gives us $9\times 3 = 27$ total possibilities in the $n=3$ case.

In total, this gives us $27+5 = 32$ possibilities.

Now, this is a structured way of thinking to approach this problem (tackle the large numbers to reduce leftover sum possibilities), but there is of course a more... operational approach. Generating functions are a handy tool for any combinatorist to have.

One way to consider this problem if you have computational power at hand is as follows.

When $n=3$, we consider the product

$$\prod_{i=0}^9 (x_1^i+x_2^i+x_3^i).\tag{$*$}$$

Expanding this product, we'll find a sum of monomials of the form $c\cdot x_1^ax_2^bx_3^c$. Each such monomial can be interpreted as follows: there are $c$ ways to partition the set $\{0,1,2,\dots,9\}$ such that the first subset sums to $a$, the second subset sums to $b$ and the third subset sums to $c$.

Indeed, when expanding the product, at each step we must choose which $x_i^j$ we're taking. Choosing $x_i^j$ means assigning the element $j$ from $\{0,1,2,\dots,9\}$ to the $i$-th subset.

Since we want all our subsets to sum to $s=15$, we're then interested in the coefficient of $x_1^{15}x_2^{15}x_3^{15}$ in the expansion of $(*)$. Of course, since we also don't care about the order of our subsets, we have to divide the end result by $3!$.

When I say we don't care about the order of our subsets, I mean that the family of subsets $\big\{\{0,6,9\}, \{7,8\}, \{1,2,3,4,5\}\big\}$ is just as good as $\big\{\{7,8\}, \{1,2,3,4,5\}, \{0,6,9\}\big\}$ or any other permutation.

You can check with Wolfram Online Notebooks (or your choice of math software) using 1/3! * Coefficient[Product[(x^i+y^i+z^i),{i,0,9}], x*y*z,15] that the answer comes out to $27$, like we did when counting by hand.

Similarly, to count the number of possibilities for $n=5$ we'd look at

$$\frac1{5!}\left[x_1^9x_2^9x_3^9x_4^9x_5^9\right]\left(\prod_{i=0}^9 (x_1^i+x_2^i+x_3^i+x_4^i+x_5^i)\right).$$

You can check with 1/5! * Coefficient[Product[(a^i+b^i+c^i+d^i+e^i),{i,0,9}], a*b*c*d*e, 9] that the answer comes out to $5$, like we did when counting by hand.

I will say, however, that this is not a computationally cheap or fast way to obtain the answer (if you are interested in computationally feasible ways to approach this problem, it is traditionally handled with a technique called dynamic programming). So, if you can afford to let the computer do the calculations for you while you're doing something else, go ahead. Of course, you can also expand the product by hand yourself if you prefer.

You can also combine both methods. This approach clearly suffers at higher values of $n$, because the number of monomials in the product expansion grows too fast with $n$. On the other hand, for higher values of $n$, $s$ is lower and we see from the example that the inductive reasoning becomes simpler, with less combinations to consider.

Finally, this approach also tackles other variations of this problem, like specifying different sums for different subsets and also generalizing to ordered subsets.