factorials vs nCr: Does order matter in this probability problem?

The figure above shows 5 walkways, R,S,T,U, and V, leading to and from a momument. Carlos will take one walkway to the mounment and will leave by a different walkway. From how many different pairs of these walkways can Carlos choose? For example, the pair starting with Walkway S and ending with Walkway V is different from the pair starting with walkway V and ending with Walkway S.

I used factorials to solve this problem instead of nCr because the problem says that order matters but I find that factorials doesn't make sense... i.e. 4x3x2x1. How to solve?

• This problem is actually small enough to list all the possibilities. For instance ST could denote enter by S, leave by T. – paw88789 Aug 11 '14 at 17:45
• @paw88789 That would be a very inefficient way of solving this – Mathmo123 Aug 11 '14 at 17:46
• @Mathmo123: True, but sometimes listing out the possibilities sheds light on why we choose one formula over another (e.g., when the user is unsure whether to use factorials or combinations or...) – paw88789 Aug 11 '14 at 17:53
• "What formula shall I use?" is often the wrong question, in SAT. or in anything but an end-of-section problem. Ask what's happenin'. We can enter in $5$ ways and for each such way we can leave in $4$ ways. – André Nicolas Aug 11 '14 at 18:25

Hint: How many walkways can he enter with? Once he's entered a walkway, how many can he exit through?

• He can enter through any of R,S,T,U,V - i.e. $5$. Once he's chosen one of them to enter through, how many can he exit through? Can you see how to use this? – Mathmo123 Aug 11 '14 at 17:46
• he can exit through 4. I meant he can enter through 5 not 4 – user159778 Aug 11 '14 at 17:49
• Exactly. So he has 5 choices for entering and 4 for exiting... so how many combinations in total? – Mathmo123 Aug 11 '14 at 17:51
• 20. but should i solve for 20 by using 5x4 or 5nCr1 x 4nCr1? – user159778 Aug 11 '14 at 17:53
• I don't think nCr is right in this case as order matters. – user159778 Aug 11 '14 at 17:53

If you're stuck between nCr and factorials, this probably means you're missing the tool in between: permutation counting. nPr is n! / (n-r)!, and is the number of ways to select r things from a pile of n total things without replacement, where order matters.

http://en.wikipedia.org/wiki/Permutations#k-permutations_of_n

I'll give a hint. The key difference between permutations and combinations is in your statement here:

For example, the pair starting with Walkway S and ending with Walkway V is different from the pair starting with walkway V and ending with Walkway S.

I'll give another hint. You can check whether you're right or not by writing down all of the possible paths.

I'll give a third hint. There are twenty paths.

• i think order matters for the problem so use factorials – user159778 Aug 11 '14 at 17:50
• The key difference isn't really "using factorials" or "not using factorials" because both permutations and combinations are computed with factorials. It's whether or not the order matters. What you want is the number of permutations of two things, drawn from a set of five things, which is $_5 P _2$. You want permutations because order does matter. If order did not matter, then you'd want the number of combinations or two things, drawn from a set of five thinge (which is $_5 C _2$). – John Aug 11 '14 at 17:55