Permutations and Combinations 3 Question 12
12. Let $n$ and $k$ be positive integers such that $n \geq \frac{k(k+1)}{2}$. The number of solutions $\left(x _1, x _2, \ldots, x _k\right)$, $x _1 \geq 1, x _2 \geq 2, \ldots, x _k \geq k$ for all integers satisfying $x _1+x _2+\ldots+x _k=n$ is …
(1996, 2M)
Show Answer
Answer:
Correct Answer: 12. $\frac{1}{2}\left(2 n-k^{2}+k-2\right)$
Solution:
- The number of solutions of $x _1+x _2+\ldots+x _k=n$
$=$ Coefficient of $t^{n}$ in $\left(t+t^{2}+t^{3}+\ldots\right)\left(t^{2}+t^{3}+\ldots\right) \ldots$
$=$ Coefficient of $t^{n}$ in $t^{1+2+\ldots+k}\left(1+t+t^{2}+\ldots\right)^{k}$
$$ \left(t^{k}+t^{k+1}+\ldots\right) $$
Now, $\quad 1+2+\ldots+k=\frac{k(k+1)}{2}=p$
[say]
and $\quad 1+t+t^{2}+\ldots=\frac{1}{1-t}$
Thus, the number of required solutions
$=$ Coefficient of $t^{n-p}$ in $(1-t)^{-k}$
$=$ Coefficient of $t^{n-p}$ in $\left[1+{ }^{k} C _1 t+{ }^{k+1} C _2 t^{2}+{ }^{k+2} C _3 t^{3}+\ldots\right]$
$={ }^{k+n-p-1} C _{n-p}={ }^{r} C _{n-p}$
where, $r=k+n-p-1=k+n-1-\frac{1}{2} k(k+1)$
$$ =\frac{1}{2}\left(2 k+2 n-2+k^{2}-k\right)=\frac{1}{2}\left(2 n-k^{2}+k-2\right) $$
