# Street Combinatorics - 6 by 7 grid

You go to school in a building located six blocks east and seven blocks north of your home. So, in walking to school each day you go thirteen blocks. All streets in a rectangular pattern are available to you for walking. In how many different paths can you go from home to school, walking only thirteen blocks?

I want to say that the answer can be found knowing that there are $6!$ ways east and $7!$ ways north. Then, the answer would be $6!+ 7!$ .

I feel like this is way too simple of a solution to be correct.

• I like the attempt. To see the flaw in the logic, suppose the school were located 6 blocks due east. By your reasoning, there would be 6! ways east, instead of only one way. – Teepeemm Sep 15 at 1:58
• Of the thirteen total blocks you must walk, you simply choose the six you'll walk east on (numbers 1, 3, 4, 8, 9, 12, for instance). That determines your route. – BallpointBen Sep 15 at 6:14

Consider this:

You have to go north 7 times and go east 6 times. How can you slip in the 6 "east moves" into 7 "north moves"?

The answer is then $\binom{6+7}6=\binom{13}6=1716$

• I think you messed up the combination notation... – Rushabh Mehta Sep 15 at 0:20
• @RushabhMehta I did. Thank you for point it out. – abc... Sep 15 at 0:21

Let's assume the only moves you are allowed are moving north and moving east. Denote a move north as n and a move east as e. Hence, we need to make 7 n moves and 6 e moves, and we seek to compute the number of arrangements of these moves.

This is equivalent to the problem

nnnnnnneeeeee


How many distinct rearrangements are there of the above letters. Through some combinatorics, we find the answer is $${13\choose6}=\frac{13!}{6!7!}=\color{red}{1716}$$

• This would be a utilization of the multinomial theorem, correct? – Ludwigthestud Sep 17 at 19:55
• @Ludwigthestud That's one way of thinking about it. – Rushabh Mehta Sep 17 at 19:57