0
$\begingroup$

I have an assignment to search how many solution of $a+b+c+d=100$ where $1\leq a\leq 10, b\geq 0, c\geq 2, 20\leq d \leq 30$. So I use the generating function method. So I got the generating function that is :
$[x^{100}] \frac {x^{23}(1-x^{10})(1-x^{11})}{(1-x)^4}$
which is congruent too :
$[x^{77}] \frac {(1-x^{10})(1-x^{11})}{(1-x)^4}$
Then I begin to search the coefficient by using extended binomial formula for this, and I found that this has so many case which is about $P(8,2)=8*7=56$ ways. I wont write all the 56 total ways of combination for doing that. The first 4 terms are :
$C(10,0)C(11,0)C(-4,77)-C(10,1)C(11,0)C(-4,67)-C(10,0)C(11,1)C(-4,66)+C(10,1)C(11,1)C(-4,56)+...$
where $C(n,r)$ is extended binomial coefficient and its defined as $C(n,r):=\begin{pmatrix} n \\ r \end{pmatrix}$ Can anyone help me with this? Or have other solution not involving generating function I would like to know too. Thank You :D

$\endgroup$

2 Answers 2

1
$\begingroup$

As shown by @HennoBrandsma we have just $4$ terms to calculate and you already essentially did the calculation.

Written in some detail we obtain \begin{align*} \color{blue}{[x^{100}]}&\color{blue}{\frac{x^{23}\left(1-x^{10}\right)\left(1-x^{11}\right)}{(1-x)^4}}\\ &=[x^{77}]\frac{1-x^{10}-x^{11}+x^{21}}{(1-x)^4}\tag{1}\\ &=\left([x^{77}]-[x^{67}]-[x^{66}]+[x^{56}]\right)\sum_{n=0}^\infty\binom{-4}{n}(-x)^{n}\tag{2}\\ &=-\binom{-4}{77}+\binom{-4}{67}-\binom{-4}{66}+\binom{-4}{56}\tag{3}\\ &=\binom{80}{77}-\binom{70}{67}-\binom{69}{66}+\binom{59}{56}\tag{4}\\ &=82\,160-54\,740-52\,394+32\,509\\ &\,\,\color{blue}{=7\ 535} \end{align*}

Comment:

  • In (1) we apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$.

  • In (2) we again apply the rule as in (1) and we use the binomial series expansion.

  • In (3) we select the $4$ coefficients accordingly.

  • In (4) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

$\endgroup$
1
$\begingroup$

$(1-x^{10})(1-x^{11})$ is just $(1-x^{10}-x^{11} + x^{21})$ and so only has $4$ terms to help form $x^{77}$, together with the last part.

$\frac{1}{(1-x)^4}$ has an infinite expansion $\sum_{k=0}^{\infty} \binom{k+3}{k}x^k$ (see here e.g.)

So we just get a sum of $4$ terms:

$$\binom{80}{77} - \binom{70}{67} - \binom{69}{66} + \binom{59}{56}$$

and I don't see how we'd get $56$ summands... Just the $4$ you already mentioned yourself.

$\endgroup$
2
  • $\begingroup$ I used this video reference youtube.com/watch?v=ZyUb5UxBA9Q The video said when you encounter with that, you must make all possible way of product of the binomial coefficient to reach x^n $\endgroup$
    – Aji Wibowo
    Oct 25, 2021 at 8:55
  • $\begingroup$ @AjiWibowo The only four ways are those that I enumerated. What are other ways according to you? $\endgroup$ Oct 25, 2021 at 9:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .