# Finding number of different paths

Consider a finite grid, suppose points a and b have positive x and y components ,and a has coordination of (x1,y1) and b has coordination of (x2,y2) and we want to go from a to b, how many possible paths exist if our movement is just going up and going right?

-

actually this is not HW question , this is part of my php programing for graphing calculator, – user1667315 Nov 4 '12 at 5:06
Thanks man, very helpful – user1667315 Nov 4 '12 at 5:08
is there a formula that i can plug in x y coordinate for a and b ? – user1667315 Nov 4 '12 at 5:12
If these answers are helpful to you, they may be helpful to others as well.  Please do not vandalize the question after it is answered. – Ross Millikan Nov 13 '12 at 19:05
rolled back edit to give answer context. – robjohn♦ Nov 13 '12 at 21:48

## 1 Answer

I assume you mean for this problem to deal only with integer coordinates and also $x_1 \leq x_2$ and $y_1 \leq y_2$ (otherwise, one cannot move only up and right).

Let $x = x_2 - x_1$ and $y = y_2 - y_1$ (the horizontal and vertical distance between the points). We can imagine a path from the two points as a binary string of with exactly $x$ 0's and exactly $y$ 1's, where we interpret a 0 as "move right" and a 1 as "move up". Notice the string has total length $x+y$.

To form such a string, we need only pick the locations for the 0's and then fill the remaining locations with 1's. That is, we choose exactly $x$ locations (without order) out of the total $x+y$ locations, which can be done in $\binom{x+y}{x}$ ways.

-

Thank you, I already wrote a program to calculate answer using brute force but I could’d find formula from results , thanks man – user1667315 Nov 4 '12 at 5:28
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 10, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9393410682678223, "perplexity_flag": "middle"}