The question (from an NTA sample paper for JEE Main) –
If $p, q, r \in \Bbb N $, then the number of points having position vector $p\hat{i} + q\hat{j} +r\hat{k}$ such that $8 \leq p + q + r \leq 12$ are:
It is evident that I had to essentially find the integral solutions for the inequalities given. I couldn't solve it in time and moved on. However upon reviewing the explanation and key concepts of the answer, I came out more perplexed and need help.
They explain that you have to add the no. of solutions for $p+q+r = 8, 9, 10, 11, 12$.
and also $p,q,r \geq{1}$.
I knew how to solve for $p,q,r \geq{0}$ using the "Beggar's method/ Fencing method", but did not know how to solve this case.
They used the formula, required number of positive integral solutions = ${n-1}\choose{r-1}$
and have written the solution as:
$${7\choose2} + {8\choose2} + {9\choose2} + {10\choose2} + {11\choose2} = 185$$
Makes sense, but here's the stuff that baffles me:
The number of integral solutions of $x_1 + x_2 + \ldots + x_r = n$, where $x_1 \geq 1, x_2 \geq 1, \ldots, x_r \geq 1 $ is the same as the number of ways to distribute n identical things among r persons getting at least 1. This is also equal to the coefficient of $x^n$ in $(x^1 + x^2 + \ldots )^r$
= coefficient of $x^n$ in $ x^r (1-x)^{-r}$ = coefficient of $x^{n-r}$ in $\{1 + rx + \frac{r(r+1)}{2!}x^2 + \cdots + \frac{r(r+1)(r+2)\ldots(r+n-1)}{n!}x^n + \ldots \}$
= $\frac{(n-1)!}{(n-r)!(r-1)!}$ = ${n-1 \choose r-1}$
They've also explained the case for $x \geq 0$ in a very similar manner above this, instead talking about coefficient of $x^n$ in $(1-x)^{-r}$. I'm struggling to understand what this means and how it ties in to combinations. I understand how the binomial theorem for natural indices uses combinations in effect to find the coefficient so I can see how they might also be important here, but there are a few things I'm not able to get here.
How can I solve this problem in an intuitive way (like the $x_i \geq 0$ case)? What do the coefficient of $x^n$ have to do with this at all? Any help is much appreciated.
Best Answer
The formula they use is the same as Theorem One from Stars and Bars.
This is proved by considering $k$ fences that lie strictly within the fields, and only one fence between each pair of fields.
The 'zero-option' allows for fences to be placed outside the fields, and also more than one together, creating 'empty spaces'.
The generating function (GF) used is:
$$(x^1 + x^2 + \ldots )^r$$
For the zero-option, we would use:
$$(1 + x + x^2 + \ldots )^r$$
and for example if there were to be at least two fields between fences, we would use:
$$(x^2 +x^3 + \ldots )^r$$
These all go into the binomial expansion, and we look for the coefficients of $x^n, x^{n-r}, x^{n-2r}, \dots$, depending on the minimum value of $x_i$ allowed.
Which is like giving the minimum values to each player, do a zero-based stars and bars, and then give this as extra to each player.