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.

What i have so Far:

I can see that since $a_r=1$ and $a_j-a_{j+1}$=0 or 1 so putting j = r-1 we have $a_{r-1}=1$. Similarly all $a_j$ must be 1.This implies that no two $a_j$ are equal. Please help

  • $\begingroup$ This sounds very similar to your previous question? Perhaps we/you should first solve the other one before posting new ones immediately. $\endgroup$ – Dietrich Burde Feb 21 at 15:40
  • $\begingroup$ @Dietrich Burde Any help on either of them would be appreciated $\endgroup$ – Ayan Shah Feb 21 at 16:06

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,$$ so $$ n=r+(r-1)\epsilon_{r-1}+ (r-2)\epsilon_{r-2}+\cdots +2\epsilon_2+\epsilon_1 $$ defines a partition of $n$ with all distinct parts (ignoring the summands with $\epsilon_j=0$) and highest part being $r$. The correspondence thus defined is bijective: follow the same steps in reverse order.

  • $\begingroup$ can you please point out if there is any mistake in my reasoning? $\endgroup$ – Ayan Shah Feb 21 at 18:39
  • $\begingroup$ Also, can you elaborate on the equivalence of data you mentioned? $\endgroup$ – Ayan Shah Feb 21 at 18:41
  • $\begingroup$ I do not understand it: $a_r=1$ and $a_{r-1}-a_r=a_{r-1}-1=0$ or $1$ only implies $a_{r-1}=1$ or $2$. $\endgroup$ – user135826 Feb 21 at 18:43
  • $\begingroup$ OOH...that was a mistake, thanks. Can you elaborate on the last line of your proof? $\endgroup$ – Ayan Shah Feb 21 at 18:53
  • $\begingroup$ I edited the answer to clarify. $\endgroup$ – user135826 Feb 21 at 18:56

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.