You're sitting at coordinates (0,0) and have 3 options:
- Go up diagonally eg:
(0,0) -> (1,1) - Go straight 1 step eg:
(0,0) -> (1,0) - Go down diagonally eg:
(2,2) -> (3,1)
You want to reach (p,0) and you're not allowed to go under 0 (Eg, you can only walk on >= 0 coordinates) and you can only go up to a point h, in height.
How many ways can you reach the point (p, 0) from (0,0) given to constraints mentioned above ?
These are the Motzkin numbers, OEIS A001006. Mathworld gives various expressions which might be considered closed forms.