0
$\begingroup$

I asked the following question .
Let $\pi$ be the partition of $n=a_1+a_2+...+a_r$, where $a_1\geq a_2 \geq ....\geq a_r\gt0$. Prove that number of partition $\pi$ of $n$ with $a_r=1$ and $a_j-a_{j+1}$ = 0 or 1 for $1\leq j\leq r-1$ equals $p^d (n)$, i.e the number of partitions of n into distinct parts, to which a user replied the following. ( I am only posting a part of the user's answer not the entire one)

Set $$\epsilon_j=a_j-a_{j+1} \quad \text{ for } \quad 1\leq j\leq r-1.$$ Then we have
$$ a_{r-j}=1+\epsilon_{r-1}+\cdots +\epsilon_{r-j} \quad \text{ for } \quad 1\leq j\leq r-1,$$

Can someone explain how he got the "then we have part " and what is its significance?

$\endgroup$
1
$\begingroup$

With

$$\epsilon_j=a_j-a_{j+1} \quad \text{ for } \quad 1\leq j\leq r-1 \tag{1}\label{eq1}$$

note that adding together a consecutive set of terms results in just the first term of the first value less the second terms of the last value due to the cancellations of all the intermediate values. Starting with the sum of the first $2$ terms gives

$$\epsilon_j + \epsilon_{j+1} = \left(a_j - a_{j+1}\right) + \left(a_{j+1} - a_{j+2}\right) = a_j - a_{j+2} \tag{2}\label{eq2}$$

Adding the next value gives

$$\left(\epsilon_j + \epsilon_{j+1}\right) + \epsilon_{j+2} = \left(a_j - a_{j+2}\right) + \left(a_{j + 2} - a_{j + 3}\right) = a_j - a_{j+3} \tag{3}\label{eq3}$$

This continues for each next term added. This type of series is often called a Telescoping series, with the sum being a telescoping sum.

As such, note that in

$$a_{r-j}=1+\epsilon_{r-1}+\cdots +\epsilon_{r-j} \quad \text{ for } \quad 1\leq j\leq r-1 \tag{4}\label{eq4}$$

the $\epsilon$ terms sum, in reverse order, is

$$\epsilon_{r-j} + \epsilon_{r-j + 1} + \cdots + \epsilon_{r-1} = a_{r-j} - a_{r} \tag{5}\label{eq5}$$

Thus, using $a_r = 1$ shows that \eqref{eq4} holds.

Its significance, as described in the original answer by user135826 in Number of partitions of a number into distinct parts., is this. Consider

$$n = \sum_{i=1}^r a_i \tag{6}\label{eq6}$$

using the form in \label{eq4} for all terms before the last one, with each term being $1$ and the sum of all $\epsilon$ values from $r - 1$ down to that term's index. Since each term has an initial value of $1$, there are $r$ of them. Next, all of the terms from $i = 1$ to $i = r - 1$ has an $\epsilon_{r-1}$ value, so there are $r - 1$ of them. Similarly, all of the terms from $i = 2$ to $i = r - 1$ has an $\epsilon_{r-2}$ value, so there $r - 2$ of them. In general, for all $1 \le j \le r - 1$, all of the terms from $i = j$ to $i = r - 1$ has an $\epsilon_{r-j}$ value, so there $r - j$ of them, and thus they contribute $\left(r - j\right)\epsilon_{r-j}$ to the sum. Putting this all together gives what the other answer shows, i.e., that

$$n=r+(r-1)\epsilon_{r-1}+ (r-2)\epsilon_{r-2}+\cdots +2\epsilon_2+\epsilon_1 \tag{7}\label{eq7}$$

As each $\epsilon_i$ is either $0$ or $1$, when you consider all possible combinations of values of $\epsilon_i$, this is the same as choosing a distinct subset of the values from $1$ to $r - 1$, and a maximum value of $r$, to sum to $n$, over all values of $r$ from $1$ to $n$. This is what the # of distinct partitions of $n$ refers to, such as is described in Partitions Into Distinct Parts.

To help see this, consider a quite simple case of $n = 5$, where the distinct partitions are $5$, $4 + 1$ and $3 + 2$, for $3$ in total. Consider \eqref{eq7} with $r$ being $1, 2, 3, 4, 5$. For $r = 1$, there are no cases as we get $5 = 1$. For $r = 2$, we have $5 = 2 + \epsilon_1$, which also has no cases. For $r = 3$, we have $5 = 3 + 2 \epsilon_2 + \epsilon_1$. This can only work if $\epsilon_2 = 1$ and $\epsilon_1 = 0$, for the $1$ case of $5 = 3 + 2$. For $r = 4$, we have $5 = 4 + 3 \epsilon_3 + 2 \epsilon_2 + \epsilon_1$. This can only be true if $\epsilon_3 = \epsilon_2 = 0$ and $\epsilon_1 = 1$, giving $1$ more case of $5 = 4 + 1$. Finally, for $r = 5$, we have $5 = 5 + 4 \epsilon_4 + 3 \epsilon_3 + 2 \epsilon_2 + \epsilon_1$. This case requires that all $\epsilon_i = 0$, to give one more case of $5 = 5$ which works. In total, it is once again $3$. If this example is possibly too simple & not convincing, then try a somewhat larger value like $6$ or $7$ to see the results form a specific ordering of the distinct partition cases.

$\endgroup$
  • $\begingroup$ 's answer math.stackexchange.com/a/3121640/263903 $\endgroup$ – Ayan Shah Feb 22 at 6:50
  • $\begingroup$ @AyanShah Thanks for providing the link. The extra information there helped me greatly to see what this person did. As you can see in my updated answer, I have explained the reasoning in more detail, including going through all of the steps of a fairly basic example. I hope this helps you to now understand what is going on. $\endgroup$ – John Omielan Feb 22 at 7:49
  • $\begingroup$ 's answer Thank you for the answer. It is much clearer now $\endgroup$ – Ayan Shah Feb 22 at 10:46
  • $\begingroup$ @AyanShah I'm glad I was able to be of some assistance. The original answer had several important implicit steps. $\endgroup$ – John Omielan Feb 22 at 18:22

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.