Results 1 to 7 of 7

Math Help - Find the number of integral solutions

  1. #1
    Member
    Joined
    Sep 2011
    Posts
    114

    Find the number of integral solutions

    Find the number of integral solutions of x1 + x2 + x3 + x4 = 28


    where each xi ≥ 1, and in addition each xi ≤ 8. Write your answer in terms of binomial coefficients.
    I am a little confused by this question.

    My solution would be to take the number of solutions where xi ≥ 1. Then I would subtract from that the total number of solutions where xi ≥9. This would leave the number of solutions where xi ≥ 1, and in addition each xi ≤ 8.

    But when I try to find solutions where xi ≥9 I realized this is not possible.

    Could someone give me a nudge in the right direction (without giving the answer).

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1

    Re: Find the number of integral solutions

    Find the number of integral solutions of
    x1 + x2 + x3 + x4 = 28
    where each xi ≥ 1, and in addition each xi ≤ 8. Write your answer in terms of binomial coefficients.
    This is a nightmare of a question if one does by cases.
    It is easy if you use generating functions.
    Expand \left( {\sum\limits_{k = 1}^8 {x^k } } \right)^4 the answer to this question is the coefficient to the x^{28} term.

    Luckily the is an online resource to do just that.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2011
    Posts
    114

    Re: Find the number of integral solutions

    Ya but this could show up on the exam so I really want to be able to understand and solve it.

    I am not quite sure what generating functions are, and I know they were not covered in class, so there must be another way to solve it that I could understand :P.

    It says put your answer in terms of binomial coefficients, so i am sure that it is expected it solved this way.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1

    Re: Find the number of integral solutions

    Quote Originally Posted by ehpoc View Post
    Ya but this could show up on the exam so I really want to be able to understand and solve it. It says put your answer in terms of binomial coefficients, so i am sure that it is expected it solved this way.
    Well ok. But don't ask me to explain.
    I will tell you that it comes from extended applications of inclusion/exclusion.

    \sum\limits_{k = 0}^3 {( - 1)^k \binom{27-8\cdot k}{3}\binom{4}{k}}=35 .
    Last edited by Plato; December 3rd 2011 at 01:42 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Sep 2011
    Posts
    114

    Re: Find the number of integral solutions

    I think I solved it!

    U=(27C3)
    A=(19C3) =total ways with only x1>8
    B=(19C3) =total ways with only x2>8
    C=(19C3) =total ways with only x3>8
    D=(19C3) =total ways with only x4>8
    AB=(11C3)
    AC=(11C3)
    AD=(11C3)
    BC=(11C3)
    BD=(11C3)
    CD=(11C3)
    ABC=(3C3)
    ABD=(3C3)
    ACD=(3C3)
    BCD=(3C3)

    |ABCD|=|U|-|A|-|B| -|C|-|D|+|AB|+|AC|+|BC|+|AD|+|BC|+|BD|-|ABC|-|ABD|-|ACD|-|BCD|

    =(27C3)-4(19C3)+6(11C3)-4=35
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1

    Re: Find the number of integral solutions

    Quote Originally Posted by ehpoc View Post
    I think I solved it!

    U=(27C3)
    A=(19C3) =total ways with only x1>8
    B=(19C3) =total ways with only x2>8
    C=(19C3) =total ways with only x3>8
    D=(19C3) =total ways with only x4>8
    AB=(11C3)
    AC=(11C3)
    AD=(11C3)
    BC=(11C3)
    BD=(11C3)
    CD=(11C3)
    ABC=(3C3)
    ABD=(3C3)
    ACD=(3C3)
    BCD=(3C3)

    |ABCD|=|U|-|A|-|B| -|C|-|D|+|AB|+|AC|+|BC|+|AD|+|BC|+|BD|-|ABC|-|ABD|-|ACD|-|BCD|

    =(27C3)-4(19C3)+6(11C3)-4=35
    That is great!
    I hope you learned something.
    You really do need to study generating functions.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Sep 2011
    Posts
    114

    Re: Find the number of integral solutions

    You really do need to study generating functions.
    As soon as I have an exam that requires me to know it
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. how to find number of solutions of (1/x)+(1/y)=(1/n!)
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 27th 2011, 07:51 PM
  2. Find the number of integer solutions
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 24th 2011, 05:52 PM
  3. find number of solutions of x
    Posted in the Calculus Forum
    Replies: 1
    Last Post: July 8th 2010, 12:13 PM
  4. Finding the number of integral solutions..
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 17th 2009, 02:49 AM
  5. Find all real-number solutions...
    Posted in the Algebra Forum
    Replies: 1
    Last Post: April 23rd 2008, 05:35 AM

Search Tags


/mathhelpforum @mathhelpforum