2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you very much. Would you please explain how you get the first parenthesis in the first line? $\endgroup$ – No one Feb 17 '15 at 6:30
  • $\begingroup$ @Drupalist: I have added more explanation to that line. $\endgroup$ – robjohn Feb 17 '15 at 12:39
  • 1
    $\begingroup$ 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. $\endgroup$ – Ross Millikan Mar 7 '15 at 14:44
  • $\begingroup$ @RossMillikan: I was thinking of a similar amendment to my answer, but your description is a bit more succinct. $\endgroup$ – robjohn Mar 8 '15 at 0:55
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ If so, then the answer is coefficient of $x^{20}$ in $$(1-x^2)^{-1}(1-x)^{-1}(1-x)^{-1}$$, is it true? $\endgroup$ – No one Mar 4 '15 at 19:55
  • $\begingroup$ yes you're right $\endgroup$ – Vignesh Manoharan Mar 5 '15 at 6:31
  • 1
    $\begingroup$ @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$. $\endgroup$ – robjohn Mar 5 '15 at 9:14
  • $\begingroup$ @robjohn But what I said to Vignesh is true, yes? $\endgroup$ – No one Mar 5 '15 at 13:23
  • $\begingroup$ @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$. $\endgroup$ – robjohn Mar 5 '15 at 13:47

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.