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

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.

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 1s and \lt two 2s}}+\overbrace{x^3\overbrace{\frac{1-x^6}{1-x^2}}^{1+x^2+x^4}}^{\text{three 1s and \lt three 2s}}+\dots\left.\vphantom{\frac12}\right)\overbrace{\overset{\vphantom{\overbrace{a^2}}}{\frac1{1-x^3}}}^{\text{any 3s}}\\ &=\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$.

• Thank you very much. Would you please explain how you get the first parenthesis in the first line? – No one Feb 17 '15 at 6:30
• @Drupalist: I have added more explanation to that line. – robjohn Feb 17 '15 at 12:39
• In this case, there is a nice intuition about the result. It says you are making the sum out of at least one one(the $\frac x{1-x}$ term) and two kinds of threes (the two $\frac 1{1-x^3}$ terms). One kind of threes stays threes, the other gets broken down into $1+2$. This guarantees more ones than twos as required. – Ross Millikan Mar 7 '15 at 14:44
• @RossMillikan: I was thinking of a similar amendment to my answer, but your description is a bit more succinct. – robjohn Mar 8 '15 at 0:55

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

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

• If so, then the answer is coefficient of $x^{20}$ in $$(1-x^2)^{-1}(1-x)^{-1}(1-x)^{-1}$$, is it true? – No one Mar 4 '15 at 19:55
• yes you're right – Vignesh Manoharan Mar 5 '15 at 6:31
• @VigneshManoharan: The coefficient of $x^{20}$ in $\frac1{(1-x^2)(1-x)^2}$ is $121$. However, in the unrestricted case, the coefficient of $x^{20}$ in $\frac1{(1-x)(1-x^2)(1-x^3)}$ is only $44$. – robjohn Mar 5 '15 at 9:14
• @robjohn But what I said to Vignesh is true, yes? – No one Mar 5 '15 at 13:23
• @Drupalist: yes, $\frac1{(1-x^2)(1-x)^2}$ is the generating function for the number of non-negative solutions to $2a+b+c=n$. – robjohn Mar 5 '15 at 13:47