equality between partitions using generating series

72 Views Asked by At

Use a generating series to prove that the number of unordered compositions or partitions of $n$ in which only the odd parts can be repeated is the number of partitions of $n$ where no part can be repeated more than $3$ times.

The number of compositions of $n$ is $2^{n-1}$, which can be found by listing $n$ $1$'s and placing a $+$ or $,$ between them; there is a bijection between the set of such arrangements and the set of compositions of $n$. For the case where $n=3,$ the partitions where only odd parts can be repeated are $(1,1,1),(2,1),(3)$, which are also all the partitions where no part can be repeated more than $3$ times. For $n=5,$ the partitions where only odd parts can be repeated are $(1,1,1,1,1),(2,1,1,1),(2,3),(3,1,1),(4,1),(5)$ and the partitions where no part can be repeated more than $3$ times are $(2,1,1,1),(2,3),(3,1,1),(4,1),(5),(2,2,1).$ I can't seem to find a pattern for this other than the obvious fact that the intersection of $A_n := \{\text{set of partitions of $n$ where only the odd parts can be repeated}\}$ and $B_n := \{\text{set of partitions of $n$ where no part can be repeated more than $3$ times}\}$ is $C_n := \{\text{set of partitions where only the odd parts can be repeated, but no more than $3$ times}\}$. Also I'm not sure if a recurrence relation will be useful to determine the number here.

1

There are 1 best solutions below

0
On BEST ANSWER

The generating function for partitions into even parts only occurring once and odd parts as many as you like is \begin{eqnarray*} \prod_{i=1}^{\infty} \frac{1+x^{2i}}{1-x^{2i-1}}. \end{eqnarray*} The generating function for partitions where parts occur three times at most is \begin{eqnarray*} \prod_{i=1}^{\infty} (1+x^i+x^{2i}+x^{3i}) =\prod_{i=1}^{\infty} (1+x^i)(1+x^{2i}). \end{eqnarray*} To see the equality of these, note that \begin{eqnarray*} \frac{1}{1-x^{2i-1}} = \prod_{j=0}^{\infty} (1+x^{(2i-1)2^{j}}) \end{eqnarray*} and every number can be uniquely expressed as $ (2i-1)2^{j}$.

Hint to show the last equality ... \begin{eqnarray*} \frac{1}{1-y} = 1+y+y^2+y^3+ \cdots=(1+y)(1+y^2)(1+y^4)\cdots \end{eqnarray*} or use induction.