• Jan 7th 2009, 01: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, 12: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 $\displaystyle 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 $\displaystyle n=1$. Clearly there is no solution unless $\displaystyle k_1 \ge c + 1$, since $\displaystyle x_1<k_1$, and one solutions otherwise.

Now consider $\displaystyle n=2$.

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

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

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

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

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

Now consider $\displaystyle n = 3$.

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

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

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

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

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

$\displaystyle 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:

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

For the general case, $\displaystyle n$
, for the maximum number of solutions $\displaystyle k_i \ge c-n+2$ and $\displaystyle c \ge n$; and, again, for every integer value below $\displaystyle c-n+2$ that a $\displaystyle k_i$ falls, the number of solutions will be reduced by $\displaystyle 1$ (I think!). How do you get the maximum number of solutions? Is it $\displaystyle _{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 $\displaystyle n=4$, and indeed it is $\displaystyle \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 $\displaystyle n = 4$, I used the solution for $\displaystyle n=3$ as follows:

If $\displaystyle x_1 = c-i$, then $\displaystyle x_2+x_3+x_4 = i$, and the number of ways in which this can occur is the same as the problem for $\displaystyle n = 3$, with $\displaystyle c$ being replaced by $\displaystyle i$. Could a recursive method like this be applied to the general case, or is there a more direct way?
• Jan 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.

$\displaystyle ^{c+m - 1}C _{m-1}$ and for positive integral solutions $\displaystyle ^{c - 1}C _{m-1}$(m-1 choose c-1).
ans: The number of ways in which they can denote $10 is the same as the number of solutions to the equation$\displaystyle x_1 + x_2 + x_3 = 10$subject to the condition that$\displaystyle 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$\displaystyle x^10$in$\displaystyle (1+ x + x^2 + ..... + x^6)((1+ x + x^2 + ..... + x^7)(1+ x + x^2 + ..... + x^8)$= coef of x^10 in$\displaystyle (1- x^7)(1- x^8)(1- x^9)(1 - x)^-3 $= coef of x^10 in$\displaystyle (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 =$\displaystyle ^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 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$\displaystyle x^10$in$\displaystyle (1+ x + x^2 + ..... + x^6)((1+ x + x^2 + ..... + x^7)(1+ x + x^2 + ..... + x^8)$= coef of x^10 in$\displaystyle (1- x^7)(1- x^8)(1- x^9)(1 - x)^-3 $= coef of x^10 in$\displaystyle (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 =$\displaystyle ^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$\displaystyle 1+ x + x^2 + ..... + x^6$is a GP with$\displaystyle a = 1$,$\displaystyle r = x$and$\displaystyle n = 7$. So$\displaystyle 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$\displaystyle 1 - x^n = 0$when$\displaystyle x = 1$, so$\displaystyle (1-x)$is always a factor of$\displaystyle (1 - x^n)$, and use algebraic long division to confirm that$\displaystyle \frac{1 - x^n}{1-x} = 1+ x + x^2 + ..... + x^7\$