Massachusetts Institute of Technology Lecture 16 6.042J/18.062J: Mathematics for Computer Science November 2, 2000 Professors Nancy Lynch and Srinivas Devadas

Permutations and Combinations

Topics for today:

• Division rule

• Combinations

• Signal transmission

Reading: Rosen 4.3

We have seen a variety of techniques for counting elements in a finite set: Setting up bijections, the Sum Rule, Inclusion-Exclusion, the Product Rule, tree diagrams, formula for number of permutations. In this lecture we introduce a new counting tool called the Division Rule and use it to find a formula for the number of combinations of elements from a set. One common pitfall in counting problems is mixing up combinations with permutations; try to keep track of which is which!

1 r-Permutations

Brief review from last time.

Definition An r-permutation of a set is an ordering of r distinct items from the set.

Definition P (n, r) denotes the number of r-permutations of an n-element set.

P (n, r) = n(n − 1) … (n − r + 1) = \frac{n!}{(n − r)!}

Example 1.1 How many ways can 5 students be chosen from a class of 180 to be given 5 fabulous (different) prizes, say $1000, $500, $250, $100, $50? Answer: P (180, 5), which is 180 × 179 × 178 × 177 × 176.

Example 1.2 How many injective functions are there from A to B, if |A| = n and |B| = m (assume n ≤ m)? Answer: Order A arbitrarily. First element maps somewhere in B. Second element maps somewhere else (injective), etc. Number of possibilities is P (m, n) = m(m − 1)(m − 2) … (m − n + 1) = \frac{m!}{(m−n)!}. Essentially picking a sequence of n of the m elements of B.

2 The Division Rule

The division rule is a common way to ignore “unimportant” differences when you are counting things. You can count distinct objects, and then use the division rule to “merge” the ones that are not significantly different.

2.1 Statement and proof of the division rule

We will state the Division Rule twice, once informally and then again with more precise notation.

Theorem 2.1 (Division Rule) If B is a finite set and f : A ↦ B maps precisely k items of A to every item of B, then A has k times as many items as B.

For example, suppose A is a set of students, B is a set of tutorials, and f defines the assignment of students to tutorials. If 12 students are assigned to every tutorial, then the Division Rule says that there are 12 times as many students as tutorials.

The following two definitions permit a more precise statement of the Division Rule.

Definition If f : A ↦ B is a function, then f^{−1}(b) = {a ∈ A | f(a) = b}.

That is, f^{−1}(b) is the set of items in A that are mapped to the item b ∈ B. In the preceding example, f^{−1}(b) is the set of students assigned to recitation b.

This notation can be confusing, since f^{−1} normally denotes the inverse of the function f. With our definition, however, f^{−1}(b) can be a set, not just a single value. For example, if f assigns no items in A to some element b ∈ B, then f^{−1}(b) is the empty set. In the special case where f is a bijection, f^{−1}(b) is always a single value, and so f^{−1} by our definition is just the ordinary inverse of f.

Definition A function f : A ↦ B is k-to-1 if for all b ∈ B, |f^{−1}(b)| = k.

For example, if f assigns exactly 12 students to each recitation, then f is 12-to-1. Assuming k is non-zero, a k-to-1 function is always a surjection; every element of the range is mapped to by k > 0 elements of the domain.

We can now restate the Division Rule more precisely:

Theorem (Division Rule, restatement) If B is a finite set and f : A ↦ B is k-to-1, then |A| = k|B|.

Proof. Since B is finite, we can let n = |B| and let B = {b_{1}, b_{2}, …, b_{n}}. Then we have:

A = f^{−1}(b_{1}) ∪ f^{−1}(b_{2}) ∪ … ∪ f^{−1}(b_{n})

Equality holds because each side is contained in the other. The right side is contained in the left side because every set f^{−1}(b_{i}) is contained in A by the definition of f^{−1}(b_{i}). The left side is contained in the right, since every item in A maps to some b_{i}, and therefore is contained in the set f^{−1}(b_{i}).

Furthermore, all of the sets f^{−1}(b_{i}) are disjoint. The proof is by contradiction. Assume for the purpose of contradiction that a ∈ f^{−1}(b_{i}) and a ∈ f^{−1}(b_{j}) for some i ≠ j. The first inclusion implies f(a) = b_{i}, but the second inclusion implies that f(a) = b_{j}. This is a contradiction since f(a) denotes a unique item.

Since the sets f^{−1}(b_{i}) are disjoint, we can compute the cardinality of their union with the Sum Rule. Note that each set f^{−1}(b_{i}) has size k, since f is k-to-1.

|A| = |f^{−1}(b_{1})| + |f^{−1}(b_{2})| + … + |f^{−1}(b_{n})|
= \underbrace{k + k + … + k}_{n=|B| terms}
= k|B|

2.2 Example: Seating at a Round Table

In how many ways can King Arthur seat n knights at his round table? Two seatings are considered equivalent if one can be obtained from the other by rotation. For example, if Arthur has only four knights, then there are six possibilities as shown in Figure 1. Hereafter, we denote a seating arrangement in text by listing knights in square brackets in clockwise order, starting at an arbitrary point. For example, [1234] and [4123] are equivalent.

As a sign that we should bring in the division rule, the question points out that certain distinct seatings are equivalent, so should only be counted once—that is, we want to count equivalence classes instead of individual objects. The division rule is a good way to do this.

Claim 2.2 Arthur can seat n knights at his round table in (n − 1)! ways.

In particular, the claim says that for n = 4 knights there are (4 − 1)! = 3! = 6 orderings, which is consistent with the example in Figure 1.

Proof. The proof uses the Division Rule. Let A be the set of orderings of n knights in a line. Let B be the set of orderings of n knights in a ring. Define f : A ↦ B by f((x_{1}, x_{2}, …, x_{n})) = [x_{1}x_{2} … x_{n}].

The function f is n-to-1. In particular:

f^{−1}([x_{1}x_{2} … x_{n}]) = { (x_{1}, x_{2}, x_{3}, …, x_{n}),
(x_{n}, x_{1}, x_{2}, …, x_{n−1})
(x_{n−1}, x_{n}, x_{1}, …, x_{n−2}),
…
(x_{2}, x_{3}, x_{4}, …, x_{1})}

Figure 1: These are the 6 different ways that King Arthur can seat 4 knights at his round table. Two seatings differing only by rotation are considered equivalent. We denote a seating arrangement in text by listing knights in square brackets in clockwise order, starting at an arbitrary point. For example, the seatings in the top row can be denoted [1234], [2413], and [3421].

There are n tuples in the list of tuples, because x_{1} can appears in n different places in a tuple. By the Division Rule, |A| = n|B|. This gives:

|B| = \frac{|A|}{n}
= \frac{n!}{n}
= (n − 1)!

The second equality holds, because the number of orderings of n items in a line is n!, as we showed previously.

2.3 Example: Students and prizes

How many sets of 5 students can be chosen from an 180-student class, to win 5 fabulous $1000 prizes? (This time, all the prizes are the same.)

Let A = number of 5-permutations of the set of students. Number is P (180, 5) = 180 × 179 × 178 × 177 × 176. But that’s not really what we want—order of the 5 students doesn’t matter. Let B = number of 5-student sets. This is what we want. Map f : A ⇒ B by ignoring the order. Claim that f is 5! to 1, in other words, 120 to 1. This is based on the number of ways that 5 students could be lined up. So, by Division Theorem, |B| = \frac{|A|}{120} = \frac{180×179×178×177×176}{120}.

3 Combinations

Generalizing the example that we just did: The Division Rule can be used to count the number of r-combinations of a set.

3.1 Definition: r-Combinations of a Set

Definition An r-combination of a set is a subset of size r.

For example, for the set {A, B, C}, we have the following three 2-combinations:

{A, B} {A, C} {B, C}

Understanding the distinction between r-combinations and r-permutations is important. The rcombinations of a set are different from r-permutations in that order does not matter. For example, the above set {A, B, C} has six 2-permutations:

\begin{matrix}(A, B) & (A, C) & (B, C) \\ (B, A) & (C, A) & (C, B) \end{matrix}

The previous example was talking about the 5-combinations of the set of students in the class.

3.2 The number of r-combinations

The number of r-combinations of an n-element set comes up in many problems. The quantity is important enough to merit two notations. The first is C(n, r); this is analogous to the notation P (n, r) from before for the number of r permutations of an n-element set. The second notation is \binom{n}{r}, read “n choose r”. The values \binom{n}{r} or C(n, r) are often called binomial coefficients because of their prominent role in the Binomial Theorem, which we will cover shortly.

The following theorem gives a closed form for \binom{n}{r}. This theorem is used all the time; remember it!

Theorem 3.1

\binom{n}{r} = \frac{n!}{(n − r)! r!}

The theorem says, for example, that the number of 2-combinations of the three element set \{A, B, C\} is \frac{3!}{(3−2)!2!} = 3 as we saw above.

Also, for example, the number of 5-combinations of the 180 element set of students is \frac{180!}{175!5!}.

Proof. The proof uses the Division Rule. Let X be a set with n elements. Let A be the set of r-permutations of X, and let B be the set of r-combinations of X. Our goal is to compute |B|. To this end, let f : A ↦ B be the function mapping r-permutations to r-combinations that is defined by:

f( \underbrace{(x_{1}, x_{2}, …, x_{r})}_{order matters (permutation)} ) = \underbrace{\{x_{1}, x_{2}, …, x_{r}\}}_{order does not matter (combination)}

The function f is r!-to-1. In particular:

f^{−1}({x_{1}, x_{2}, …, x_{r}}) = { (x_{1}, x_{2}, x_{3}, x_{4}, …, x_{r}),
(x_{2}, x_{1}, x_{3}, x_{4}, …, x_{r}),
… all r! permutations … }

By the Division Rule, |A| = r!|B|. Now we can compute the number of r-combinations of an n-element set, |B|, as follows:

|B| = \frac{|A|}{r!}
= \frac{P (n, r)}{r!}
= \frac{n!}{(n − r)! r!}

Binomial coefficients are important enough that some special values of \binom{n}{r} are worth

remembering:

\binom{n}{1} = \frac{n!}{(n − 1)! 1!} = n There are n 1-element subsets of an n-set.
\binom{n}{n − 1} = \frac{n!}{1! (n − 1)!} = n There are n (n − 1)-element subsets of an n-set. That’s because there are n possible choices for which element to leave out.
\binom{n}{0} = \frac{n!}{n! 0!} = 1 There is a single 0-element subset of an n-set.
\binom{n}{n} = \frac{n!}{0! n!} = 1 There is a single n-element subset of an n-set.

Recall that 0! is defined to be 1, not zero.

Theorem 3.2 For all n ≥ 1, 0 ≤ r ≤ n, \binom{n}{r} = \binom{n}{n−r}.

Says that the number of ways to choose an r-element set is the same as the number of ways to choose the n − r elements to exclude.

Proof. Just do the calculations: \binom{n}{r} = \frac{n!}{(n−r)!r!} = \binom{n}{n−r}.

3.3 Examples: Poker hands

In the poker game Five-Card Draw, each player is dealt a hand consisting of 5 cards from a deck of 52 cards. Each card in the deck has a suit (clubs ♣, hearts ♡, diamonds ♢, or spades ♠) and a value (A = 1, 2, …, 10, J, Q, K). The order in which cards are dealt does not matter. We will count various types of hands in Five-Card Draw to show how to use the formula for r-combinations given in Theorem 3.1.

It may not be clear why we want to count the number of types of hands. The number of hands of a particular type tells us how “likely” we are to encounter such a hand in a “random” deal of the cards. Hands that are less likely are ranked higher than those that are more likely, and so will win over those. Knowing the likelihood (or the number) of various hands can help us to figure out how to bet on the game.

We will see more about such issues when we study probability, later in the term.

All Five-Card Hands

How many different hands are possible in Five-Card Draw? A hand is just a 5-card subset of the 52-card deck. Therefore, the possible hands in Five-Card Draw are exactly the 5-combinations of a 52-element set. By Theorem 3.1, there are \binom{52}{5} = \frac{52!}{47! 5!} = 2, 598, 960 possible hands.

Confusion between combinations and permutations is a common source of error in counting problems. For example, one might erroneously count the number of 5-card hands as follows. There are 52 choices for the first card, 51 choice for the second card given the first, …, and 48 choices for the fifth card given the first four. This totals 52 · 51 · 50 · 49 · 48 possible hands. The problem with this way of counting is that a hand is counted once for every ordering of the five cards; that is, each hand is counted 5! = 120 times. We accidentally counted r-permutations instead of r-combinations! To get the number of 5-combinations, we would have to divide by 120.

Hands with Four-of-a-Kind

How many hands are there with four-of-a-kind? For example, 9♠ 4♢ 9♣ 9♡ 9♢ has a four-of-a-kind, because there are four 9’s.

First we must choose one value to appear in all four suits from the set of 13 possible values (the follows the “tree diagram” approach to exploring distinct cases). There are 13 choices of this value, and if we pick one we can’t have any others (that would require 8 cards). So the choice of value gives 13 disjoint cases to count. After this choice, we have to choose one more card from the remaining set of 48. This can be done in \binom{48}{1} = 48 ways. In total, there are 13 · 48 = 624 hands with four-of-a-kind. The situation is illustrated by the tree diagram in Figure 2.

Figure 2: This (incomplete) tree diagram counts the number of hands with four-of-a-kind. There are 13 choices for the value appearing in all four suits. The fifth card in the hand can be any of the 48 cards remaining in the deck. This gives a total of 13 · 48 = 624 possible hands.

Here is a way to interpret the result that uses probability. If all \binom{52}{5} hands are equally likely, then the probability that we are dealt a four-of-a-kind is 624/\binom{52}{5} = 1/4165. In other words, we can only expect to get four-of-a-kind only once in every 4165 games of Five-Card Draw! (This is just a passing observation; we will talk about probability “for real” in a few weeks.)

Mistakes are easy to make in counting problems. It is a good idea to check a result by counting the same thing in another way. For example, we could also count the number of hands with a four-of-a-kind as follows. First, there are 52 ways to choose the “extra” card. Given this, there are 12 ways to choose the value that appears in all four suits. (We cannot choose the value of the first card.) The possibilities are illustrated by the tree diagram in Figure 3. By this method, we find that there are 52 · 12 = 624 four-of-a-kind hands. This is consistent with our first answer (which is a good thing).

Figure 3: This tree diagram shows another way to count the number of hands with a four-of-a-kind. There are 52 choices for the “extra” card and then 12 choices for the value appearing in all four suits. This gives 52 · 12 = 624 hands, the same answer as before.

Hands with a Full House

A full house is a hand with both a three-of-a-kind and a two-of-a-kind. For example, the hand 7♠ 7♢ J♣ J♡ J♢ is a full house because there are three jacks and two sevens. How many full house hands are there?

We can choose the value that appears three times in 13 ways. Then we can pick any three of the four cards in the deck with this value; this can be done in \binom{4}{3} = 4 ways. There are then 12 remaining choices for the value that appears two times. We can pick any two of the four cards with this value; this can be done in \binom{4}{2} = 6 ways.

The total number of full house hands is therefore 13 · 4 · 12 · 6 = 3744. This is 6 times greater than the number of hands with a four-of-a-kind. Since a four-of-a-kind is rarer, it is worth more in poker!

Hands with Two Pairs

How many hands are there with two pairs, but no three- or four-of-a-kind?

Incorrect count. There are 13 choices for the value of the cards in the first pair. There are then \binom{4}{2} = 6 ways to choose two of the four cards in the deck that have this value. Next, there are 12 choices for the value of the cards in the second pair, and \binom{4}{2} = 6 ways to choose two of the four cards with this value. Finally, the fifth card can be any one of the 48 cards remaining in the deck. Altogether there are 13 · 6 · 12 · 6 · 48 hand with just two pairs.

There are actually two bugs in this argument. The first is that the fifth card cannot be any one of the 48 remaining cards; in particular, it cannot have the same value as a card already selected. (Otherwise, there would be three of a kind.) This rules out 4 of the 48 cards, leaving only 44 choices for the fifth card.

The second bug is that every hand has been counted twice! For example, a pair of kings and a pairs of queens is counted once with the kings as the first pair and a second time with the queens as the first pair. The references in the argument to a “first pair” and a “second pair” signal danger; these terms imply an ordering that is not part of the problem. To fix the second bug, we can apply the Division Rule. There is a 2-to-1 mapping from the set of hands we counted to the set of hands with two pairs. Therefore, the set of hands with two pairs is half as large as our initial count:

hands with two pairs = \frac{13 · 6 · 12 · 6 · 44}{2}
= 123, 552

Why did this factor of 2 arise in counting pairs, but not in counting full houses? The reason is that pairs are interchangeable, but a pair and a triple are not. For example, a pair of 2’s and a pair of 9’s is the same as a pair of 9’s and a pair of 2’s. On the other hand, a pair of 2’s and a triple of 9’s is different from a pair of 9’s and a triple of 2’s!

To check our result, we can count the number of hands with two pairs in a completely different way. The number of ways to choose the values for the two pairs is \binom{13}{2}. We can choose suits for each pair in \binom{4}{2} = 6 ways, and we can choose the remaining card in 44 ways as before. This gives:

\binom{13}{2} · 6 · 6 · 44 = 123, 552

This is the same answer as before. Two pairs turn out to be 33 times more likely than a full house; as one would expect, a full house beats two pairs in poker!

Three of a kind, 2 different

There are \binom{13}{1} ways to choose the rank for the three-of-a-kind, and once that is chosen, there are \binom{4}{3} ways to choose the three cards. Once we have the three-of-a-kind, there are \binom{12}{2} ways to choose the two ranks for the other two cards. And then for each of these ranks, there are \binom{4}{1} ways to choose the single card of that rank. The total is:

\binom{13}{1}\binom{4}{3}\binom{12}{2}\binom{4}{1}\binom{4}{1} = 54, 912.

Since this is fewer than the hands with two pairs, this is ranked higher.

1 pair, others all different

There are \binom{13}{1} ways to choose the rank for the pair, and then \binom{4}{2} ways to choose the two cards of that rank. Then there are \binom{12}{3} ways to choose the ranks of the remaining three cards, and for each of these ranks, \binom{4}{1} ways to choose the single card of that rank. The total is:

\binom{13}{1}\binom{4}{2}\binom{12}{3}\binom{4}{1}\binom{4}{1}\binom{4}{1} = 1, 098, 240

4 different ranks

We have analyzed all the actual poker hands based on the numbers of cards of different ranks (4-1, 3-2, 3-1-1, 2-2-1, 2-1-1-1).

How many hands have all 5 cards of different ranks? That’s the total number of hands minus the sum of the numbers of hands of these five kinds, or

2, 598, 960 − 1, 098, 240 − 123, 552 − 54, 912 − 3, 744 − 624 = 1, 317, 888

Counted another way: There are 52 choices for the first card, 48 choices for the second card given the first, 44 choices for the third given the first two, etc. After each card, the number of remaining choices drops by four, since we cannot subsequently pick the card just taken or any of the other three cards with the same value. This gives 52 · 48 · 44 · 40 · 36 hands with no pair. Is this answer right?

The references to “first card”, “second card”, … are a warning signal that we may be inadvertently counting an ordered set. To be sure, we can check how many times a particular hand is counted. Consider the hand A♡ K♠ Q♣ J♣ 10♡. We could have obtained this hand by drawing cards in the order listed, but we could also have drawn them in another order. In fact, we counted this hand once for every possible ordering of the five cards, and in fact, every hand is counted 5! = 120 times! We can correct our initial answer by applying the Division Rule. This gives:

hands with no pairs = \frac{52 · 48 · 44 · 40 · 36}{120}
= 1, 317, 888

And still another way: There is another way to count the hands with no pairs that avoids this confusion. Since there are no pairs, no two cards have the same value. This means that we could first choose 5 distinct values from the set of 13 possibilities. Then we could choose one of the four suits for each of the five cards. This gives:

hands with no pairs = \binom{13}{5} · 4^{5}
= \frac{13 · 12 · 11 · 10 · 9}{5 · 4 · 3 · 2 · 1} · 4^{5}
= 1, 317, 888

This is the same answer as before. Notice that the number of hands with no pairs is more than half of all the hands. This means that in more than half our games of Five-Card Draw, we will not have even one pair!

Other poker hands

Because they are so common, hands with no repeated ranks should be the least valuable hands. However, among these are several that have special value: Straight: Consecutive ranks (no wraparound)

Flush: All same suit Straight flush: Both Royal flush: A,K,Q,J,10 of one suit

Number of flush hands: \binom{4}{1} ways to choose the suit, then \binom{13}{5} ways to choose the 5 cards. This gives \binom{4}{1}\binom{13}{5} = 5188.

Number of royal flush hands: 4

Number of straight flush hands: \binom{4}{1} ways to choose the suit, then 9 ways to choose the starting rank of the straight.

Number of straight hands: 9 starting ranks, then for each of the five ranks, \binom{4}{1} ways to choose the card. That gives 9 × 4^{5} = 9216.

Hands with Every Suit

How many hands contain one card of every suit? Such a hand must contain two cards from one suit and one card from each of the other three suits. Again, we can count in two ways.

First count. Pick one card from each suit. This can be done in 13^{4} ways. Then pick any one of the remaining 48 cards. This gives a total of 13^{4} · 48 hands. However, we have overcounted by two, since the two cards with the same suit could be picked in either order. Accounting for this, there are \frac{13^{4}·48}{2} = 685, 464 hands.

Second count First, we can pick the suit that contains two cards in four ways. Then we can pick values for these two cards in \binom{13}{2} ways. Finally, we can pick a card from each of the other three suits in 13 ways. This gives:

hands with all suits = 4\binom{13}{2}\binom{13}{1}^{3}
= 4 · \frac{13 · 12}{2} · 13 · 13 · 13
= 685, 464

More than a quarter of all Five-Card Draw hands contain all suits.

Reminders

To make sure that you get the right answer when counting:

1. Look at a sample 5-card hand (or a sample of whatever you are counting) and make sure that it is covered once and only once in your count.

2. Try counting by two different ways and check that you get the same answer.

For example, when we first counted the number of hands with no pairs, we discovered that we had massively overcounted; a sample hand was actually covered 120 times by our count! We corrected this answer by applying the Division Rule, and we counted the same thing again in a different way as a double-check.

4 The Magic Trick

Counting has many applications in computer science. For example, we have proved upper and lower bounds on the run time of algorithms, proved that some functions are not computable, etc. Counting also has applications in information theory. Here is a fun one!

There is a magician and an assistant. The assistant goes into the audience with a deck of 52 cards while the magician looks away. Five audience members are asked to select one card each from the deck. The assistant then gathers up the five cards and announces four of them to the magician. The magician thinks for a time and then correctly names the secret, fifth card!

4.1 How the Trick Works

The assistant has somehow communicated the secret card to the magician just by naming the other four cards. In particular, the assistant has two ways to communicate. First, he can announce the four cards in any order. The number of orderings of four cards is 4! = 24, so this alone is insufficient to identify which of the remaining 48 cards is the secret one. Second, the assistant can choose which four of the five cards to reveal. The amount of information that can be conveyed this way is harder to pin down. The assistant has \binom{5}{4} = 5 ways to choose the four cards revealed, but the magician can not determine which of these five possibilities the assistant selected, since he does not know the secret card! Nevertheless, these two forms of communication allow the assistant to covertly reveal the secret card to the magician.

Here is an overview of how the trick works. The secret card has the same suit as the first card announced. Furthermore, the value of the secret card is offset from the value of the first card announced by between 1 and 6. See Figure 4. This offset is communicated by the order of the last three cards.

Figure 4: The 13 possible card values can be ordered in a cycle. For any two distinct values, one is offset between 1 and 6 clockwise steps from the other. In this diagram, 3 is offset five steps from J. In the card trick, the value of the secret card is offset between 1 and 6 steps from the first card announced. This offset is communicated by the order of the last three cards named by the assistant.

Here are the details. The audience selects five cards and there are only 4 suits in the deck. Therefore, by the Pigeonhole Principle, the assistant can always pick out two cards with the same suit. One of these will become the secret card, and the other will be the first card that he announces.

Here is how he decides which is which. Note that for any two card numbers, one is at most six clockwise steps away from the other in Figure 4. For example, if the card numbers are 2 and Q, then 2 is three clockwise steps away from Q. The assistant ensures that the value of the secret card is offset between 1 and 6 clockwise steps from the first card he announces.

The offset is communicated by the order that the assistant announces the last three cards. The magician and assistant agree in advance on an order for all 52 cards. For example, they might use:

A ♣, 2 ♣, …, K ♣, A ♢, …, K ♢, A ♡, …, K ♡, A ♠, …, K ♠

With this order, one of the last three cards announced is the smallest (S), one is largest (L), and the other is medium (M). The offset is encoded by the order of these three:

\begin{matrix}SML = 1 & SLM = 2 & MSL = 3 \\ MLS = 4 & LSM = 5 & LMS = 6 \end{matrix}

For example, suppose that the audience selects 3♡ 8♢ A♠ J♡ 6♢. The assistant picks out two cards with the same suit, say 3♡ and J♡. The 3♡ is five clockwise steps from J♡ in Figure 4. So the assistant makes 3♡ the secret card, announces J♡ first, and then encodes the number 5 by the order in which he announces the last three cards: A♠ 6♢ 8♢ = LSM = 5.

4.2 Same Trick with 4 Cards?

Could the same magic trick work with just 4 cards? That is, if the audience picks four cards, and the assistant reveals three, then can the magician determine the fourth card? The answer turns out to be “no”. The proof relies on the Pigeonhole Principle.

Theorem 4.1 The magic trick is not possible with 4 cards.

Proof. The audience can select any 4-combination of cards; let A be the set of all such 4combinations. The assistant can announce any 3-permutation of cards; let B be the set of all such 3-permutations. The formulas for r-combinations and r-permutations give the following sizes for A and B:

|A| = C(n, r)
= \frac{52!}{48! 4!}
= 270, 725
|B| = P (n, r)
= \frac{52!}{49!}
= 132, 600

The assistant sees a 4-combination of cards selected by the audience and must announce a 3permutation to the magician. Let f : A ↦ B be the function that the assistant uses in mapping one to the other. Since |A| > |B|, the Pigeonhole Principle implies that f maps at least two 4combinations to the same 3-permutation. That is, there are two different sets of four cards that the audience can pick for which the assistant says exactly the same thing to the magician.

For these two sets of four cards, three cards must be the same (since the assistant announces the same three cards in both cases) and one card must be different (since the two sets are different). For example, these might be the two sets of four cards for which the assistant says exactly the same thing to the magician:

3♡ 8♢ A♠ J♡
3♡ 8♢ A♠ K♢

In this case, the assistant announces 3♡ 8♢ A♠ in some order. The magician is now stuck; he can not determine whether the remaining card is J♡ or K♢.

There are many variants of the magic trick. For example, if the audience picks 8 cards, then revealing 6 to the magician is enough to let him determine the other two. This sort of subtle transmission of information is important in the security business where one wants to prevent information from leaking out in undetected ways. This is actually a whole field of study, but this trick is all we’ll see in 6.042.