Given integers p,q> 1, a (p,q)-path is a path from (0,0) to (p,q) on the plane...

 

Transcribed Image Text:

Given integers p,q> 1, a (p,q)-path is a path from (0,0) to (p,q) on the plane that uses only right steps of length one and up steps of length one. (a) Here is an example of a (2,3)-path: Up, Right, Up, Up, Right, as illustrated in the figure below. 2 List all (2,3)-paths (either as a word sequence of steps or as pictures). How many did you find? (b) List all elements of [5]. How many elements are there? (c) Drawing inspiration from your findings in (a) and (b), complete the statement of the following theorem, and give a combinatorial proof for it. The ????? part should be a binomial coefficient. Theorem. For all integers p, q1, there are ????? (p,q)-paths. Given integers p,q> 1, a (p,q)-path is a path from (0,0) to (p,q) on the plane that uses only right steps of length one and up steps of length one. (a) Here is an example of a (2,3)-path: Up, Right, Up, Up, Right, as illustrated in the figure below. 2 List all (2,3)-paths (either as a word sequence of steps or as pictures). How many did you find? (b) List all elements of [5]. How many elements are there? (c) Drawing inspiration from your findings in (a) and (b), complete the statement of the following theorem, and give a combinatorial proof for it. The ????? part should be a binomial coefficient. Theorem. For all integers p, q1, there are ????? (p,q)-paths.