How many ways to reach point?

221 Views Asked by At

You're sitting at coordinates (0,0) and have 3 options:

  1. Go up diagonally eg: (0,0) -> (1,1)
  2. Go straight 1 step eg: (0,0) -> (1,0)
  3. 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 ?

1

There are 1 best solutions below

0
On BEST ANSWER

These are the Motzkin numbers, OEIS A001006. Mathworld gives various expressions which might be considered closed forms.