Plain integer partitions of $n$ using $r$ parts

Question

Division of number $n$ on parts $a_1,...,a_r$ where $a_1 \le ... \le a_r$ we call a plain if $a_1 = 1$ and $a_i - a_{i-1} \le 1$ for $2 \le i \le r$. Find enumerator (generating function) for plain divisions.

my try

The hint was to use bijection between plain divisions and some commonly know enumerator. I tried to use enumerator of divisions on different parts: $$ (1+x)(1+x^2)...(1+x^r)$$ where number of plain divisions is

$$[x^n](1+x)(1+x^2)...(1+x^r) $$ let function $$f(n,r) = [x^n](1+x)(1+x^2)...(1+x^r) $$

For some first divisions it works. For example: $$f(4,3) = 1 $$ $$f(6,3) = 1 $$ $$f(11,5) = 2$$ But when I tried to find bijection, I failed. I found that this function isn't correct because $f(15,6) = 4$ but should be equal to $3$ because: $$15 = 1,1, 2, 3, 4, 4 \\ 15 = 1, 2, 2, 3, 3, 4\\ 15 = 1, 2, 3, 3, 3, 3 $$. There I stucked.

Answer 1

The set of plain division of $n$ into $r$ parts is in bijection with the set of divisions of $n$ into distinct parts whose largest part is equal to $r$. The bijection is conjugation, i.e. reflecting the Ferrer's diagram. Since there must be a part of size $r$, the factor must be $x^r$ instead of $(1+x^r)$, while all other parts are the same as what you had. Therefore, the generating function is $$ (1+x)(1+x^2)\dots(1+x^{r-1})x^r. $$ Note that the coefficient of $x^{15}$ in $(1+x)\cdots(1+x^5)x^6$ is indeed $3$.

Answer 2

Are you familiar with Ferrer's Diagrams? Make a row of dots for each part, so the plain partition $(4,4,3,2,1,1,1)$ is $$\begin{matrix} \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \\ \bullet & \bullet & & \\ \bullet & & & \\ \bullet & & & \\ \bullet & & & \\ \bullet & & & \\ \end{matrix}$$

Now look at the columns. You get the partition into distinct parts $(8,4,3,2)$. Try to prove that this bijection works.

Now, $$\sum_{n \geq 1} d(n) x^n = \prod_{n \geq 1} \left(1+x^n \right),$$ where $d(n)$ is the number of partitions of $n$ into distinct parts. But by the bijection, $d(n)$ equals the number of plain partitions of $n$, so the above product is the required generating function.

Answer 3

Let $0\leq d_{i-1}:=a_i - a_{i-1} \le 1$ be the $i$-th increment for $2\leq i\le r$ then $$d_1+\dots+d_{i-1}=a_i-1$$ and $$(r-1)d_1+(r-2)d_2+\dots+1\cdot d_{r-1}=a_2+a_3+\dots +a_r-(r-1)=n-r$$ that is $$r+1\cdot d_{r-1}+\dots+(r-2)d_2+(r-1)d_1=n.$$ with $d_i\in\{0,1\}$. It follows that the generating function for a given $r\geq 2$ is $$x^{r}\prod_{k=1}^{r-1}(1+x^k).$$