# Permutation/Combination of x,y and z moves

First of all, I am not quite sure but I think the problem asks for a permutation/combination of 13 elements over the {x, y, z} set.

Here is the problem: How many ways are there for a spaceship to travel in a 3-D space from the origin (0,0,0) to the point (2,4,7) by taking 13 steps, one at a time, where a step moves one unit in the positive x, y or z direction? Moving in the negative x, y or z direction is prohibited.

Thank you very much in advance!

-
Where does 12 come from? – Henry Apr 9 '11 at 12:00
Hint: How many $x$-steps? $y$-steps? $z$-steps? How many ways of permuting these steps? – Henry Apr 9 '11 at 12:00
12 was a typo. Fixed now. Excuse me, I don't understand what you mean with your second question. Could you, please, be more specific? – User3419 Apr 10 '11 at 12:36

There are thirteen available steps, 2 of which must change $x$, $4$ of which must change $y$ and $7$ of which must change $z$. There are $\binom{13}{2}$ ways to choose the $x$-changing steps, $\binom{11}{4}$ ways to choose the y steps from the remaining steps, and then you're done since the remaining steps are automatically z-changing steps. So the final anaswer is $\binom{13}{2}\binom{11}{4}$.
Now I get it. I tried to approach it analogically starting with y, then z, and leaving x for the end. I got the same answer $\binom{13}{4} \binom{9}{7} = 25740$. Thank you! – User3419 Apr 9 '11 at 12:05
I find it easier with the multinomial $\dfrac{13!}{2!\, 4!\,7!} =25740$ – Henry Apr 9 '11 at 12:22
A good way of understanding the multinomial, incidentally: start by labeling all your steps uniquely as $x_a$, $x_b$, $y_a$, $y_b$, etc; then there are $13$! permutations of these labeled objects. Now 'unlabel' the two $x$ steps, since they can't be distinguished from each other; this removes a factor of $2!$ from the result. Similarly, unlabeling the four $y$ steps removes a factor of $4!$ from the result, and unlabeling the seven $z$ steps removes a factor of $7!$ from the result, leaving you with that multinomial. – Steven Stadnicki Apr 10 '11 at 16:11