Until now, we have considered enumerations where the order of arrangement or selection matters. In the last exercise, one flight itinerary chosen could be New York, Virginia, Florida, Louisiana, Texas, Nevada, California.

Or it could be New York, Florida, Virginia, California, Texas, Louisiana, Nevada,

The first itinerary is a logical and efficient way of traveling as it requires a minimal change in direction. The second itinerary is an inefficient way to travel as the seemingly random selection of states requires many directional changes.

In this scenario, the order in which the states are visited is important as it will affect the efficiency of the trip. To plan the most efficient trip possible, we can hire a company that will plan the trip for us. All we have to do is provide any list of seven states and the company will offer the best route possible. The order of the list of states we provide is now irrelevant. How many ways can we compose a list of seven US states?

Initially, we had P(50, 7) different lists. This number is now reduced as any selection of seven states, ordered in any fashion, will produce the same outcome. Any list of seven states generated can be ordered in 7! different ways, all of which will return the same single list from the travel company. This scales P(50, 7) by 7!, which is:

$\frac{P(50,7)}{7!} = \frac{50!}{7!(50-7)!} = 99,884,400$

An enumeration of distinct objects where the order does not matter is called a combination; it is the permutation of k items out n possible choices scaled by k!. The formula for this is:

$C(n, k) = \frac{n!}{k!(n-k)!}$

This operation is also called “choose” because we say “out of n items, choose k“. We also denote it like this:

$C(n, k) = \binom{n}{k} =\frac{n!}{k!(n-k)!}$

Note the following identities:

$C(n,n) = 1$

$C(n,1) = n$