Results 1 to 4 of 4

Math Help - combinatorics question -- please help

  1. #1
    Newbie
    Joined
    Dec 2008
    Posts
    5

    combinatorics question -- please help

    how many whole integral solutions does the equation

    have if
    and c and k are constants.

    This problem is analogous to the to this if a number of people have each some amount of money(may or may not be the same amount) , in how many ways can they pay a bill.

    I cannot understand how to do this question please help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Combinatorics

    Hello druvid fae
    Quote Originally Posted by druvid fae View Post
    how many whole integral solutions does the equation

    have if
    and c and k are constants.

    This problem is analogous to the to this if a number of people have each some amount of money(may or may not be the same amount) , in how many ways can they pay a bill.

    I cannot understand how to do this question please help.
    This is certainly a complex question, isn't it? So far, I think I've been able to come up with solutions for n=1, 2,3, and a suggestion for a general solution. I haven't any more time at present to complete the problem, but maybe you can do so.

    Consider the case n=1. Clearly there is no solution unless k_1 \ge c + 1, since x_1<k_1, and one solutions otherwise.

    Now consider n=2.

    Since x_1>0 and x_2>0, if c =1, there is no solution; and there is no solution if k_1+k_2 < c+2, since in that case x_1+x_1< c.

    But if c>1 and k_1+k_2 \ge c+2, there will be at least one solution. In fact, provided k_1 \ge c and k_2 \ge c, there will be c-1 possible solutions from x_1 =1, x_2 =c-1 to x_1=c-1, x_2 = 1.

    Moreover, for each integer by which either k_1 or k_2 is less than c, the number of solutions is reduced from c-1 by 1.

    Thus, the number of solutions for n = 2 is:

    max(max(c-1,0)-max(c-k_1,0)-max(c-k_2,0),0), where max(a,b) is the greater of the two integers a and b.

    Now consider n = 3.

    If c\ge 3 and k_i \ge (c-1) for all i, then the number of solutions is at a maximum, since the x_i may then have any values in the required range, 1 \le x_i \le (c-2). This maximum is \frac{1}{2}(c-1)(c-2), which we may prove as follows:

    Suppose x_1 has the value c-i. Then x_2+x_3 =i, and there are then (i-1) possible pairs of values of x_2 and x_3. Now since 1 \le x_1 \le c-2, i takes values from 2 to c-1. Thus the total number of solutions is:

    1 + 2 + \dots + c-2 which is an AP with sum \frac{1}{2}(c-1)(c-2)

    (Incidentally, this is clearly _{c-1}C^2, the number of ways of selecting 2 items from c-1, but at present I can't see why this should be so! Perhaps you can?)

    So, taking the same line as when n = 2, I think the solution to n = 3 is:

    max(max(\frac{1}{2}(c-1)(c-2),0)-max(c-1-k_1,0)-max(c-1-k_2,0) -max(c-1-k_3,0),0) which we may write using sigma notation as:

    max(max(\frac{1}{2}(c-1)(c-2),0) - \sum_{i=1}^3max(c-1-k_i,0),0)

    For the general case, n
    , for the maximum number of solutions k_i \ge c-n+2 and c \ge n; and, again, for every integer value below c-n+2 that a k_i falls, the number of solutions will be reduced by 1 (I think!). How do you get the maximum number of solutions? Is it _{c-1}C^{n-1}? I don't know. Perhaps you can take it a bit further, but I must sign off for the present.

    Grandad

    PS I've now worked out the maximum number of solutions for n=4, and indeed it is \frac{1}{6}(c-1)(c-2)(c-3) = _{c-1}C^3, suggesting even more strongly that my guess for the general case is correct. But I still can't see why this should be so.

    The other thing to note is that in working out the solution for n = 4, I used the solution for n=3 as follows:

    If x_1 = c-i, then x_2+x_3+x_4 = i, and the number of ways in which this can occur is the same as the problem for n = 3, with c being replaced by i. Could a recursive method like this be applied to the general case, or is there a more direct way?
    Last edited by Grandad; January 8th 2009 at 09:00 AM. Reason: Added PS
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2008
    Posts
    5
    thank you, your explanation is far more lucid than my books' inadequate lone example.Before I start , I would like to apologize for replying so late,I do not regularly check my mail,and am even more inconsistent in checking my forum posts.

    Your answer is correct.the number of non negative integral solutions is
    ^{c+m - 1}C _{m-1} and for positive integral solutions ^{c - 1}C _{m-1}(m-1 choose c-1).
    My book approaches this problem as an example of the multinomial theorem.
    It gives the following example to explain
    ""
    Q.In how many different ways can 3 people A,B, and C having 6, 7, and 8 dollars each donate 10 dollars collectively.

    ans: The number of ways in which they can denote $10 is the same as the number of solutions to the equation  x_1 + x_2 + x_3 = 10
    subject to the condition that  0 \le x_1 \le 6 ,0 \le x_2 \le 7,0 \le x_3 \le 8.
    Hence the required number of ways is the coefficient of x^10 in (1+ x + x^2 + ..... + x^6)((1+ x + x^2 + ..... + x^7)(1+ x + x^2 + ..... + x^8)
    = coef of x^10 in  (1- x^7)(1- x^8)(1- x^9)(1 - x)^-3
    = coef of x^10 in  (1- x^7- x^8 - x^9)( 1 + ^3 C_1 x +  ^4 C_2 x^2 +  ^5 C_3 x^3 + ..... +  ^12 C_10 x^10) ignoring terms higher than 10
    = ^12 C_2 - ^5 C_3 - ^4 C_2 - ^3 C_1
    ""
    it is how the multinomial changed to the binomial factors which really confuses me.(if you can see how pleases tell me).

    thank you once again.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Multinomial to Binomial

    Hello druvid fae
    Quote Originally Posted by druvid fae View Post
    Hence the required number of ways is the coefficient of x^10 in (1+ x + x^2 + ..... + x^6)((1+ x + x^2 + ..... + x^7)(1+ x + x^2 + ..... + x^8)
    = coef of x^10 in  (1- x^7)(1- x^8)(1- x^9)(1 - x)^-3
    = coef of x^10 in  (1- x^7- x^8 - x^9)( 1 + ^3 C_1 x +  ^4 C_2 x^2 +  ^5 C_3 x^3 + ..... +  ^12 C_10 x^10) ignoring terms higher than 10
    = ^12 C_2 - ^5 C_3 - ^4 C_2 - ^3 C_1
    ""
    it is how the multinomial changed to the binomial factors which really confuses me.(if you can see how pleases tell me).

    thank you once again.
    All you need is to say that 1+ x + x^2 + ..... + x^6 is a GP with a = 1, r = x and n = 7. So

    S_6 = \frac{1 - r^n}{1-r} = \frac{1 - x^7}{1-x}

    Similarly with the other two multinomial terms.

    Or, you could note that 1 - x^n = 0 when x = 1, so (1-x) is always a factor of (1 - x^n), and use algebraic long division to confirm that

    \frac{1 - x^n}{1-x} = 1+ x + x^2 + ..... + x^7

    OK?

    Grandad
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorics question
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 29th 2011, 06:35 AM
  2. Combinatorics Question
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: May 2nd 2011, 04:30 AM
  3. Combinatorics question
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 24th 2011, 10:19 AM
  4. Combinatorics question
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 24th 2011, 06:47 AM
  5. Combinatorics Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 10th 2008, 11:21 AM

Search Tags


/mathhelpforum @mathhelpforum