Counting Problem?

Question

How many ways are there for a robot to travel in xyz space from the origin (0,0,0) to the point (4,3,5) by taking 12 steps, one at a time, where a step moves one unit in the positive x direction, one unit in the positive y direction, or one unit in the positive z direction? (NOTE: moving in the negative x,y, or z direction is prohibited, so that no backtracking is allowed). Explain your answer.

Answer 1

The robot has to travel a net total of 4 steps in the x direction, 3 in the y and 5 in the z. If the robot has to do this in exactly 12 steps, then it already goes without saying the robot can't backtrack.

Let "X" stand for a movement one unit in the positive x direction, "Y" for a movement in the positive y direction, and "Z" in the positive z direction. Then a series of moves is represented by an arrangement of four Xs, three Ys, and five Zs. For example, "YYXXYZZYZXXZZ" means "Go up 2 in the y direction, then up 2 in the x direction, the one in the y, two in the z," etc.

The question is now "How many ways can we rearrange these letters?" The formula for finding the rearrangement of N objects were a quanitity of A are all the same, and B are all alike, and C others are all alike, etc. are all the same is N! / (A! B! C!...). So this would be 12! / (4! 3! 5!) = 12! / (4! 3! 5!) = 27,720.

Answer 2

It has to step 4 in x direction, 3 in y direction and 5 in z direction. Now, how many possibilities are there to arrange 4x's, 3y's and 5z's?
xxxxyyyzzzz

4!*3!*5! = 4*3*2*1*3*2*1*5*4*3*2*1 = 17 280
There are 17280 different ways.

Answer 3

You need to make 4 moves forward (FFFF),
3 moves left (LLL) and five moves up (UUUUU).

There are
C(4,12) ways to place FFFF into12 available places,
C(3,8) to place LLL into remaining 8 places, and
C(5,5) to place UUUUU into 5 last places left.

Total is
N = C(4,12) * C(3,8) * C(5,5) =
12 ! / (4! 8!) * 8 ! /(3! 5!) * 5! /(5! 0!) =
12 ! / (4! 3! 5!) = 27720