In this exercise we will count the number of paths in the

Chapter 5, Problem 5.4.33

(choose chapter or problem)

In this exercise we will count the number of paths in the xy plane between the origin (0, 0) and point (m, n) 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 ,----,.----,---r----.---, such paths from (0, 0) to (5, 3) are illustrated here. (5, 3) (0, 0) '-----''------'-----'----'----' ,..-----,---r---r-----,---. (5, 3) (0, 0) '----'-----'-----'-----'-------' a) Show that each path ofthe type described can be represented by a bit string consisting of m Os and n 1 s, 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 ( m : n ) paths of the desired type.