Generating function for the number of ways to part an integer $n$ such that no summand will repeat more than 3 times

Question

What is the generating function for the number of ways to part an integer $n$ such that no summand will repeat more than 3 times?

For example: $n=6$ so we can part it like this: $1+1+1+3$ but not like this: $1+1+1+1+2$.

I think the parenthesis are: $(1)(1+x)(1+x+x^2)(1+x+x^2+x^3)$ each one represent a repetition of $0,1,2,3$. Is this right?

Or is it: $(1)(1+x^2)(1+x^3)(1+x^4)$?

Answer 1

The generating function you're looking for is: $$\prod_{i=1}^{\infty}\left(1+x^i+x^{2i}+x^{{\displaystyle \color{#f00}3i}}\right)$$

I will let you think why this is the answer? I will give you an example take $n=3$ the questions you have to answer are:

• What is the coefficient of $x^3$ when you expend the product: $$\prod_{i=1}^{\color{#00f}3}(1+x^i+x^{2i}+x^{3i})=(1+x+x^2+x^3)(1+x^2+x^4+x^6)(1+x^3+x^6+x^9)$$ $$=1 +\color{#f00}1 x +\color{#f00} 2 x^2 +\color{#f00} 3 x^3 + 3 x^4 + 4 x^5 + 5 x^6 + 5 x^7 + 5 x^8 + 6 x^9 + 5 x^{10} + 5 x^{11} +\cdots $$
• What is the number of representation of $3$ as you described them: $$\begin{align}\color{#0a0}1&\color{#0a0}{=1}& 2&=1+1& \color{#0a0}3&\color{#0a0}{=1+1+1}&4&=1+1+1+1\\&& 2&=2& \color{#0a0}3&\color{#0a0}{=1+2}&4&=1+1+2\\&&&&\color{#0a0}3&\color{#0a0}{=3}&4&=2+2 \\ &&&&&&4&=4\\ &\color{#f00}1&&\color{#f00}2&&\color{#f00}3&&\color{#f00}4 \end{align}$$

(In the product the coefficient of $x^4$ is only $3$ because we did not yet expand until $i=\color{#00f}4 $)

Now I invite you to expand the product without summing the exponent I mean when you have $x^i\cdot x^j$ just write it as $x^{i+j}$ and don't sum $i+j$ you will obtain: $$1+x^{\color{#0a0}1}+x^{1+1}+x^{2}+x^{\color{#0a0}{1+1+1}}+x^{\color{#0a0}{1+2}}+x^{\color{#0a0}3}+x^{1+1+1+1}+x^{1+1+2}+x^{2+2}+x^4 $$

Now I will answer the question why this is the right answer, when you expand the following product: $$\prod_{i=1}^{\infty}\left(1+x^i+x^{i+i}+x^{i+i+i}\right)$$

you will get : $$\cdots+x^{n_1+n_2+\cdots+n_k}+\cdots$$ where: $$ \begin{align} n_1&=i_1&\text{or}&&n_1=i_1+i_1&&\text{or}&&n_1=i_1+i_1+i_1\\ n_2&=i_2&\text{or}&&n_2=i_2+i_2&&\text{or}&&n_2=i_2+i_2+i_2\\ \cdots &\cdots\\ n_k&=i_k&\text{or}&&n_k=i_k+i_k&&\text{or}&&n_3=i_k+i_k+i_k \end{align} $$

so the number of times $x^n$ occurs in the expansion of this product is the number of possible writing of $n$ as sum of positive integers $i_k$ such that no one occurs more than $3$ times