Animals 6:   N u m b e r   o f   S t a t e s

How many states are there? It seems that even for a small number of vertices of the underlying graph, we have a large number of states. This suspicion is confirmed as follows:

In the animal example:

• There are 6 locations for the fox.
• Having placed the fox, there remain 5 possible locations for the kangaroo.
• Having placed both fox and kangaroo, there remain 4 possible locations for the donkey.
• And so on.

So overall there are 6 · 5 · 4 · 3 ·2 = 720 states in our animal example.

Such a number n · (n-1) · (n-2) · ... · 3 · 2 is abbreviated as n! and pronounced "n factorial"

In the same way, in the 15 puzzle there are 15! = 1,307,674,368,000 states. More than 1 trillion states.