Partitions of $n$ where every element of the partition is different from 1 is $p(n)-p(n-1)$

79 Views Asked by At

I am trying to prove that $p(n|$ every element in the partition is different of $1)=p(n)-p(n-1)$, and I am quite lost... I have tried first giving a biyection between some sets, trying to draw an example in a Ferrers diagram and working on it... Nevertheless, I have not obtained significant results. Then, I have thought about generating functions; we know that the generating function of $\{p(n)\}_{n\in\mathbb{N}}$ is $\prod_{i=1}^{\infty}\frac{1}{1-x^{i}}$, so $\{p(n-1)\}_{n\in\mathbb{N}}$ will have $\prod_{i=1}^{\infty}\frac{x}{1-x^{i}}$ as generating function. So, what we have to prove is that $\prod_{i=1}^{\infty}\frac{1}{1-x^{i}}-\prod_{i=1}^{\infty}\frac{x}{1-x^{i}}=(1-$x)$\cdot$$\prod_{i=1}^{\infty}\frac{1}{1-x^{i}}$ is the generating function of $p(n|$every element in the partition is different of $1$)... but i'm am not seeing why! Any help or hint will be appreciate it! Thanks!

1

There are 1 best solutions below

1
On BEST ANSWER

Totally: there are $p(n)$ partitions of $n$.
You want to avoid the partitions which have a $1$ in them. Do you see a natural bijection: $$\{\text{partitions of $n$ with a $1$}\} \leftrightarrow \{\text{partitions of $n - 1$}\}?$$ (Hint: To go from the left to the right, simply delete a $1$ from that partition.)

Note that the set on the right has cardinality $p(n - 1)$. Subtracting this from the total gives you the desired quantity.