Quoted By:
the key is to solve the subproblem: suppose you have an x*y rectangular array, what are the number of paths between the bottom left and top right corner if you can only move right and up?
since any path between the start and end contains the same number of up and right movements, just permuted, we have a combinatorics problem. consider a movement as being encoded by a string of Rs for right and Us for up. Their are always x - 1 R symbols and y - 1 U symbols for x + y - 2 total symbols for each path. Thus, there are (x + y - 2)! permutations of distinguishable symbols. but this overcounts the number of paths because it assumes different Us and Rs can be distinguished, which isn't the case. thus we need to divide by the total number of possible permutations for each type of symbol. thus the total number of paths is N = (x + y - 2)!/ (x -1)! (y - 1)!
now go back to the original problem. notice that there are two squares that every path must pass through in the bottle neck. factor the problem into counting how many paths there are from A to the bottleneck squares, and from the bottleneck squares to B, then combine the results.
2 * ((5 + 6 - 2)!/((5-1)! (6-1)!))^2 = 31752
penis
