combinatorics question -- please help

Printable View

January 7th 2009, 01:13 AM
druvid fae

combinatorics question -- please help

how many whole integral solutions does the equation
http://scienceforums.net/forum/latex...7edfde8a-1.gif
have if http://scienceforums.net/forum/latex...c0983268-1.gif
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.
January 8th 2009, 12:43 AM
Grandad

Combinatorics

Hello druvid fae

Quote:

Originally Posted by druvid fae

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?
January 30th 2009, 10:45 PM
druvid fae

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.
January 30th 2009, 11:10 PM
Grandad

Multinomial to Binomial

Hello druvid fae

Quote:

Originally Posted by druvid fae

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