Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In how many different ways three persons A, B, C having 6, 7 and 8 one rupee coins respectively can donate Rs.10 collectively? This isn't a homework question. Please explain me the steps. Thank you!

share|cite|improve this question
up vote 2 down vote accepted

Let $a,b,c$ be the amounts that $A,B$ and $C$ give resp. Then we want to count the number of distinct solutions to $a + b + c = 10$ under the condition that $a,b,c$ are positive integers and $a \le 6, b \le 7, c \le 8$.

One way to compute this is to compute the coefficient of $x^{10}$ in the expression $(1+x+\ldots +x^6)(1+x+\ldots +x^7)(1+x+\ldots +x^8)$ ($a$ is the exponent we choose in the first term, $b$ in the second etc., so the fact that we go up to $x^6$ in the first term expresses the $a \le 6$ and so on.)

We can write these terms as $\frac{1-x^7}{1-x}$, $\frac{1-x^8}{1-x}$ and $\frac{1-x^9}{1-x}$, respectively, so this product equals

$$(1-x^7)(1-x^8)(1-x^9)(1-x)^{-3}$$ and then we can use the general Newton formula to compute the coefficient of $x^{10}$ (we expand $(1-x)^{-3}$ using that, and then count the (not too many) ways the first terms give rise to a power of $x$ that is $\le 10$).

Expanded: the general binomial implies

$$(1-x)^{-3} = \sum_{n=0}^{\infty} \binom{k+2}{2} x^k$$

e.g. see here, and now note that we can form $x^{10}$ by picking 1's in the first 3 terms and the coefficient of $x^{10}$ in this expansion, so $\binom{12}{2}$, and also by picking $-x^7$,1,1 and $\binom{5}{3}$ (term for $x^3$), $1,-x^8,1$ and the $x^2$ term and finally $1,1,-x^9$ and the term for $x^1$ in the infinite expansion.

So we get $$\binom{12}{2} - \binom{5}{3} - \binom{4}{2} - \binom{3}{1} = 47$$

share|cite|improve this answer
that is what I want to know. How to compute the coefficient of x^10? Please elaborate. – Somebody Feb 3 '13 at 13:36

If $A$ gives $a$ coins, clearly, $0\le a\le 6$

and $B+C=10-a$

Now, $0\le B\le 7\implies 0\le 10-a-C\le 7\implies 3-a\le C\le 10-a $

Also, $0\le C\le 8\implies$ max $(3-a,0)\le C\le $ min$(10-a,8)$

If $a=0,$ max $(3,0)\le C\le $ min$(10,8)\implies 3\le C\le 8$ so $C$ can assume $8-3+1=6$ values.

Similarly, for $a=1,2,3,4,5,6;$ $ C$ can assume $7,8,8,7,6,5$ values respectively.

So, the number possible combinations are $6+7+8+8+7+6+5=47$

share|cite|improve this answer
how do you do it using multinomial theorem? – Somebody Feb 3 '13 at 13:35
@PushkarMishra, the coefficient of $x^{10}$ in $(1-x^7)(1-x^8)(1-x^9)(1-x)^{-3}$ is the coefficient of $x^{10}$ in $(1-x)^{-3}$-the coefficient of $x$ in $(1-x)^{-3}$-the coefficient of $x^2$ in $(1-x)^{-3}$-the coefficient of $x^3$ in $(1-x)^{-3}$ which is $66-(3+6+10)=47$ – lab bhattacharjee Feb 3 '13 at 13:48

Let A,B,C donate $x_1,x_2,x_3$ coins with $x_i\geq 0$.

Then A/Q $\sum x_i=10$ .....(1)

At first lets find all the solutions of this equation in integers.

The no. of such solution is $12C2$

Now we will find the no. of solution in which $x_1\geq 7$,(these solutions cant be considered),

To find this lets replace $x_1$ by $x+6$ where $x\geq 1$ putting this into 1 we have $x+x_2+x_3=4$ we will find no. of such solns. $5C2$

In this way we will find the other cases which are not possible.

Namely when $x_2\geq8$ in this case we have $4C2$ solutions , and the last one when $x_3\geq 9$ then we have $3C2$ solutions.

All the cases which cant be posiible are disjoint implying the total no. of solution =(total no. of cases)-(cases not possible).


share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.