9
$\begingroup$

The Number Of Integer Solutions Of Equations

An approach is to find the number of distinct non-negative integer-valued vectors $(x_1,x_2,...,x_r)$ such that $$x_1 + x_2 + ... + x_r = n$$

  • Firstly, considering the number of positive integer-valued solutions.

    An approach to solving this problem for positive integer-valued solutions is to imagine that you have $n$ indistinguishable objects lined up and that you want to divide them into $r$ nonempty groups. To do so, you can select $r-1$ of the $n-1$ spaces between adjacent objects as the dividing points. See the diagram below for a visual representation.

$$0_\wedge0_\wedge0_\wedge..._\wedge0_\wedge0$$

$$n\,\, objects\,\,0$$ $$Choose\,\,r-1\,\,of\,\,the\,\,spaces\,\,_\wedge.$$

For instance if you have $n=8$ and $r=3$ and you choose the 2 divisors so as to obtain $$000|000|00$$ then the resulting vector is $x_1 = 3. x_2 = 3, x_3 = 2.$ As there are $n-1\choose r-1$ possible selections, you have the following proposition.

  • Proposition 1: There are $n-1\choose r-1$ distinct positive integer-valued vectors $(x_1, x_2,...,x_r)$ satisfying the equation $$x_1 + x_2 + ... + x_r = n, \,\,\, x_i > 0,\,\,\, i = 1,...,r$$

  • Finally, from Proposition 1 you can obtain the following proposition

  • Proposition 2: There are $n+r-1\choose r-1$ distinct non-negative integer-valued vectors $(x_1, x_2,...,x_r)$ satisfying the equation $$ x_1 + x_2 + ... + x_r = n$$

  • Question: I understand all the steps taken prior to Proposition 2, so what I want to know is how is Proposition 2 derived from Proposition 1? I have drawn multiple diagrams using the spaces between objects analogy by adding $r$ extra possible positions for a divider, but none of them hold for all possible vectors.

$\endgroup$
14
$\begingroup$

For concreteness, let us work with the specific numbers $8$ and $3$ mentioned in the post, though the argument is general.

We have $8$ identical candies, and we want to distribute them among $3$ kids, with some kid(s) possibly getting no candy. Call this Task A.

Task B goes as follows. Distribute $8+3$ candies among the kids, with each kid getting at least $1$ candy. Then take away a candy from each kid.

It is clear that there are just as many ways to carry out Task B as there are to carry out Task A. And by the analysis of Proposition 1, there are $\binom{8+3-1}{3-1}$ ways to carry out Task B.

Another way: Imagine $8+3-1$ slots in a row, like this: $$\square\quad\square\quad\square\quad\square\quad\square\quad\square\quad\square\quad\square\quad\square\quad\square$$ We will put place $8$ candies ("stars") in these slots, with the other $2$ slots serving as separators ("bars"), possibly adjacent. The number of ways of placing the candies is $\binom{8+3-1}{8}$. It is the same as the number of ways of choosing the $2$ slots to be left blank.

So the number of solutions is $\binom{10}{8}$, or equivalently $\binom{10}{2}$.

In general, the same analysis shows that the number of ways to distribute $n$ candies among $r$ kids is $\binom{n+r-1}{n}$, or equivalently $\binom{n+r-1}{r-1}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Nice answer - but so mean to the kids! :) $\endgroup$ – Chas Brown Sep 4 '14 at 19:52
  • $\begingroup$ @AndreNicolas I just can't seem to make the connection between Task A and Task B. Is there a way you can demonstrate it visually? $\endgroup$ – Kermit the Hermit Sep 4 '14 at 20:01
  • $\begingroup$ For every way of carrying out A, there is a way to carry out B, and vice-versa. In terms of formulas, the number of non-negative solutions of $x_1+x_2+x_3=8$ is the same as the number of positive solutions of $y_1+y_2+y_3=11$. The mapping is $(x_1,x_2,x_3)$ goes to $(y_1,y_2,y_3)$ where $y_i=x_i+1$. $\endgroup$ – André Nicolas Sep 4 '14 at 20:07
  • $\begingroup$ I will add a visual way of doing it that may be more meaningful to you. About $10$ minutes! $\endgroup$ – André Nicolas Sep 4 '14 at 20:15
  • $\begingroup$ That would be greatly appreciated, @AndréNicolas. $\endgroup$ – Kermit the Hermit Sep 4 '14 at 20:18
6
$\begingroup$

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ With $\ds{ 0 < a < 1}$: \begin{align} &\color{#66f}{\large\sum_{x_{1} = 0}^{n}\ldots\sum_{x_{r} = 0}^{n}\delta_{x_{1} + \cdots + x_{r},n}} =\sum_{x_{1} = 0}^{\infty}\ldots\sum_{x_{r} = 0}^{\infty} \delta_{x_{1} + \cdots + x_{r},n} \\[3mm]&=\sum_{x_{1} = 0}^{\infty}\ldots\sum_{x_{r} = 0}^{\infty} \oint_{\verts{z}\ =\ a}{1 \over z^{-x_{1}\ -\ \cdots\ -\ x_{r}\ +\ n\ +\ 1}} \,{\dd z \over 2\pi\ic} \\[3mm]&=\oint_{\verts{z}\ =\ a}{1 \over z^{n + 1}} \pars{\sum_{x = 0}^{\infty}z^{x}}^{r}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ a}{1 \over z^{n + 1}}\pars{1 \over 1 - z}^{r} \,{\dd z \over 2\pi\ic} \\[3mm]&=\oint_{\verts{z}\ =\ a}{1 \over z^{n + 1}} \sum_{k = 0}^{\infty}{-r \choose k}\pars{-1}^{k}z^{k}\,{\dd z \over 2\pi\ic} =\sum_{k = 0}^{\infty}{r + k - 1 \choose k} \oint_{\verts{z}\ =\ a}{1 \over z^{n - k + 1}}\,{\dd z \over 2\pi\ic} \\[3mm]&=\sum_{k = 0}^{\infty}{r + k - 1 \choose k}\delta_{kn} =\color{#66f}{\large{r + n - 1 \choose n}} \end{align}

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

An alternate explanation (based on the first part of the accepted answer):

Say there are 8 candies in a row and 3 kids. Each kid gets all the candies to its left, upto the previous kid (or upto the start, for the first kid).

For Proposition 1, the kids are only allowed to stand between the candies, so there are 8-1 possible positions for them to stand. For Proposition 2, the kids are also allowed to stand outside the row of candies - there are 3 possible positions outside the right edge of the row of candies that are now allowed positions to stand. Therefore, there are 8-1+3 positions to choose from, hence the number of ways of dividing the candies is now $\binom{8-1+3}{3-1}$.


I'll also add another way to derive the formula (though here, the actual formula was computed by Wolfram Alpha - this only derives a summation whose result is the formula in the question):

The difference between Proposition 1 and Proposition 2 is that, P1 allows only positive values for $x_i$, whereas P2 allows any non-negative value - i.e., for P2, some $x_i$ are allowed to be 0.

Let's say there are $k$ values in the vector $(x_1,x_2,...,x_r)$ that are 0. Then, only the remaining $(r-k)$ positive, non-zero values in the vector contribute to the sum. Therefore, the number of distinct vectors here reduces to the number of distinct vectors with $(r-k)$ positive (non-zero) values that sums up to n. From Proposition 1, we know that to be $n-1\choose r-k-1$. Therefore, the number of distinct vectors $(x_1,x_2,...,x_r)$ in which a given set of $k$ values are 0 is $n-1\choose r-k-1$.

Now, those $k$ zeros can be any of the $r$ values in the vector. Hence, there are $r\choose k$ ways of choosing the places where $x_i$ is zero. For each choice, there are $n-1\choose r-k-1$ distinct vectors. Therefore, the number of distinct vectors $(x_1,x_2,...,x_r)$ in which any $k$ values are 0 is $n-1\choose r-k-1$$r\choose k$.

$k$ can range from 0 (all non-zero positive values in vector) to $r-1$ (1 non-zero positive value, all other values 0 in the vector). So, the total number of distinct vectors $(x_1,x_2,...,x_r)$ with non-negative values is: $\large{\sum_{k=0}^{r-1} \binom{n-1}{r-k-1} \binom{r}{k}}$.
This summation, according to Wolfram|Alpha, evaluates to $(n+r-1)!\over n!(r-1)!$, which is the same as ${\large{n + r - 1 \choose r - 1}}$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Just let $y_i=x_i+1$, and $x_1+\cdots+x_r=n$ becomes $y_1+\cdots+y_r=n+r$, whose positive integer-valued solutions correspond to non-negative solutions to the previous one.

| cite | improve this answer | |
$\endgroup$
-2
$\begingroup$

Well, this particular problem can be solved by thinking in following way:

Step 1: First find the total number of solutions in which none of the variables from x1, x2, and x3 is zero.

Step 2: Then find the number of solutions in which only one from x1, x2, and x3 is zero.

Step 3: Then find the number of solutions in which only two from x1, x2, and x3 is zero.

Step 4: Finally, add all the number of solutions found in the abovementioned steps. This is the final answer.

This method can be generalized and we will arrive at the same formula.

PS: I don't have any idea how to write math equations here, and therefore my contribution may rightly look ugly to some of the contributors here.

| cite | improve this answer | |
$\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.