0
$\begingroup$

I got confused with the stars and bars notation.

For example:

$x_1 + x_2 + x_3 + x_4 = 51$

How many solutions with empty cells allowed? How many solutions with empty cells forbidden?

Is it possible to "fix" 5 out of 51, and then distribute the rest using the empty cells allowed method?

If I'm not wrong, $({n+k-1\atop k-1})$ is the method to select with empty cells allowed.

$\endgroup$
  • $\begingroup$ Same number of solutions, $x_1+\cdots+x_4=47$ with empty cells forbidden, $x_1+\cdots+x_4=51$ with empty cells allowed. $\endgroup$ – Gerry Myerson Feb 10 '20 at 0:31
  • $\begingroup$ Did you mean "fix" $\color{red}{4}$ out of $51$? $\endgroup$ – N. F. Taussig Feb 10 '20 at 9:54
1
$\begingroup$

The formula $$\binom{n + k - 1}{k - 1}$$ gives the number of solutions of the equation $$x_1 + x_2 + \cdots + x_k = n$$ in the nonnegative integers.

To see why, let's consider the example of finding the number of solutions of the equation $$x_1 + x_2 + x_3 + x_4 = 10$$ in the nonnegative integers. A particular solution of this equation corresponds to the placement of $4 - 1 = 3$ addition signs in a row of $10$ ones. For instance, $$1 1 + + 1 1 1 1 1 + 1 1 1$$ corresponds to the solution $x_1 = 2$, $x_2 = 0$, $x_3 = 5$, $x_4 = 3$. The number of solutions corresponds to the number of ways we can place three addition signs in a row of ten ones, which is $$\binom{10 + 4 - 1}{4 - 1} = \binom{13}{3}$$ since we must choose which three of the thirteen positions required for ten ones and three addition signs will be filled with addition signs.

In the general case of finding the number of solutions of the equation $$x_1 + x_2 + \cdots + x_k = n$$ in the nonnegative integers, we must place $k - 1$ addition signs in a row of $n$ ones, which can be done in $$\binom{n + k - 1}{k - 1}$$ ways since we must select which $k - 1$ of the $n + k - 1$ positions required for $n$ ones and $k - 1$ addition signs will be filled with addition signs.

Therefore, the equation $$x_1 + x_2 + x_3 + x_4 = 51$$ has $$\binom{51 + 4 - 1}{4 - 1} = \binom{54}{3}$$ solutions in the nonnegative integers.

If we wish to find the number of solutions of the equation $$x_1 + x_2 + \cdots + x_k = n$$ the addition signs must be placed in the spaces between the ones.

Let's consider the example of finding the number of solutions of the equation $$x_1 + x_2 + x_3 + x_4 = 10$$ in the positive integers. A particular solution corresponds to the placement of $4 - 1 = 3$ addition signs in the $10 - 1 = 9$ spaces between the ones in a row of ten ones.
$$1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1$$ For instance, if we will the second, third, and seventh spaces with addition signs, we obtain $$1 1 + 1 + 1 1 1 1 + 1 1$$ which corresponds to the solution $x_1 = 2$, $x_2 = 1$, $x_3 = 4$, $x_4 = 2$. The number of such solutions is the number of ways we can place three addition signs in the nine spaces between successive ones in a row of ten ones, which is $$\binom{10 - 1}{4 - 1} = \binom{9}{3}$$

In the general case of finding the number of solutions of the equation $$x_1 + x_2 + \cdots + x_k = n$$ in the positive integers, we must select $k - 1$ of the $n - 1$ spaces between successive ones in a row of $n$ ones in which to insert an addition sign, which can be done in $$\binom{n - 1}{k - 1}$$ ways.

Therefore, the equation $$x_1 + x_2 + x_3 + x_4 = 51$$ has $$\binom{51 - 1}{4 - 1} = \binom{50}{3}$$ solutions in the positive integers.

Another way we could find the number of solutions of the equation $$x_1 + x_2 + \cdots + x_k = n$$ in the positive integers is to first place one object in each of the $k$ cells so that there is at least one object in each cell. Then we have $n - k$ objects left to distribute to $k$ cells without restriction. If we let $x_i'$ be the number of additional objects placed in cell $i$, where $1 \leq i \leq k$, then we need to solve the equation $$x_1' + x_2' + \cdots + x_k' = n - k$$ in the nonnegative integers. Using our formula for the number of solutions in the nonnegative integers gives $$\binom{n - k + k - 1}{k - 1} = \binom{n - 1}{k - 1}$$ which agrees with the formula we obtained above.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.