Factorial !!!!! Problem of choosing chairs

Suppose you have three friends Alice, Bob and Conor, who are wondering in how many different ways they can seat in a row of three chairs. You come along, and offer help.



For the sake of brevity, let calls these three friends A, B and C. Listing all the possible configurations:
A–B–C
A–C–B
B–A–C
B–C–A
C–A–B
C–B–A

Six different ways!

But what if you have 100 friends who are wondering the same thing? You need a better way to count rather than listing out all the possibilities.

First, notice that for the first chair you have three choices. You can put Alice, Bob or Conor in first chair. Let say you choose Alice. Now you only have Bob and Conor to give the second chair to. So 2 choices. Say, you give it to Bob. Then Conor has no choice but to take the last chair.

Let look at a more useful way to represent these possibilities, tree diagram!


As discussed above, at first branch we have 3 choices. For each choice in the first branch, we have 2 choices in the second branch. For each choice in the second branch, we have one choice in the third branch. We notice that this tree is perfectly symmetric. Three groups look exactly the same as far as counting is concerned. They all have one circle at the top, two at the middle and two at the bottom. The names and the positioning of the circles may be different, but that does not matter in counting. So we can just focus on the first group.

There are two possible ways for the first group, namely A–B–C and  A–C–B. 
The groups starting with Bob and Conor will each have 2 ways. So there are
2 (group Alice) + 2 (group Bob) + 2(group Conor) = 6 ways
$2+2+2$ also $= 2.3$ (you see, multiplication is nothing but addition in disguise)

Stop! Draw a tree diagram for four people and four chairs yourself before continue reading

By the same reasoning, if we have n people with n being any arbitrary positive integer number, we have:
$n.(n-1).(n-2).(n-3)…4.3.2.1$ ways to choose
We develop a special notation for this to avoid writing out this tedious multiplication.
$n! = n.(n-1)…3.2.1$ (yeah, that’s the exclamation mark)

This is called “n factorial”

Exercise:
http://euclid.colorado.edu/~ersh6364/2300/doc/factorials.pdf   (University of Colorado)