Number of ways through a modified grid

Question

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.

Answer 1

One elementary fact is key to making these problems tractable:

If you pass through a given square, you must cross its northeast/southwest diagonal in exactly one place.

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.

Answer 2

I don't see a general closed form way for many deletions of cells. You can just build a Pascal's triangle starting from A. There is 1 way to reach A, then 1 way to reach each neighboring cell, and keep going. The missing cells have 0 in them, as you can't get there at all. Each non-zero cell has the sum of the one above and the one to the left.

Answer 3

When the number of deleted cells is small (you wouldn't want to use it for anything more than 3 or 4), you can use inclusion-exclusion, which reduces the problem to computing how many paths pass through a given subset of deleted cells. In the case of the bottom-left grid, this is particularly easy, since any path can pass through at most one of the deleted cells.

This approach is exponential in the number of deleted cells, but constant in the size of the grid. It would be interesting if it could be generalized to deleted rectangles, as then every one of your friend's examples would be tractable.