Javascript required
Skip to content Skip to sidebar Skip to footer

Find the Number of Nonnegative Integer Solutions

You are using an out of date browser. It may not display this or other websites correctly.
You should upgrade or use an alternative browser.
  • Forums
  • Homework Help
  • Precalculus Mathematics Homework Help

Number of non negative integer solutions to this inequality

  • Thread starter Woolyabyss
  • Start date

Homework Statement


How many non-negative integer solutions are there to the equation
x1 + x2 + x3 + x4 + x5 < 11,
(i)if there are no restrictions?
(ii)How many solutions are there if x1 > 3?
(iii)How many solutions are there if each xi < 3?

Homework Equations


N/A

The Attempt at a Solution


(i) inequality equivalent to equality x1 + x2 + x3 + x4 + x5 + x6 = 10
(n+k-1)choose(k-1) = (10+6-1)choose(6-1) = 3003

(ii) if x1 > 3 ------------> x2 + x3 + x4 + x5 < 8
equality equivalent x2 + x3 + x4 + x5 +x6 = 7
again (7+5-1)choose(4) = 330

(iii)
Its this part I'm not certain about

like in (ii) let x1 instead be > 3 we find 7+5-1)choose(4) = 330

now let x1 and x2 be > 3
we find x3 + x4 + x5 < 5
----> x3 + x4 + x5 +x6 = 4
(4+4-1)choose(4-1) =35

finally let x1,x2 and x3 >3
then x4 +x5 <2
equality x4 + x5 + x6 =1
(1+3-1)choose(2) = 3

answer: 3003 - 35 - 330 - 3 = 2635

any help would be appreciated.

Answers and Replies

You made a small error in (ii). If x1>3 then x1>=?
(iii) is actually the easiest of the questions. If every term is under 3, and there are only 5 terms....
You made a small error in (ii). If x1>3 then x1>=?
(iii) is actually the easiest of the questions. If every term is under 3, and there are only 5 terms....

is this correct?
(ii)
If x1>3 then x1 >= 4
if x1 >= 4 ------------> x2 + x3 + x4 + x5 < 7
equality equivalent x2 + x3 + x4 + x5 + x6 = 6
(6+5-1)choose(5-1)
(iii) since xi < 3
each term can be 0,1 or 2
so 3^5
is this correct?
(ii)
If x1>3 then x1 >= 4
if x1 >= 4 ------------> x2 + x3 + x4 + x5 < 7
equality equivalent x2 + x3 + x4 + x5 + x6 = 6
(6+5-1)choose(5-1)
(iii) since xi < 3
each term can be 0,1 or 2
so 3^5
Looks right to me.

Homework Statement


How many non-negative integer solutions are there to the equation
x1 + x2 + x3 + x4 + x5 < 11,
(i)if there are no restrictions?
(ii)How many solutions are there if x1 > 3?
(iii)How many solutions are there if each xi < 3?

Homework Equations


N/A

The Attempt at a Solution


(i) inequality equivalent to equality x1 + x2 + x3 + x4 + x5 + x6 = 10
(n+k-1)choose(k-1) = (10+6-1)choose(6-1) = 3003

(ii) if x1 > 3 ------------> x2 + x3 + x4 + x5 < 8
equality equivalent x2 + x3 + x4 + x5 +x6 = 7
again (7+5-1)choose(4) = 330

(iii)
Its this part I'm not certain about

like in (ii) let x1 instead be > 3 we find 7+5-1)choose(4) = 330

now let x1 and x2 be > 3
we find x3 + x4 + x5 < 5
----> x3 + x4 + x5 +x6 = 4
(4+4-1)choose(4-1) =35

finally let x1,x2 and x3 >3
then x4 +x5 <2
equality x4 + x5 + x6 =1
(1+3-1)choose(2) = 3

answer: 3003 - 35 - 330 - 3 = 2635

any help would be appreciated.


You have part (i) wrong: the totality of non-negative integer solutions to ##x_1+x_2+x_3+x_4+x_5 < 11## is all the solutions to ##\sum x_i = 0## plus all the solutions to ##\sum x_i = 1##, plus ... plus all the solutions to ##\sum x_i = 9## plus all the solutions to ##\sum x_i = 10##. These all have sums < 11, as requested.

The solutions to other parts will be similarly affected.

You have part (i) wrong: the totality of non-negative integer solutions to ##x_1+x_2+x_3+x_4+x_5 < 11## is all the solutions to ##\sum x_i = 0## plus all the solutions to ##\sum x_i = 1##, plus ... plus all the solutions to ##\sum x_i = 9## plus all the solutions to ##\sum x_i = 10##.
Did the trick of introducing a sixth unknown to take up the slack not resolve that?
Did the trick of introducing a sixth unknown to take up the slack not resolve that?

Yes, it does, but I missed that!

Related Threads on Number of non negative integer solutions to this inequality

  • Last Post
  • Last Post
Ray Vickson
  • Last Post
  • Last Post
Ray Vickson
  • Last Post
  • Last Post
  • Last Post
Leo Consoli
  • Last Post
  • Last Post
mfb
  • Last Post
Mark44
  • Forums
  • Homework Help
  • Precalculus Mathematics Homework Help

Find the Number of Nonnegative Integer Solutions

Source: https://www.physicsforums.com/threads/number-of-non-negative-integer-solutions-to-this-inequality.845997/