No. of positive integral solutions and link to coefficients in expansion

Question

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.

Answer 1

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.

Answer 2

If you suppose $p+q+r=8$ then they are natural numbers, so you can replace them with $x+1$, $y+1$ and $z+1$. Your new equation is $x+y+z=5$. The number of solutions is $7\choose2$. Similarly for remaining values, you will get the rest.

Answer 3

I guess I can help you by providing another way to think about the whole $n$ identical things being distributed among $r$ people.

So, imagine you have $n$ identical objects to be distributed in $r$ groups and you plan to do so by putting partitions/walls between them. Since there are $n$ objects, you've got $n-1$ spaces to put that partition, if you don't want any group to have $0$ objects(that is similar to saying that $x_i\geq1$). Also, since you want $r$ groups, the number of partitions you need to use is $r-1$.

Now, it breaks down to a simple Permutation Combination problem. Choose $r-1$ spaces/points from $n-1$, i.e. $$n-1\choose r-1$$ which gives you the "number of possible solutions under given constraint".

Also, the questions with a given constraint like $x_i\geq1$ have their branches in the Multinomial Theorem which is not a part of JEE Mains (I suppose) and given that NTA has placed a few questions which are way out of JEE Mains syllabus in there tests, you can surely move on.