Number of paths in a square lattice with restrictions It is known that the number of paths with only rightward and upward moves in a square lattice from the lower left corner to the upper right corner is $\binom{a+b}{b}$, where $a$ is the height of the lattice and $b$ is the width. What is the number of paths in the lattice that do not contain four or more upward consecutive moves? ($a > 4$, $b > 4$).
 A: The problem is equivalent to finding the number of permutations of $a$ letters $U$ and $b$ letters $R$ such that there aren't four or more consecutive $U$s in the permutation. right?
If first, we put $R$s in a row, then there will be $b + 1$ places between the letters:
\begin{align*}
-\ R\ -\ R\ -\ R\ - \cdots -\ R\ -\ R\ -
\end{align*}
Now we must put $U$ letters in these places, such that each place contains $0$, $1$, $2$, or $3$ $U$s. So if we set $p_i$, $1 \leq i \leq b + 1$, to be the number of $U$s that are located in $i^{th}$ place, then we must count the number of solutions of the equation
\begin{align*}
p_1 + p_2 + \cdots + p_{b + 1} = a && \mbox{for} && 0 \leq p_i \leq 3,\ \ \ 1 \leq i \leq b + 1.
\end{align*}
We use generating functions. for each $i$, $1 \leq i \leq b + 1$, the generating polynomial of $p_i$ equals
\begin{align*}
x^0 + x^1 + x^2 + x^3 = \frac{1 - x^4}{1 - x}.
\end{align*}
So we must find the coefficient of $x^a$ (denoted by $[x^a]$) in
\begin{align*}
(1 + x + x^2 + x^3)^{b + 1} = \underbrace{\left(\frac{1 - x^4}{1 - x}\right)\left(\frac{1 - x^4}{1 - x}\right)\cdots \left(\frac{1 - x^4}{1 - x}\right)}_{b + 1\text{ times}} = \left(\frac{1 - x^4}{1 - x}\right)^{b + 1}.
\end{align*}
Therefore:
\begin{align*}
[x^a]\left(\frac{1 - x^4}{1 - x}\right)^{b + 1} = [x^a] \frac{(1 - x^4)^{b + 1}}{(1 - x)^{b + 1}} &= [x^a]\frac{\sum_{k = 0}^{b + 1}(-1)^k \binom{b + 1}{k}x^{4k}}{(1 - x)^{b + 1}}\\
&= \sum_{k = 0}^{b+1}[x^a]\frac{(-1)^k \binom{b + 1}{k}x^{4k}}{(1 - x)^{b + 1}}\\
&= \sum_{k = 0}^{b+1}[x^{a - 4k}]\frac{(-1)^k \binom{b + 1}{k}}{(1 - x)^{b + 1}}\\
&= \sum_{k = 0}^{b+1} (-1)^k \binom{b + 1}{k}\binom{b + a - 4k}{b}
\end{align*}
For calculation purposes, instead of this approach and finding the exact formula, you can write some code or use a program to evaluate the coefficient of $x^a$ in $(1 + x + x^2 + x^3)^{b+1}$.
