2
$\begingroup$

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

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

1 Answer 1

4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ "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 Rs in the permutation. right?" -yeah, exactly! Thank you for the answer, I will study it now. $\endgroup$ Aug 11 at 13:47
  • $\begingroup$ @Shorty12319 You're welcome. Happy to be of help. $\endgroup$
    – on1921379
    Aug 11 at 13:48

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.