Kenneth Rosen Edition 7 Exercise 6.4 Question 33 (Page No. 422)

Question

In this exercise we will count the number of paths in the $xy$ plane between the origin $(0, 0)$ and point $(m, n),$ where $m$ and $n$ are nonnegative integers, such that each path is made up of a series of steps, where each step is a move one unit to the right or a move one unit upward. (No moves to the left or downward are allowed.) Two such paths from $(0, 0)$ to $(5, 3)$ are illustrated here.

• A. Show that each path of the type described can be represented by a bit string consisting of $m\: 0s$ and $n\: 1s,$ where a $0$ represents a move one unit to the right and a $1$ represents a move one unit upward.
• B. Conclude from part $(A)$ that there are $\binom{m + n}{n}$ paths of the desired type.

Answer 1

To reach a point (m,n) from (0,0) by following the given two conditions,

let's represent taking a right by value 0 and taking upward by value 1,

whatever path you take from (0,0) to (m,n) it always consists of m rights and n upwards.

in simple words, every path has m 0’s and n 1’s  [length of the bit string is m+n, so I can represent the path in the form of bit strings. ].

 

now let's count the number of paths that are possible:

as we need n 1’s in the bit string let's find out how many bit strings are possible with n 1’s in  n+m length bits strings.

which ( n+m C n ) = (n+m C m).