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

• Is the binom expression equal to $\frac{(a+b)!}{a!b!}?$ Aug 11 at 11:21
• Actually i don't know this notation that's why Aug 11 at 11:22
• @abcdefu:::::: sure. Aug 11 at 11:23

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