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:
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:
This operation is also called “choose” because we say “out of n items, choose k“. We also denote it like this:
Note the following identities:
You are playing a trick-taking card game in which you will be dealt 13 cards. How many ways could you be dealt 13 unsorted cards from a 52-card hand? Set the variable
unsorted_thirteen to your answer.
and this hand:
are two different kinds of possible hands! In this situation, the order in which you are given the cards is relevant.
Given any 13 cards in how many ways can you arrange them? Set the
thirteen_cards variable to your answer.
Assuming you were going to sort the cards when you receive them, how many different 13-card hands can you have? Set the
sorted_thirteen variable to your answer.