I was in math class listening to my teacher blather on about solids of revolution when my friend passed me a note with a puzzle on it. It looked something like this:
How many different ways can you get from A to B moving only right or down? (In his barely legible hand of course)
I reasoned that since the ways to get to each vertex is additive in a manner similar to that of Pascal's triangle the ways through an $n\times n$ square grid could be given by $${2n} \choose n$$
So I passed the note with the answer back to him, but that was a short lived victory, as a second note was passed to me with several modified grids such as:
And I drew a blank as how to formulate these nicely, so I resorted to adding by hand, which was rather boring.
Is there a way to nicely formulate the number of ways you can get from A to B if any number of vertices are removed, or would it be easier to simply do it by hand write (or write an algorithm)?
I'll be happy if I can get a formula for any constraint, such as the missing vertices being symmetrical about the diagonal, there being only a certain number, etc. At the moment the only case I can apply combinations to is the where the bottom half of the grid is gone, in which case the number of ways can be determined by the catalan numbers $$C_n={1 \over {1+n}}{{2n} \choose n}$$
Please note I am only a sophomore in high school. I know basic calculus, algebra, number theory, and combinatorics; if it all possible phrase your answer in something I might be able to comprehend.
Best Answer
One elementary fact is key to making these problems tractable:
So, consider the upper-left problem. The number of allowed paths is equal to the total number of paths (on the original grid), minus the number of paths that pass through either of the two deleted squares. The number of paths passing through either deleted square is equal to the number passing through the first deleted square, plus the number passing through the second deleted square, minus the number passing through both (this is the "inclusion-exclusion" rule). Finally, the paths passing through the upper-left deleted square are those going through $(5,6)$ or $(6,5)$, and the paths passing through the lower-right deleted square are those passing through $(8,8)$. Let $N_{i,j}=N_{j,i}={{i+j}\choose{i}}$ be the number of paths that go $i$ squares to the right and $j$ squares down. Putting these together, $$ N_{UL}=N_{12,12}-\left(N_{5,6}N_{7,6} + N_{6,5}N_{6,7}+N_{8,8}N_{4,4}-(N_{5,6}N_{3,2}N_{4,4} + N_{6,5}N_{2,3}N_{4,4})\right) \\ = N_{12,12} - 2N_{5,6}N_{7,6} - N_{8,8}N_{4,4} + 2N_{5,6}N_{2,3}N_{4,4}. $$ The upper-right problem is similar, but simpler. The lower-left and lower-right problems do not involve inclusion-exclusion at all: for instance, the lower-right problem just requires you to count the paths going through one of $(8,4)$, $(7,5)$, $(6,6)$, $(5,7)$, and $(4,8)$, or $$ N_{LR}=N_{12,12} - 2N_{8,4}^2 -2N_{7,5}^2 - N_{6,6}^2 $$ after using symmetry.