# How many possible paths

Consider the point $$\vec{p} = (3,48,4,5,8) \in\mathbb{R}^{5}$$, how many distinct paths are there from zero to $$\vec{p}$$ if the only movements allowed are unit movements in the directions $$\vec{e}_{1}, \vec{e}_{2}, \vec{e}_{3}, \vec{e}_{4}, \vec{e}_{5}$$?

Would this mean that we have $$\frac{(3+48+4+5+8)!}{3!48!4!5!8!} = \frac{68!}{3!48!4!5!8!}$$ distinct paths?

• if you can only move "right" along an axis that distnguishes left from right and you can only move "up" along an axis that distinguishes up from down, then the answer is there are no paths from the origin that allow you to reach $p(3,48,4,5,8)$ becuase the point $p$ is defined in a coordinate system with $5$ axes. By analogy, how many paths can you take to reach the point $p(3,4)$ when you start at the origin and can only perform unit movements "to the right"? Oct 24, 2019 at 20:51

Assuming "up and right" means we are only allowed to move in the direction of $$\vec{e}_1, \vec{e}_2, \vec{e}_3, \vec{e}_4$$ and $$\vec{e}_5$$, not the linear combinations of them and not scaled versions of them, I think this is a simple combinatorics question. Equivalent problem would be "Given five letters A, B, C, D and E, how many 68 letters words can you make such that there are 3 As, 48 Bs, 4 Cs, 5 Ds and 8 Es?"

Your answer $$\frac{(3+48+4+5+8)!}{3!48!4!5!8!} = \frac{68!}{3!48!4!5!8!}$$ is exactly correct.

We have to 'line up' 68 moves, so that would suggest $$68!$$ possibilities, but since you have $$3$$ $$e_1$$-moves, they are indistinguishable in this line-up, so the $$68!$$ overcounts by a factor of $$3!$$, mneaning that you need to divide $$68!$$ by $$3!$$. But the same is true for the other dimensions.

• Sorry, but what you are saying is that the answer is correct, but isn't because of the overcounting? How would I eliminate this overcounting by a factor of 3! ? Oct 24, 2019 at 21:18
• @AndrewRyan The overcounting is corected by dividing the $68!$ by $3!$. And likewise, you have to dive by $48!$, $4!$, etc. So yes, what you end up with is excactly correct. I just tried to explain how that formula makes sense. Oct 24, 2019 at 21:42
• Thank you it makes sense now. Oct 24, 2019 at 21:49
• @AndrewRyan You're welcome! :) Oct 24, 2019 at 21:54

You need to pick $$3+48+4+5+8=68$$ moves, so you want to know how many ways you can order those. However, there are five move types, corresponding to the directions, and the order in which the moves of a single type are picked does not count. Can you take it from there?

• No, it's the number of ways to sort the 68 moves divided by the number of ways you can sort the individual move types, just like you proposed in the edit. Oct 24, 2019 at 21:13