# Travelling from city A to B, then B to A.

I found a permutation problem like "show that there is a ... number of ways of..." which is given below. I tried to show that, but I got a different answer. I will describe how I did, after stating the problem.

Here is the problem:

There are $$5$$ roads connecting the cities $$A$$ and $$B$$. $$3$$ men want to travel from $$A$$ to $$B$$, then again $$B$$ to $$A$$. If the journeys $$AB$$ and $$BA$$ must be not on the same road and no two men can use the same road when traveling from one city to another city, show that there are $$1440$$ ways they can travel.

First, I found there are $$5\times4\times3=60$$ ways they can travel from $$A$$ to $$B$$. Similarly, without any special case, there are $$60$$ ways of traveling from $$B$$ to $$A$$. Considering one permutation of traveling from $$A$$ to $$B$$, there are $$12+9+7=28$$ different ways to travel from $$B$$ to $$A$$, when at least one man is using the same way. Because the number of different ways to return when

1. the first man reuses a road is $$4\times3=12$$,
2. the second man reuses but the first man does not is $$12-3=9$$,
3. the third man reuses but the first and second do not is $$12-3-2=7$$.

Therefore, the total number of ways they can travel is $$60\times(60-28)=1920$$, which is not the result given.

What was the mistake? Please, explain the correct method. Sorry for the faults in explaining.

Thank you.

• The mistake is in the source. Your solution is correct. Nov 18, 2022 at 10:20

Here is another method of solving the problem:

As you observed, there are $$5 \cdot 4 \cdot 3$$ ways for the three people to take three different routes from $$A$$ to $$B$$.

Since there are six one-way trips and oly five available roads, at least one person must travel from $$B$$ to $$A$$ by a route another person took to get from $$A$$ to $$B$$.

Exactly one person travels from $$B$$ to $$A$$ by a route another person took to get from $$A$$ to $$B$$: There are three ways to select the person who travels from $$B$$ to $$A$$ by a route another person took to travel from $$A$$ from $$B$$, two ways for that person to select one of those two routes, and $$2!$$ ways for the remaining two people to travel from $$B$$ to $$A$$ by the two routes nobody took from $$A$$ to $$B$$. Hence, there are $$3 \cdot 2 \cdot 2!$$ ways for the three people to return from $$B$$ to $$A$$ for each of the $$5 \cdot 4 \cdot 3$$ ways they could have traveled from $$A$$ to $$B$$.

Exactly two people travel from $$B$$ to $$A$$ by a route another person took to get from $$A$$ to $$B$$: There are $$\binom{3}{2}$$ ways to select the two people who travel from $$B$$ to $$A$$ by a route another person took from $$A$$ to $$B$$. They can either both select to return by the route the other took to get from $$A$$ to $$B$$ or exactly one of them can do so, with the other selecting the route the third person took to get there, giving $$1 + 2 = 3$$ choices. The third person must return using one of the two routes nobody used to travel from $$A$$ to $$B$$. Hence, there are $$\binom{3}{2} \cdot (1 + 2) \cdot 2$$ ways for the three people to travel from $$B$$ to $$A$$ for each of the $$5 \cdot 4 \cdot 3$$ ways they could have traveled from $$A$$ to $$B$$.

All three people travel from $$B$$ to $$A$$ by a route another person took from $$A$$ to $$B$$: There are $$2$$ ways this can occur for each of the $$5 \cdot 4 \cdot 3$$ ways they could have traveled from $$A$$ to $$B$$, namely the oldest person returns by the route the next oldest person took from $$A$$ to $$B$$, the second oldest person returns by the route the youngest person took from $$A$$ to $$B$$, and the youngest person returns by the route the oldest person took from $$A$$ to $$B$$, or the oldest person returns by the route the youngest person took from $$A$$ to $$B$$, the next oldest person returns by the route the oldest person took from $$A$$ to $$B$$, and the youngest person returns by the route the second oldest person took from $$A$$ to $$B$$.

Total: Since these cases are mutually exclusive and exhaustive, the number of ways three people can travel from $$A$$ to $$B$$ and return from $$B$$ to $$A$$ on the five roads connecting the cities if they each take different routes from $$B$$ to $$A$$ than they took from $$A$$ to $$B$$ and no two of them take the same route in the same direction is $$5 \cdot 4 \cdot 3\left[3 \cdot 2 \cdot 2! + \binom{3}{2} \cdot (1 + 2) \cdot 2 + 2\right] = 1920$$