Suppose that we begin at (0, 0) and are allowed to take two types of steps - steps one unit up and steps one unit to the right. For example, a legal path might be (0, 0) → (1, 0) → (2, 0) → (2, 1) → (3, 1).
Now, suppose that you are given a number k. Is there an efficient algorithm to list of all points (x, y) with exactly k paths to them? For example, given the number 6, we would list (1, 5), (5, 1) and (2, 2), since these points have exactly six paths to them.
Thanks!