Combinatorics. Please explain me how to do it.

Question

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!

Answer 1

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$$

Answer 2

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$

Answer 3

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

$12C2-5C2-4C2-3C2$