In how many different ways can I get from A to B?

Question

I can only use horizontal and vertical arrows, like in the picture, and I must get from $A$ to $B$ using only $4$ horizontal arrows and $3$ vertical arrows. (One arrow counts as the line connecting only two dots)

My answer is $4! \cdot 3!$, however I don't know if I am right

Answer 1

One of the key observations with directed graph problems in this fashion is that it will always take the same number of moves in either of the two directions, regardless of the path.

For example:

$$\text{up, up, up, right, right, right, right}$$

gets you there, as does

$$\text{right, right, up, up, up, right, right}$$ $$\text{up, right, right, up, up, right, right}$$ $$\text{right, right, up, right, up, up, right}$$

or, really, any permutation of these sequences.

This actually allows us to reframe this in terms of a different common combinatorics problem that might be more familiar to you. Let $U$ represent up movements and $R$ movements to the right. Then we know that any permutation of the letters $UUURRRR$ defines a valid path if we do the actions in order sequentially.

So we ask: in this "word" $UUURRRR$ (three $U$'s, four $R$'s), how many distinct arrangements are there?

This is a problem in which the multinomial theorem applies. To see it more directly:

• We know we have $7$ letters total. So if they were all distinct, then we would have $7!$ permutations, right?
• But some are identical! For any permutation of the $U$'s in a given word, the word is still the same: that is, for each of our $7!$ permutations, we have duds. That number of duds is equal to the number of arrangements of $U$'s we can have, which is $3!$. We will need to divide by $3!$ to handle that.
• Similarly, we will need to divide by $4!$ because of the $R$'s.

Thus, we get our answer,

$$\frac{7!}{3!\cdot 4!} \;\;\; \text{sometimes represented by} \;\;\; \binom{7}{3,4}$$

Answer 2

You can convert each allowable path into a "word" of $H$s and $V$s, for horizontal and vertical steps respectively. Your example corresponds to the word $VHVHHVH$. The word must consist of three $V$s and four $H$s. How many ways are there to choose three letters in a seven-letter word to be $V$s?