I have to find out the number of paths of length $n$ starting from the origin with movements

  • $R : (x,y) \rightarrow (x+1,y)$

  • $L : (x,y) \rightarrow (x-1,y)$

  • $U : (x,y) \rightarrow (x,y+1).$

Also step $R$ is not followed by $L$ and vice-versa.

In a book that I was following has done it in the following way way.

I have some problem understanding it.

  1. First why $a_{n-1} = b_n$ ?
  2. Secondly why should I only adjoin step $R$ in a path of length $(n-1)$ which ends with $R$ ? I may adjoin $U$ to the path to get a path of length $n$.
  3. Also the recurrence relation is not clear to me.

Any help will be very helpful.( If any other way of understanding is possible please let me know) Thank you.

  • 1
    $\begingroup$ For your first point of confusion, note that before you move at all you can move left right or up with $n$ steps to go. But if you take the first action to go up, then you're on a new point which can now (for the second step) go left right or up, but with only $n-1$ steps left to go. So going up on your first step makes no difference to your current situation, only that you have $1$ less steps left to proceed with $\endgroup$ – Jihoon Kang Sep 23 '17 at 5:43
  • $\begingroup$ Then it will be same case if I start with $R$ or $L$ ? $\endgroup$ – hiren_garai Sep 23 '17 at 5:45
  • $\begingroup$ no, because if you take L first, say, then on your next point you can only go U or L again, since according to the rules R is now not allowed. So you're in a different situation $\endgroup$ – Jihoon Kang Sep 23 '17 at 5:46
  • $\begingroup$ Oh ! I get it . What about other confusions ? $\endgroup$ – hiren_garai Sep 23 '17 at 5:47

To count $a_n$, the number of paths of length $n$, the author is splitting the set of such paths into the disjoint union of three subsets:

  1. The paths ending in U
  2. The paths ending in LL, RR or UL
  3. The paths ending in UR

Note that the latter two cases combine to count all of the paths ending in L or R, as LR and RL are not permitted.

@Jihoon Kang addressed your first concern. For the remaining two, both points are addressed by counting the three subsets above individually.

First, any path ending in U may be preceded by any legal path of length $n-1$, so there are $a_{n-1}$ paths in the first subset.

Second, given any path of length $n-1$, there is a unique way to complete it such that the path ends with one of LL, RR, or UL. You are correct that it is legal to follow a U with an R, but that would create a path that is not in the second subset, so it is not counted here. The number of paths in this subset is $a_{n-1}$.

Finally, a path ending in UR can be obtained by adding UR to any path of length $n-2$, so there are $a_{n-2}$ paths in this subset.

Since the set of paths of length $n$ is the disjoint union of these three subsets, we get the recurrence $a_n = 2a_{n-1} + a_{n-2}$ by simply summing the sizes of the three subsets.

  • $\begingroup$ Completely ok now !. Thanks @JeremyDover. $\endgroup$ – hiren_garai Sep 23 '17 at 16:58

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.