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.

2. ## Combinatorics

Hello druvid fae
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?

3. 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).