0

I was looking around questions and I found one that intrigued me, and I need help explaining it.

Here is the question with the answers, Discrete math and integer solutions problem

Can someone explain to me how to find the number of non-negative integer solutions for the inequality:

$x_1+x_2+\dots+x_6 < 10$?

I know this question was posted already and answered, but I was unable to comprehend the answer given for that question.

I'm stuck at the part $x_1+x_2+⋯+x_7=9$, can someone explain to me why we add an extra "holder", or $x_7$ to the equation?

Ray
  • 73

3 Answers3

2

Finding the number of solutions to $x_1+x_2+...+x_6<10$ is equivalent to finding the number of solutions to $x_1+x_2+...+x_6=9$, the number of solutions to $x_1+x_2+...+x_6=8$, the number of solutions to $x_1+x_2+...+x_6=7$ etc. down to $x_1+x_2+...+x_6=0$.

In each of these cases we're just finding number of solutions to $x_1+x_2+...+x_6=n$ for $n=9,n=8,...,n=0$. It would be equivalent to look at $n$ as $n=9-k$ so that we're finding solutions to $x_1+x_2+...+x_6=9-k$ for $k=0,k=1,...,k=9$. Note that

$$x_1+x_2+...+x_6=9-k\implies x_1+x_2+...+x_6+k=9$$

We could just as easily call $k$ by another name. So let's call it $x_7$ for the sake of being consistent on the left hand side of the equation. So now we need to solve for the number of solutions to $x_1+x_2+...+x_6+x_7=9$ for $x_7=0,x_7=1,...,x_7=9$.

But then note that if we just find all of the solutions to $x_1+x_2+...+x_6+x_7=9$ then it will include the solutions of all of these individual cases where $x_7=0,1,2,...,9$ already, so in fact finding the number of solutions to $x_1+x_2+...+x_6+x_7=9$ is the same problem!

Thus the number of solutions to $x_1+x_2+...+x_6<10$ is the same as the number of solutions to $x_1+x_2+...+x_6+x_7=9$, which we know to be

$${{9+7-1}\choose{7-1}}=5005$$

  • What do you mean it being equivalent to finding the number of solutions when it equal 9 , 8 , 7 ect ect. – Ray May 25 '14 at 22:33
  • How do you explain the transition between moving the 9-k sot hat k is on LHS..? Please ignore first comment. – Ray May 25 '14 at 22:40
  • If $x_1+x_2+...+x_6\lt 10$ and all of the $x$'s are non-negative integers, then $x_1+...+x_6$ must be be equal to $9,8,7,6,5,4,3,2,1$ or $0$. The number of ways that $x_1+...+x_6$ can be less than $10$ must then be the number of ways that it can be equal to $9$, plus the number of ways that it can be equal to $8$, plus the number of ways it can be equal to $7$, and so on down to the number of ways that it can be equal to $0$. – Arthur Skirvin May 25 '14 at 22:40
  • Sorry about the first question >.<, can you explain how you moved the k from 9-k to the LHS making it + k? – Ray May 25 '14 at 22:41
  • @Ray If you add $k$ to both sides of $x_1+...+x_6=9-k$ you end up with $x_1+...+x_6+k=9$. Adding the same element to both sides of an equation preserves the equality AND the number of solutions to the equality. So the number of solutions to $x_1+...+x_6=9-k$ is the same as the number of solutions to $x_1+...+x_6+k=9$. – Arthur Skirvin May 25 '14 at 22:47
1

$\newcommand{\+}{^{\dagger}} \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{\down}{\downarrow} \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{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \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{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert} \newcommand{\wt}[1]{\widetilde{#1}}$ With $\ds{N \in {\mathbb N}}$: \begin{align} &\color{#c00000}{\sum_{x_{1} = 0}^{\infty}\ldots\sum_{x_{6} = 0}^{\infty} \delta_{x_{1} + \cdots + x_{6},N}} =\sum_{x_{1} = 0}^{\infty}\ldots\sum_{x_{6} = 0}^{\infty}\oint_{\verts{z}\ =\ 1} {1 \over z^{-x_{1} - \cdots - x_{6} + N + 1}}\,{\dd z \over 2\pi\ic} \\[3mm]&=\oint_{\verts{z}\ =\ 1}{1 \over z^{N + 1}} \pars{\sum_{x = 0}^{\infty}z^{x}}^{6}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ 1}{1 \over z^{N + 1}} {1 \over \pars{1 - z}^{6}}\,{\dd z \over 2\pi\ic} \\[3mm]&=\oint_{\verts{z}\ =\ 1}{1 \over z^{N + 1}} \sum_{n = 0}^{\infty}{-6 \choose n}\pars{-1}^{n}z^{n}\,{\dd z \over 2\pi\ic} =\sum_{n = 0}^{\infty}{-6 \choose n}\pars{-1}^{n}\ \overbrace{\oint_{\verts{z}\ =\ 1}{z^{n} \over z^{N + 1}} \,{\dd z \over 2\pi\ic}}^{\ds{=\ \delta_{nN}}} \\[3mm]&=\pars{-1}^{N}{-6 \choose N} = \pars{-1}^{N}\bracks{\pars{-1}^{N}{-\bracks{-6} + N - 1 \choose N}} =\color{#c00000}{{N + 5 \choose 5}} \end{align}

\begin{align} &\color{#c00000}{\sum_{N = 0}^{9}{N + 5 \choose 5}} =\sum_{N = 0}^{9}\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{N + 5} \over z^{6}} \,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ 1}{1 \over z^{6}}\sum_{N = 0}^{9}\pars{1 + z}^{N + 5} \,{\dd z \over 2\pi\ic} \\[3mm]&=\oint_{\verts{z}\ =\ 1}{1 \over z^{6}}\, {\pars{1 + z}^{5}\bracks{\pars{1 + z}^{10} - 1} \over \pars{1 + z} - 1} \,{\dd z \over 2\pi\ic} \\[3mm]&=\overbrace{\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{15} \over z^{7}}\,{\dd z \over 2\pi\ic}}^{\ds{=\ {15 \choose 6}}}\ -\ \overbrace{\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{5} \over z^{7}}\,{\dd z \over 2\pi\ic}}^{\ds{=\ 0}}\ =\ {15 \choose 6} = \color{#00f}{\large 5005} \end{align}

Felix Marin
  • 89,464
  • Woah. I wish I could favorite answers. – Arthur Skirvin May 25 '14 at 22:55
  • @ArthurSkirvin I like solution like this because we don't have 'to count' but just follow the algorithm. However, I agree that a solution like the one you did it is very nice because it is more intuitive. Thanks. – Felix Marin May 25 '14 at 22:59
0

Since you want to count all the possible disjoint cases of $x_1+x_2+...+x_6 = k$ where $0\leq k\leq 9$ where $x_i\geq 0$ so lets think of $x_7 = 9-k$ then obviously $x_7 \geq 0$ and we have $x_1+x_2+...+x_6 + x_7 = 9$

so by adding $x_7$ we acctually decide how far from the inequality we want to go, and by that we pass on summing disjoint cases (It's acctually a bijection from the original solutions to the new solution, where old solution is mapped to the same solution with $x_7 = 9-\sum x_i$) .

Snufsan
  • 2,125