## anonymous one year ago Determine the number of integer solutions to the inequality

1. anonymous

What is the inequality?

2. anonymous

$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$

3. ParthKohli

Wow, this is a good question.

4. ParthKohli

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

5. ParthKohli

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?

6. anonymous

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

7. ParthKohli

@oldrin.bataku just to party with a good question

8. ParthKohli

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

9. ParthKohli

The answer is an astonishing one: 7059052

10. anonymous

But shouldnt the answear be 44 choose 39?

11. ParthKohli

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.

12. anonymous

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

13. anonymous

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..

14. ParthKohli

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

15. anonymous

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

16. ParthKohli

@oldrin.bataku plugging again

17. anonymous

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)?

18. ParthKohli

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

19. ParthKohli

do you understand why the above expression holds true?

20. anonymous

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...

21. ParthKohli

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

22. Zarkon

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}$

23. ParthKohli

that's a grand mistake.

24. ParthKohli

thanks for the catch.

25. anonymous

@zarkon could you explain?

26. anonymous

@Michele_Laino could you explain this a little further?

27. Michele_Laino

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

28. anonymous

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

29. anonymous

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

30. anonymous

@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?

31. anonymous

@oldrin.bataku

32. anonymous

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

33. Zarkon

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$

34. anonymous

gj @Zarkon

35. Zarkon

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

36. anonymous

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

37. anonymous

@Zarkon

38. anonymous

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

39. anonymous

er, the second should be $$y_i\ge0$$

40. anonymous

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

41. anonymous

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

42. anonymous

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$$

43. anonymous

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

44. anonymous

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

45. anonymous

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}$$

46. anonymous

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$$

47. anonymous

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

48. anonymous

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

49. anonymous

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$$

50. anonymous

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$$

51. anonymous

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

52. anonymous

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)$

53. anonymous

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

54. anonymous

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}$$

55. anonymous

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

56. anonymous

@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

57. anonymous

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

58. anonymous

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