Number of distinct arrangements such that $n_1+n_2+n_3+n_4+n_5 = 20$ subject to given conditions

Question

Let $n_1<n_2<n_3<n_4<n_5$ be positive integers such that $$n_1+n_2+n_3+n_4+n_5=20$$ then the number of such distinct arrangements $(n_1,n_2,n_3,n_4,n_5)$ is?

So I tried this by generating a function, as following

Since $n_1<n_2<n_3<n_4<n_5$ , I set

$$n_2=n_1+k$$ $$n_3=n_2+p = n_1+p+k$$ $$n_4=n_3+q=n_1+p+k+q$$ $$n_5=n_4+r=n_1+p+k+q+r$$

So, putting this in the original equation I got

$$5n_1+4k+3p+2q+r = 20$$

where $n_1,p,q,r,k > 0$

Now my question is, what would be the upper limit in the series that I generate for this. I found another answer here that followed the same approach as I did (link: https://math.stackexchange.com/q/2401439) and then solved this by taking the limit of the upper variable as infinity and thus this is a summation of an infinite geometric series of which I take the coefficient of $x^{20}$ to find my required answer.

But I can't understand why should I take the limit as infinity in this particular question, and how to understand taking upper limits in further problems.

My book states

If upper limit of the variable is more than or equal to the sum required, then the upper limit of the variable can be taken as infinity.

If the upper limit of a variable is less than the sum required and the lower limit of the variable is non-negative, then the upper limit of that variable is that given in the problem.

I don't quite understand how it translates to this question, I mean how is it that I know that the upper limits of $n_1,k,p,q,r$ are greater than or equal to the sum required so as to take it as infinity?

Also can someone recommend further resources for studying these kind of questions (explained simply, I'm a high schooler).

Answer 1

Note that we can rewrite the problem as $$ \eqalign{ & \left\{ \matrix{ n_{\,1} < n_{\,2} < n_{\,3} < \cdots < n_{\,q - 1} < n_{\,q} \hfill \cr n_{\,1} + n_{\,2} + n_{\,3} + \cdots + n_{\,q - 1} + n_{\,q} = s \hfill \cr} \right. \cr & \quad \quad \Downarrow \cr & \left\{ \matrix{ n_{\,1} \le n_{\,2} - 1 \le n_{\,3} - 2 \le \cdots \le n_{\,q - 1} - \left( {q - 2} \right) \le n_{\,q} - \left( {q - 1} \right) \hfill \cr n_{\,1} + \left( {n_{\,2} - 1} \right) + \cdots + \left( {n_{\,q} - \left( {q - 1} \right)} \right) = s - \left( \matrix{ q \cr 2 \cr} \right) \hfill \cr} \right. \cr & \quad \quad \Downarrow \cr & \left\{ \matrix{ m_{\,1} \le m_{\,2} \le \cdots \le m_{\,q - 1} \le m_{\,q} \hfill \cr m_{\,1} + m_{\,2} + \cdots + m_{\,q - 1} + m_{\,q} = s - \left( \matrix{ q \cr 2 \cr} \right) \hfill \cr} \right. \cr} $$

That means that:
- if $1 \le m_1$, which means $ m_k \in \mathbb N$, then the number you are looking for is the number of partitions of $s -\binom{q}{2}$ into $q$ parts;
- if $0 \le m_1$, which means $ 0 \le m_k \in \mathbb Z$, then the number you are looking for is the number of partitions of $s -\binom{q}{2}$ into at most $q$ parts.

You can then refer to this Wikipedia article about partitions with restricted part size/number and to the vast literature on the subject.

Keeping instead with your approach, which is a valid alternative, we have $$ \eqalign{ & \left\{ \matrix{ 0 < n_{\,1} < n_{\,2} < n_{\,3} < \cdots < n_{\,q - 1} < n_{\,q} \hfill \cr n_{\,1} + n_{\,2} + n_{\,3} + \cdots + n_{\,q - 1} + n_{\,q} = s \hfill \cr} \right. \cr & \quad \quad \Downarrow \cr & \left\{ \matrix{ 1 \le n_{\,1} = m_{\,1} \hfill \cr 1 \le m_{\,k} = n_{\,k} - n_{\,k - 1} \quad \left| {\;2 \le k \le q} \right. \hfill \cr qm_{\,1} + \left( {q - 1} \right)m_{\,2} + \cdots + 2m_{\,q - 1} + 1m_{\,q} = s \hfill \cr} \right. \cr & \quad \quad \Downarrow \cr & \left\{ \matrix{ 0 \le p_{\,q + 1 - k} = m_{\,k} - 1 \hfill \cr 1p_{\,1} + 2p_{\,2} + \cdots + q\,p_{\,q} = s - \left( \matrix{ q + 1 \cr 2 \cr} \right) \hfill \cr} \right. \cr} $$

In your example with $q=5$ we have that, if we take the polynomial $$ \eqalign{ & P(x) = \left( {x^{\,1} \cdot x^{\,2} \cdot \cdots \cdot x^{\,5} } \right)\underbrace {\left( {x^{\,1} + x^{\,2} + \cdots + x^{\,5} } \right)\left( {x^{\,1} + x^{\,2} + \cdots + x^{\,5} } \right) \cdots \left( {x^{\,1} + x^{\,2} + \cdots + x^{\,5} } \right)}_{s - 1\, \le \,t\,{\rm terms}} \cr & = \cdots + x^{\left( {\scriptstyle 6 \atop \scriptstyle 2} \right)} x^{\,1\,k_{\,1} } x^{\,2\,k_{\,2} } \cdots x^{\,5\,k_{\,5} } + \cdots \quad \left| {\;0 \le k_{\,1} + k_{\,2} + \cdots + k_{\,5} = t} \right. \cr} $$ we do get $$ \left[ {x^{\,s} } \right]P(x) = {\rm number}\,{\rm of}\,{\rm solutions}\left\{ \matrix{ 1 \le \left( {k_{\,j} + 1} \right) \hfill \cr 1\,\left( {k_{\,1} + 1} \right) + 2\,\left( {k_{\,2} + 1} \right) + \cdots + 5\left( {k_{\,5} + 1} \right) = s \hfill \cr} \right. $$

Instead of the above, especially for analysis purposes, we have better to consider the fractional function (which has an infinite power expansion) $$ F(x) = {x \over {1 - x}}{{x^{\,2} } \over {1 - x^{\,2} }} \cdots {{x^{\,5} } \over {1 - x^{\,5} }} = x^{\left( {\scriptstyle 6 \atop \scriptstyle 2} \right)} {1 \over {1 - x}}{1 \over {1 - x^{\,2} }} \cdots {1 \over {1 - x^{\,5} }} $$ and this seems to be what your book is suggesting.

Answer 2

This infinity business is just a cleaner way of writing everything out which hides some computation. Instead of writing $$(x^5+x^{10}+x^{15} + x^{20})(x^4+\cdots + x^{20})(x^3+\cdots)\cdots$$ And explicitly stating that we only need terms $x^k$ with $k\leq 20$ to find the coefficient of $x^{20}$, we can just say find the coefficient of $x^{20}$ in $$\prod_{n=1}^5 \left(\sum_{k=1}^\infty x^{nk}\right) = \prod_{i=1}^5 \frac{x^n}{1-x^n} $$ This is probably what is meant by taking "infinity as the upper limit" instead of $20$. It's just really a notational thing.

The reason for using the infinite notation is that we now theoretically have an infinite polynomial, or "formal power series", for which the coefficient of $x^k$ is precisely whatever we are trying to count. Computationally, these notations are the same.