How to build generating function when there is restriction on number of occurrences

Question

Let me ask my question in this way:

Suppose we are going to represent number $20$ as sum of $1$s and $2$s and $3$s, the coefficient of $x^{20}$ in this generating function is the answer :

$(1+x+x^2+x^3+...)(1+x^2+x^4+...)(1+x^3+x^6+...)$

Now if we put this restriction that the number of occurrences of $1$s must be more than number of occurrences of $2$s in the sequence of numbers that build $20$ then what generating function is going to be the answer. actually this problem can be generalized to many other cases.

Answer 1

Summing the cases for the number of $1$s, we get $$ \begin{align} &\left(\vphantom{\frac12}\right.\overbrace{x\overbrace{\frac{1-x^2}{1-x^2}}^{1}}^{\text{one $1$ and $\lt$ one $2$}}+\overbrace{x^2\overbrace{\frac{1-x^4}{1-x^2}}^{1+x^2}}^{\text{two $1$s and $\lt$ two $2$s}}+\overbrace{x^3\overbrace{\frac{1-x^6}{1-x^2}}^{1+x^2+x^4}}^{\text{three $1$s and $\lt$ three $2$s}}+\dots\left.\vphantom{\frac12}\right)\overbrace{\overset{\vphantom{\overbrace{a^2}}}{\frac1{1-x^3}}}^{\text{any $3$s}}\\ &=\left(\frac{x}{1-x}-\frac{x^3}{1-x^3}\right)\frac1{(1-x^2)(1-x^3)}\\ &=\frac{x(1+x)}{(1-x^2)(1-x^3)^2}\\ &=\bbox[5px,border:2px solid #C00000]{\frac{x}{(1-x)(1-x^3)^2}}\tag{1} \end{align} $$ Now find the coefficient of $x^{20}$ in $(1)$.

We can compute the coefficients $$ x\sum_{j=0}^\infty x^j\sum_{k=0}^\infty(k+1)x^{3k} =\sum_{n=1}^\infty\frac12\left\lfloor\frac{n+2}3\right\rfloor\left\lfloor\frac{n+5}3\right\rfloor x^n\tag{2} $$ since all $k\le\frac{n-1}3$ contributes $k+1$. That is, $$ \begin{align} \sum_{k=0}^{\left\lfloor\frac{n-1}3\right\rfloor}(k+1) &=\frac12\left(\left\lfloor\frac{n-1}3\right\rfloor+1\right)\left(\left\lfloor\frac{n-1}3\right\rfloor+2\right)\\ &=\frac12\left\lfloor\frac{n+2}3\right\rfloor\left\lfloor\frac{n+5}3\right\rfloor \end{align} $$ For $n=20$, this gives $28$.

Answer 2

Let $ k_{1} , k_{2}, k_{3}$ be number of 1's ,2's and 3's. You want $k_1 \ge k_2 \rightarrow k_1 - k_2 \ge 0$

So let $k_{2}^{'} = k_1 - k_2 \ge 0$ and your condition is

---

EDIT: this is wrong , I lost sight of the original question

$2k_1 + k_{2}^{'} + k_3 = 20$

---

EDIT : correct solution : as $ k_1=k_2+k_2^{'}$ , the correct equation is

$k_2+k_2^{'}+2k_2+3k_3 =k_2^{'}+3k_2+3k_3 = 20 $

The corresponding generating function is $(1-x)^{-1}(1-x^3)^{-2}$.

The coefficient of $x^{20}$ is 28 ( <44 :-) )

---

EDIT 2: Since the op wants $k1>k2$ and not $k1 \ge k2$ , $ k_1=k_2+k_2^{'}+1$ leading to $k_2^{'}+3k_2+3k_3 = 19 $ with answer coefficient of $x^{19}$ in $(1-x)^{-1}(1-x^3)^{-2}$ which is also 28

Answer 3

If there were complicated rules relating the frequencies of different parts, then there would be no obvious way to write a generating function. Here however it is simple: a first part $1$ is obligatory, then every part $2$ brings along one part$~1$, and then there may be some parts$~1$ left that get in unaccompanied. So effectively you are allowing parts $1$ (among which a first one is obligatory), and two different kinds of parts$~3$, namely plain $3$ and ($2$-$1$) pairs. The generating function then is $$(x+x^2+x^3+\cdots)+(1+x^3+x^6+\cdots)^2 =\frac x{1-x}×\left(\frac 1{1-x^3}\right)^2 =\frac x{(1-x)(1-x^3)^2}. $$