5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Think about conjugate partitions. $\endgroup$ – Angina Seng Aug 8 '19 at 19:19
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Tester1998 Aug 8 '19 at 21:21
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ but where in this solution is $r$? $\endgroup$ – Tester1998 Aug 8 '19 at 19:26
  • $\begingroup$ @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! $\endgroup$ – Dzoooks Aug 8 '19 at 20:03
  • $\begingroup$ @Tester1998 Indeed, it should be $\prod_{n=1}^r(1+x^n)$. $\endgroup$ – Mike Earnest Aug 8 '19 at 20:04
  • 1
    $\begingroup$ @MikeEarnest but this is wrong, I gave example in topic that for $n=15$ and $r=6$ it gives wrong answer $\endgroup$ – Tester1998 Aug 8 '19 at 20:59
  • $\begingroup$ @Tester1998 Apologies, I did not read your post carefully enough. See my answer. $\endgroup$ – Mike Earnest Aug 8 '19 at 21:12
0
$\begingroup$

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

$\endgroup$

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.