1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0

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.