Determine the number of integer solutions to the inequality

Question

anonymous · Answer

What is the inequality?

anonymous · Answer

$$x _{1} + x _{2} + x _{3} + x _{4} + x _{5} <40$$

$$1. x _{i} \ge 0$$
$$2.x _{i} \ge -3$$
$$1\le i \le 5$$

parthkohli · Answer

Wow, this is a good question.

parthkohli · Answer

The number of nonnegative integral solutions to the equation:$$x_1+x_2 + \cdots + x_n = k$$is$$\binom{n+k-1}{k-1 }$$

parthkohli · Answer

The inequality is $x_1 + x_2 + x_3 + x_4 + x_5 < 40$ and not $x_1 + x_2 + \cdots + x_i$ where $1 \le i \le 5$ right?

anonymous · Answer

Yea!! 1< i <5 is the last subquestion

parthkohli · Answer

@oldrin.bataku just to party with a good question

parthkohli · Answer

$$N=\sum_{k=0}^{39}\binom{5+k-1}{k-1 }$$

parthkohli · Answer

The answer is an astonishing one: 7059052

anonymous · Answer

But shouldnt the answear be 44 choose 39?

parthkohli · Answer

It's great that you're following me. 

The answer is no. Note that we want to find the number of solutions to the inequality $\rm something < 40$ which boils down to adding the solutions of the equalities $\rm something = 1, 2, \cdots, 39$.

The combination expression gives the number of solutions to equalities, not inequalities. So yeah.

anonymous · Answer

Is the answear to xi>= -3    47 choose 38?

anonymous · Answer

Iam following I think, But I still couldnt explain it good to my frienda or teacher, I dont know how to write it down on my paper..

parthkohli · Answer

That is a lot more interesting. Where did you get that figure?

anonymous · Answer

I was just thinkin because it increases the intervall of combinationa with +3?

parthkohli · Answer

@oldrin.bataku plugging again

anonymous · Answer

But in the sum you did upthere, sorry fr not writing in latex im on my phone right now... but in the sum why is it (5+k-1) choose (k-1)?

parthkohli · Answer

$$n = 5$$Number of nonnegative solutions to$$x_1 + x_2 + \cdots +  x_n = k $$is$$\binom{n+k-1}{k-1}$$

parthkohli · Answer

do you understand why the above expression holds true?

anonymous · Answer

Not reqlly, the only thing our teacher did with this is some kind of cinnamon buns example with four students and 12 buns, x1+x2+x3+x4=12 and the k-1 just represents the walls of the students...

parthkohli · Answer

yay, she explained the stars-and-bars analogy to you.

zarkon · Answer

don't you want ...

n=5
Number of nonnegative solutions to
$$x_1+x_2+\cdots+x_n=k$$
is

$${n+k-1 \choose n-1}$$

instead of 

$${n+k-1 \choose k-1}$$

parthkohli · Answer

that's a grand mistake.

parthkohli · Answer

thanks for the catch.

anonymous · Answer

@zarkon could you explain?

anonymous · Answer

@Michele_Laino could you explain this a little further?

michele_laino · Answer

I'm very sorry, I'm not good with discrete mathematics

anonymous · Answer

$$\sum_{k=0}^{39}\left(\begin{matrix}n+k-1 \ n-1\end{matrix}\right)=1086008=\left(\begin{matrix}44 \ 39\end{matrix}\right)$$

anonymous · Answer

@Zarkon, @ParthKohli right? is
$$\left(\begin{matrix}n+k-1 \ n-1\end{matrix}\right)$$
a known equation for this type of problems?

anonymous · Answer

@Zarkon, @ParthKohli, if k starts from -3 it should be the same answear? cause the first $$\left(\begin{matrix}5+k-1 \ 5-1\end{matrix}\right)=\left(\begin{matrix}5-3-1 \ 5-1\end{matrix}\right)=0$$
$$\left(\begin{matrix}5-2-1 \ 5-1\end{matrix}\right)=0$$
$$\left(\begin{matrix}5-1-1 \ 5-1\end{matrix}\right)=0$$
and then it just starts over up to 39?

anonymous · Answer

@oldrin.bataku

anonymous · Answer

what is $$x_{i}$$ exactly? is it the number of times the first value is choosen? i.e the startvalue ?

zarkon · Answer

for (2)
let $$y_i=x_i+3\Rightarrow x_i=y_i-3$$
then $$x_1+x_2+x_3+x_4+x_5<40$$
becomes
 $$y_1-3+y_2-3+y_3-3+y_4-3+y_5-3<40$$

 $$y_1+y_2+y_3+y_4+y_5<40+15$$
 $$y_1+y_2+y_3+y_4+y_5<55$$

and the $$y_i\ge 0$$

anonymous · Answer

gj @Zarkon

zarkon · Answer

$x_i$ is the value of the $i$th number

anonymous · Answer

Why do we let $$y _{i}=x _{i}+3$$

anonymous · Answer

@Zarkon

anonymous · Answer

@pate16  because it transforms the problem from $x_i\ge-3$ into the standard stars-and-bars form in which $x_i\ge0$

anonymous · Answer

er, the second should be $y_i\ge0$

anonymous · Answer

ah, $$1\le i \le 5$$I see, hint for the last one?

anonymous · Answer

oops, can you give me a hint for the last one I mean

anonymous · Answer

basically, consider the problem where we partition the $55$ into 5 nonnegative integers $y_1,\dots,y_5$. if we afterward throw away 3 from each 'bin' (subtract 3 from each of those integer parts, so $x_i=y_i-3$) then they add up now to $50-5\cdot3=40$ and each bin is an integer greater than or equal to -3, $x_i\ge-3$

anonymous · Answer

so counting the nonnegative partitions of $40+5\cdot3=55$ is equivalent to countign the integer partitions of $40$ with the requirement that each is greater than or equal to $-3$ rather than merely nonnegative

anonymous · Answer

this is a generalization of the method we use when taking stars and bars from positive integers to nonnegative integers. the original method of stars and bars involves n indistinguishable items (stars) that we want to distribute amongst k distinct bins such that no bin is nonnegative (i.e. number of *positive* solutions to $\sum_{1\le i\le k} x_i=n$).

suppose we have 10 stars:

* * * * * * * * * *

now, if we had, say, 4 bins, then we want to find the number of ways to place 4-1 = 3 dividers amongst the 10-1 = 9 spaces between stars:

*  *  *  *  *  *  *  *  *  *
 ^  ^  ^ ^  ^ ^  ^  ^ ^

there are clearly $\binom{9}3$ such ways to place the three dividers so that we get 4 bins of distinct size. in general, for n stars and k bins, the above reasoning gives $\binom{n-1}{k-1}$ possible partitions, or positive integer solutions to $\sum_{1\le i\le k}x_i=n$.

to generalize this to *nonnegative* partitions, i.e. cases where we could have empty bins, suppose we instead add $k$ new stars and then find the positive integer partitions of these total $n+k$ stars amongst $k$ bins, and then remove one star from each bin. this sets up a bijection between the partitions of $n+k$ indistinguishable stars amongst $k$ distinct nonempty bins and partitions of of $n$ indistinguishable stars amongst $k$ distinct *possibly empty* bins, so it follows that the expression here gives $\binom{n+k-1}{k-1}$. in terms of solutions to $\sum_{1\le i\le k}x_k=n$ we have that the solutions to $\sum_{1\le i\le k}x_k=n$ with $x_k\ge0$ is equivalent to the problem of $\sum_{1\le i\le k}y_k=n+k$  with $y_k\ge1$, since we can simply subtract 1 from each of the $y_i$ to give: $$\sum_{1\le i\le k}y_k=n+k\\implies \sum_{1\le i\le k}(y_k-1)=n+k-k\\implies \sum_{1\le i\le k}(y_k-1)=n$$ or add 1 to each of the $x_k$ in the corresponding problem so that every solution of one corresponds to a unique solution of the other

in a similar way, we can extend the above reasoning to bins that contain 'negative' numbers of stars simply by *adding* or *subtracting* more than 1 item per bin

anonymous · Answer

here: $$\sum_{1\le i\le k}x_k=n,\quad x_k\ge -3$$
consider if we add $3$ to each solution, we get:

$$\sum_{1\le i\le k}(x_k+3)=n+3k$$now these $x_k+3$ correspond to a perfectly good solution $y_k$ to the complementary problem $\sum_{1\le i\le k}y_k=n+3k,\ y_k\ge 0$. so counting the solutions to the first problem is the 'same' combinatorially to counting solutions to the bottom problem, and we just showed in the previous post that the second problem is just $\binom{n+3k-1}{k-1}$

anonymous · Answer

oops I meant $x_i,y_i$ for $1\le i\le k$ in the summations of the previous problems, not specifically $x_k,y_k$

anonymous · Answer

now, the trick in this problem to *not* have to add all the solutions from $1$ to $40$ has multiple interpretations; in one, you're using the fact that these binomial coefficients (really encoding *multiset* numbers) satisfy a recurrence relation which lets us condense the big ugly sum. in another interpretation, we're introducing a 'slack' variable $x_6$ to quantify the difference between $x_1+\dots+x_5$ and $40$, and requiring $x_k>0$. observe:

$$x_1+x_2+x_3+x_4+x_5+x_6=40\x_1,x_2,x_3,x_4,x_5\ge0\x_6>0$$

now, we'd really like to have all of our variables satisfy the same constraint to reduce it to the easy stars-and-bars problem we had before; consider that if we deal with $x_6'=x_6-1\ge0$ instead, and then add a star for $x_6$ specifically, we get consistent requirements on all of variables so $x_1,\dots,x_5,x_6'\ge 0$ transforming our problem into: $$x_1+x_2+x_3+x_4+x_5+x_6'+1=40\\implies x_1+x_2+x_3+x_4+x_5+x_6'=39$$

now, how many nonnegative partitions of $39$ into $6$ bins are there? simple! $$\binom{39+6-1}6=\binom{44}6= 7059052 $$ @parthkoli

anonymous · Answer

and this is the same concept of a 'slack' variable that comes up in optimization when transforming inequality constraints into equations, such as in linear programming problems: https://en.wikipedia.org/wiki/Slack_variable

anonymous · Answer

now, let's tackle the next one. we have: $$x_1+x_2+x_3+x_4+x_5<40,\quad x_i\ge -3$$
if we instead look at waht this problem spells for $y_i=x_i+3$ we see: $$y_1+y_2+y_3+y_4+y_5<40+3\cdot5=55,\quad y_i\ge 0$$now, we introduce another slack variable, here $y_i$, to compensate for the difference of $y_1+\dots+y_5$ and $55$: $$y_1+y_2+y_3+y_4+y_5+y_6=55,\quad y_1,y_2,y_3,y_4,y_5\ge 0,\quad y_6>0$$just as before, we can 'set aside' one star for $y_6$ to guarantee it stays positive and is never zero by looking instead at $y_6'=y_6-1$ and requiring $y_6'\ge 0$ so $$y_1+y_2+y_3+y_4+y_5+y_6'+1=55,\quad y_1,\dots,y_5,y_6'\ge 0\\implies y_1+y_2+y_3+y_4+y_5+y_6'=54$$ and this is just an easy standard stars-and-bars problem like before, so the answer is $$\binom{54+6-1}{6-1}=\binom{59}5=5006386$$

anonymous · Answer

in the first problem i meant to write $6-1$ in the binomial coefficient, so it's actually $$\binom{39+6-1}{6-1}=\binom{44}5= 1086008 $$

anonymous · Answer

How can I get the same answear as you but I dont use the slack variable?

anonymous · Answer

Im just summing them up in mathematica$$\sum_{k=0}^{54}\left(\begin{matrix}5+k-1 \ 5-1\end{matrix}\right)=\left(\begin{matrix}5+0-1 \ 5-1\end{matrix}\right)+\left(\begin{matrix}5+1-1 \ 5-1\end{matrix}\right)+...+\left(\begin{matrix}5+53-1 \ 4\end{matrix}\right)$$

anonymous · Answer

and the same for the first one to, but up to 39?

anonymous · Answer

so for standard stars-and-bars with nonempty bins, i.e. solutions to the equation $x_1+\dots+x_k=n,\ x_k>0$ the expression is: $$\binom{n-1}{k-1}$$
if we instead allow empty bins, i.e. $x_1+\dots+x_k=n,\ x_k\ge 0$ we basically add one star for each bin (so $y_i=x_i+1, n\to n+k$) and then use the previous expression for nonempty solutions to solve $y_1+\dots+y_k=n+k,\ y_k>0$, and then remove one from each bin afterward to give us a solution: $$\binom{n+k-1}{k-1}$$
more generally, if we have $x_1+\dots+x_k=n,\ x_k\ge c$ then we can use an analogous trick to the previous case (nonnegative) by instead looking at solutions to the problem with $y_i=x_k-c$ where $y_1+\dots+y_k=n-ck,\ y_k\ge 0$, which are counted using the expression above: $$\binom{n-ck+k-1}{k-1}=\binom{n+(1-c)k-1}{k-1}$$note the $(1-c)k$ reflects the fact that we can go straight to the first stars-and-bars case with nonnegative $x_k$ immediately by using $z_k=x_k-c+1$ so that $$z_1+\dots+z_k=n-ck+k=n+(1-c)k,\quad x_k>0$$ which is then given by the solution for *positive* (nonempty) $z_k$, so: $$\binom{n+(1-c)k-1}{r-1}$$

anonymous · Answer

I gotta go right now, but ill be back later so just finish what you are writing! thanks so much!

anonymous · Answer

@pate16 because of the recurrence relation between these binomial coefficients, also known as Pascal's identity ;-)
$$\binom{n}k=\binom{n-1}{k-1}+\binom{n-1}k$$

one interpretation of the sum you have is that you're counting the cases where the slack is $40-0=40$ so the solutions $x_1+\dots+x_5=0$, then $40-1=39$ so solutions to $x_1+\dots+x_5=1$, ..., then $40-k$ so solutions to $x_1+\dots+x_5=k$, ..., and finally where the slack is $40-39=1$ so $x_1+\dots+x_5=39$. the sum total of these solutions for the possible slack values of $1$ to $40$ is written: $$\sum_{k=0}^{39}\binom{k+5-1}{5-1}$$

alternatively, we can count all the possible solutions to $x_1+\dots+x_5+\underbrace{x_6}_{\text{slack}}=40$ for $x_1,\dots,x_5\ge 0$ and a positive slack $x_6>0$ (to ensure the inequality is strict and we don't include $x_1+\dots+x_5=40$, only up to $39$) all at once, which is what i did--and these are equivalent, which is what Pascal's identity does for us here

anonymous · Answer

that sum simplifies very cleanly by Pascal's identity, if you look: $$\binom44+\binom54+\binom64+\dots+\binom{43}4=\binom{44}5$$

anonymous · Answer

@oldrin.bataku thanks so much! that is great!!!!