2
$\begingroup$

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

$\endgroup$
18
  • 2
    $\begingroup$ Seems unnecessarily complicated. We must have $n_1≥1, n_2≥2$ and so on, and $1+2+3+4+5=15$ already so you just have to distribute $5$ amongst those values, while respecting the rules. Thus, if, say, you increase $n_1$ by $1$ you must add $1$ to each of the other elements. Not a lot of ways to do that. $\endgroup$
    – lulu
    Jan 25 '20 at 18:42
  • $\begingroup$ Should say: With bigger values, I can imagine that some algebraic machinery is helpful. Here, I think it gets in the way. $\endgroup$
    – lulu
    Jan 25 '20 at 18:46
  • $\begingroup$ @lulu yes i just want a general method for problems with let's say where the sum = 70 $\endgroup$
    – Techie5879
    Jan 25 '20 at 18:47
  • $\begingroup$ @lulu Also, this is for a competitive exam, so if I miss just a single value while calculating manually it would be a disaster...much better to use algebraic manipulation $\endgroup$
    – Techie5879
    Jan 25 '20 at 18:51
  • $\begingroup$ Ah, there I strongly disagree. Well, it depends what tools you have. If you have high powered algebraic software (Wolfram Alpha or the equivalent) then sure. Generating functions are easy to program and the machine does all the hard work for you. But my method is effortlessly worked by hand whereas multiplying those power series by hand is profoundly error prone. $\endgroup$
    – lulu
    Jan 25 '20 at 18:53
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.