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

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.

• Think about conjugate partitions. – Angina Seng Aug 8 '19 at 19:19

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

• I haven't seen that in each partition of Ferrer's diagram there is a part with size $r$. There must be part like that because of condition that each part $\ge 1$. So this is guaranteed and we must take this into our generating function. Thanks a lot! – Tester1998 Aug 8 '19 at 21:21

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.

• but where in this solution is $r$? – Tester1998 Aug 8 '19 at 19:26
• @Tester1998 The number of parts in a plain partition corresponds to the size of the largest part in a distinct parts partition, so if $d(n,r)$ denotes the number of distinct parts partitions with largest part $r$, the generating function is $$\sum_{n,r \geq 1} d(n,r) x^n y^r= \sum_{r \geq 1} y^rx^r \prod_{j=1}^{r-1} (1+x^j),$$ this is what you originally had, and it is correct! – Dzoooks Aug 8 '19 at 20:03
• @Tester1998 Indeed, it should be $\prod_{n=1}^r(1+x^n)$. – Mike Earnest Aug 8 '19 at 20:04
• @MikeEarnest but this is wrong, I gave example in topic that for $n=15$ and $r=6$ it gives wrong answer – Tester1998 Aug 8 '19 at 20:59
• @Tester1998 Apologies, I did not read your post carefully enough. See my answer. – Mike Earnest Aug 8 '19 at 21:12

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