Coefficient of generating function (hard) How to find the coefficient of $x^{46}$ in $\dfrac{1}{1 - x^3 -x^4 -x^{20}}$ without software like Maple?
I tried everything... :(
 A: $$\frac{1}{1-x^3-x^4-x^{20}}=\sum_{k\geq 0}(x^3+x^4+x^{20})^k $$
and the coefficient of $x^{46}$ in $(x^3+x^4+x^{20})^k$ is the cardinality of the $k$-uples with coordinates in $\{3,4,20\}$ such that the sum of the coordinates equals $46$. We either use two $20s$ and two $3$s (which can be arranged in six ways), a single $20$ and a representation of $46-20=26$ as a sum of $3s$ and $4s$, or just a representation of $46$ with $3$s and $4$s only. In the last cases we need an even number of $3$s since both $26$ and $46$ are even, but at least two $3s$ since neither $26$ or $46$ is a multiple of $4$. The count can be performed by hand now:
$$(3,3,20,20)$$
$$(3,3,4,4,4,4,4,20)$$
$$(3,3,3,3,3,3,4,4,20)$$
$$(3,3,4,4,4,4,4,4,4,4,4,4)$$
$$(3,3,3,3,3,3,4,4,4,4,4,4,4)$$
$$(3,3,3,3,3,3,3,3,3,3,4,4,4,4)$$
$$(3,3,3,3,3,3,3,3,3,3,3,3,3,3,4)$$
together with their anagrams give all the chances and
$$ [x^{46}]\frac{1}{1-x^3-x^4-x^{20}}=\color{red}{3224}.$$
A: If we think about a formal power series and set $y=x^3+x^4+x^{20}$ and use $[x^q](f(x))$ as the notation for coefficient of $x^q$ in $f(x)$ then
\begin{align}
&[x^{46}]((1-y)^{-1})=[x^{46}]\left(\sum_{i=0}^\infty y^i\right)\\
= & [x^{46}]\left(\sum_{i=0}^{15} y^i\right)\\
= & [x^{46}]\left(\sum_{i=0}^{15}x^{3i}(1+x+x^{17})^i\right)\\
= & \sum_{i=0}^{15}[x^{46-3i}]((1+x+x^{17})^i)\\
= & \sum_{i=0}^{15}\sum_{j=0}^i\binom{i}{j}[x^{46-3i}]\left((x+x^{17})^{j}\right)\\
= &\sum_{i=0}^{15}\sum_{j=0}^i\binom{i}{j}[x^{46-3i-j}]((1+x^{16})^j)\\
=& \sum_{i=0}^{15}\sum_{j=0}^i\binom{i}{j}\sum_{k=0}^j\binom{j}{k}[x^{46-3i-j}](x^{16k})
\end{align}
The non-zero terms would appear only when 
\begin{align}
&46-3i-j=0,16,32, \quad 0\le j\le i\\
\implies&3i+j = 46,30,14\\
\implies& (i,j)\in\{(15,1),(14,4),(13,7),(12,10)\}\cup\{(10,0),(9,3),(8,6)\}\cup\{(4,2)\}
\end{align}
And as $k\le j$, the set of $S$ of $(i,j,k)$ with non-zero contribution looks like
$$
\{(15,1,0),(14,4,0),(13,7,0),(12,10,0)\}\cup\{(9,3,1),(8,6,1)\}\cup\{(4,2,2)\}
$$
So the required coefficient is
\begin{align}
&\sum_{(i,j,k)\in S}\binom{i}{j}\binom{j}{k}\\
=& \sum_{(i,j,0)\in S}\binom{i}{j}+ \sum_{(i,j,1)\in S}i\binom{i-1}{j-1}+ \binom{4}{2}\binom{2}{2}\\
=&\binom{15}{1}+\binom{14}{4}+\binom{13}{7}+\binom{12}{10}+9\binom{8}{2}+8\binom{7}{5}+\binom{4}{2}\\
=& 3224
\end{align}
A: Let
$$f(x) = \frac{1}{1-x^3-x^4-x^{20}}$$
and define $\{a_n\}$ by
$$f(x) = \sum_{n=0}^{\infty}a_n x^n$$
Then from 
$$f(x) -x^3 f(x) - x^4 f(x) -x^{20} f(x) = 1$$
we have 
$$a_n -a_{n-3}-a_{n-4}-a_{n-20} = 0$$
for $n >0$, with $a_0 = 1$.  Equivalently,
$$a_n =a_{n-3}+a_{n-4}+a_{n-20} $$
for $n > 0$.  (We consider $a_n = 0$ for $n < 0$).  
With this recurrence relation we can grind out as many values of $a_n$ as we like.  In particular,  $a_{46} = 3224$.  
It would be a tedious computation by hand, but it's easy to automate in a spreadsheet.
