Consider a uniform lattice (grid) in a plane where the lattice points are indexed using the usual Cartesian coordinates. How many paths connect points (0,0) and (m, n) (where m, n > 0 are integers) if you can only move one unit to the right or one unit up at each step?
Answers
Answer:
main maths ka question hai
Step-by-step explanation:
We wish to count the paths that stay weakly below the line y=x (they can touch the line, but not go above)
1) Reflection Principle: First, we consider the total number of paths that exist from (0,0) to (n, n), which is (2n,n), since we must take exactly n up steps, each of which we denote by a u, and n right steps, each of which we denote by an r, and so this simply corresponds to the (2nn) ways we can rearrange a string with n us and n rs.
Next, we consider the paths that DO go above the line y=x (the bad paths). We note that for each such path, there exists a unique first up step that brings the path above the line (it could even be the first step). We draw a line of slope 1 passing through the end of this unique up step, and reflect the path up to that step about the line, giving a path from (−1,1) to (n ,n).
Now, we've shown that any bad path can be mapped onto a path from (−1,1) to (n, n). It is indeed true (but you should convince yourself of this) that any path from (−1,1) to (n ,n) can be mapped onto a bad path from from (0,0) to (n, n). Hence, there are the same number of bad paths from from (0,0) to (n ,n) as the number of all paths from (−1,1) to (n, n), which by the argument above is (2nn−1)=(2nn+1).
Hence the number of paths that stay below the line y=x is (after some manipulation):
(2nn)−(2nn−1)=1n+1(2nn)
