2
$\begingroup$

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!

  • 0
    you may refer http://stackoverflow.com/questions/58306/graph-algorithm-to-find-all-connections-between-two-arbitrary-vertices2012-01-29
  • 0
    Do you want the *number* of paths, or all possible total paths?2012-01-29
  • 0
    I edited your question because by your example seems you looking for pair of points.2012-01-29
  • 0
    If you start at (0,0), I get that you have 15 possible paths to (4,2), and 7 possible paths to (6,1) or have I misunderstood the question...?2012-01-29
  • 2
    This shouldnt be allowed ! its Facebook Hacker Cup Q1) Checkpoint... and the contest in not over yet !2012-01-29
  • 0
    This boils down to finding all $x,y$ such that the binomial coefficient $(x+y)$-choose-$x$ equals $k$. That question (or a close relative) has come up on this site two or three times in the last day or so. See http://math.stackexchange.com/questions/103506/what-is-the-maximum-point-for-which-number-of-way-to-reach-is-given and the links there to other questions.2012-01-30

2 Answers 2