• Jan 7th 2009, 02:13 AM
druvid fae
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.

• Jan 8th 2009, 01:43 AM
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.

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

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?
• Jan 30th 2009, 11: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.

$^{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.
• Jan 31st 2009, 12:10 AM
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?