Discrete Mathematics
# Grid Walking

I was on vacation in England, and wanted to visit the Tower of London. The roads were laid out on a grid map, and and the castle was 4 blocks north and 5 blocks east. Unfortunately, there was some police activity near the hotel, and that intersection was blocked off so I could not go through it.

If I were to travel only north and east, how many routes did I have to get to the castle?

The diagram above shows a tiling of 7 squares with $A$ and $B$ denoting the initial point and destination point, respectively. The arrow signs indicate the direction that you're able to travel to (east, south, north-east). Find the total number of ways to reach point $B$ from point $A$.

**Bonus**: Generalize this for $n$ squares.

If Anna only moves right or up or down, and isn't allowed to retrace her steps, how many ways does she have to get to Ben?

There are 34 people in line to get into a theatre. Admission costs 50 cents. Of the 34 people, 28 of them have a 50-cent piece and 6 have a $1 bill. Suppose that the box office has an empty cash register, how many ways can the people line up so that change is available when needed?

Note: For this question, assume that the people are indistinguishable.