5. (a) Find a formula for the number of lattice paths from (0,0) to (2n, 0)...

  

Transcribed Image Text:

5. (a) Find a formula for the number of lattice paths from (0,0) to (2n, 0) using steps of the form (1, 1) or (1,1) such that the path is never below the x-axis (but it is allowed to touch the x-axis, and of course it does so at the beginning and at the end). So we are allowed to move a distance of 2 in the northeast or southeast direction in each step. For example, when n = 2, there are 2 paths: they are (1, 1)(1, 1)(1, 1)(1,1) and (1,1)(1, 1)(1, 1)(1, 1) when listed by the moves at each step. (6pts) (b) Calculate S(100, 99) and s(100, 1) where S(p, k) is the Stirling number of the second kind and s(p, k) is the Stirling number of the first kind. (4pts) 5. (a) Find a formula for the number of lattice paths from (0,0) to (2n, 0) using steps of the form (1, 1) or (1,1) such that the path is never below the x-axis (but it is allowed to touch the x-axis, and of course it does so at the beginning and at the end). So we are allowed to move a distance of 2 in the northeast or southeast direction in each step. For example, when n = 2, there are 2 paths: they are (1, 1)(1, 1)(1, 1)(1,1) and (1,1)(1, 1)(1, 1)(1, 1) when listed by the moves at each step. (6pts) (b) Calculate S(100, 99) and s(100, 1) where S(p, k) is the Stirling number of the second kind and s(p, k) is the Stirling number of the first kind. (4pts)