5# book, Ch 30, Ques 22

[jayedgar]

Man is returning home on ew/ns grid of 4x3 squares, respectively. He can go only N and E. how many paths?

The answer says total!/repeats! = 7!/(3! * 4!) = 35.

I completely do not understand. Can anyone explain?

Thanks much,

Jay

[tommywallach]

Okay. First thing's first: you have to understand the basic rules of combinatorics, and that dividing allows you to remove duplicates. I'm not going to do a step one-step ten lesson on combinatorics here.

To get from end of the square to the other, you eventually have to go

UP UP UP UP RIGHT RIGHT RIGHT

You can do this in ANY order though:

RIGHT RIGHT RIGHT UP UP UP UP
UP RIGHT UP RIGHT UP RIGHT UP
etc.

If we just think of these as letters, you have UUUURRR

The question is "How many ways can UUUURRR be ordered?" But remember, 7! would be ALL the ways to arrange those letters. But if two of the U's switched places, that would be counted as a new order, when we know that's actually the same order. (If that doesn't make sense, think of each of those U's as if it has a little subscript on it: U1 U2 U3 U4--in this universe U1 U2 is the same as U2 U1, they both represent moving up twice in a row--but 7! would count those differently).

At that point, we simply divide by the duplicates 3! because we have three R's and 4! because we have three U's.

Hope that helps!

-t