2
$\begingroup$

I am new to generating functions / power series and I am struggling with expanding following generating function: $$F(x)=\frac{(x^2-x^{10})(1-x^{10})^3}{(1-x)^4}$$ I tried to pattern my solution on that answer and expand generating function in the same way, so i rewrote $F(x)$ as: $$F(x)=\frac{x^2(1-x^8)(1-x^{10})^3}{(1-x)^4}$$ and in order to obtain coefficient at $x^{20}$ I tried to calculate: $${(20-2)+3 \choose 3}-{(20-2)-8+3 \choose 3}-{(20-2)-10+3 \choose 3} \cdot 3$$ The result of this is $549$ which is smaller by $3$ than proper solution which is $552$. I don't know what I did wrong. In fact, I don't understand this method of expanding coefficients so if you could provide the name of this technique or some resources to read about I would be thankful. I mean, I see the pattern this technique follows, but I don't see why it works.

This generating function gives solution to one problem that I solved first in purely combinatoric way. My calculations were nearly identical to these presented above, but I had to exclude intersection of two sets which was of size $3$. So I understand that there should be $+3$ term in solution above, but I don't know where it would come from in case of expanding generating function.

$\endgroup$
1
$\begingroup$

Using negative binomial series,

\begin{align} F(x) &= x^2(1-x^8)(1-3x^{10}+3x^{20}-x^{30})(1-x)^{-4}\\ &= x^2(1-x^8)(1-3x^{10}+3x^{20}-x^{30})\sum_{k=0}^\infty \binom{4+k-1}{k} x^k\\ &= (x^2-x^{10})(1-3x^{10}+3x^{20}-x^{30})\sum_{k=0}^\infty \binom{3+k}{k} x^k\\ &= (x^2-3x^{12}-x^{10}+\color{blue}{3x^{20}}+p(x))\sum_{k=0}^\infty \binom{3+k}{3} x^k\\ \end{align}

where $p(x)$ are higher order terms that are not interesting for the question.

Hence

$$\binom{18+3}{3}-3\binom{11}{3}-\binom{13}{3}+3\binom{3}{3}$$

I suspect you left out the case where we let $k=0$.

$\endgroup$
  • $\begingroup$ I misunderstood the process of expanding generating function. Looking at the example I linked to, I didn't realize it's author skipped some part of calculations and just gave the final result. This is why I was confused. Thank you for answer. $\endgroup$ – mrJoe Feb 16 '18 at 18:13
1
$\begingroup$

I think that you missed one term. Notice that $$(1-x^8)(1-x^{10})^3=(1-x^8)(1-3x^{10}+O(x^{20}))=1-x^8-3x^{10}+3x^{18}+o(x^{18}).$$ Hence \begin{align} [x^{20}]\frac{x^2(1-x^8)(1-x^{10})^3}{(1-x)^4} &=[x^{18}]\frac{1-x^8-3x^{10}+3x^{18}+o(x^{18})}{(1-x)^4}\\ &=[x^{18}]\frac{1}{(1-x)^4}-[x^{10}]\frac{1}{(1-x)^4}-[x^{8}]\frac{3}{(1-x)^4}+[x^{0}]\frac{3}{(1-x)^4}\\ &=\binom{18+3}{3}-\binom{10+3}{3}-3\binom{8+3}{3}+3=552. \end{align}

$\endgroup$
  • $\begingroup$ Thank you for explanation. I missed one term because I wrongly deduced the pattern of expanding generating functions. So if there was a term in numerator like (1+x)^123 we would have to calculate it? I thought there is some way to avoid exponentiation. $\endgroup$ – mrJoe Feb 16 '18 at 18:09
  • $\begingroup$ Could you rephrase your question, please? $\endgroup$ – Robert Z Feb 16 '18 at 18:24
  • $\begingroup$ I mean, we had to expand numerator and then split function into partial fractions. In my situation there was a value (1+x^10)^3 so it was not hard to expand it. But if the exponent was e.g. 123 we would have a lot of work to do. So I wondered if there is a technique which lets avoid this time-consuming calculation. $\endgroup$ – mrJoe Feb 16 '18 at 18:54
  • $\begingroup$ No, it suffices to consider $(1-x^{10})^{123}=1-123x^{10}+O(x^{20})$ $\endgroup$ – Robert Z Feb 16 '18 at 18:59

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.