Correspondences and Choice Trees

Gamblers and other people playing card or dice games depend on more than luck to succeed. They need to know the odds—how likely various combinations of cards or dice throws are likely to come up in different situations. Determining these probabilities brings us into the realm of sets, counting, and choice trees.

Disjoint Sets

Two sets and are disjoint if their intersection , where is the empty set. In other words, the two sets have no elements in common.

If and are two disjoint, finite sets, then the size of is the sum of the size of and the size of :

We can show by induction that, if are disjoint, finite sets, then the size of the union of these sets is the sum of the sizes of the individual sets.

Suppose that I roll a white die and a black die. The total number of different outcomes is 36. We can let be the set of all outcomes where the dice show different values and be the set of outcomes where the two dice agree. We know that .

What is the size of ? We can work out directly. For each number on one die, there are five cases in which the number is different on the other die: . Alternatively, we can take advantage of the fact that there are six cases in which both dice show the same number (doubles): . So, .

So, we can take advantage of disjoint sets and use different methods to get the same answer. In effect, we're counting in different ways to obtain an answer.

This time, let be the set of all outcomes where the black die shows a smaller number than the white die. What is the size of ? To find directly, let us say that represents the set of outcomes where the black die says and the white die says something larger. We simply sum all of these cases.

Alternatively, we can let be the set of all outcomes where the black die shows a larger number than the white die, we already know that . Because and are the same size, it is clear by symmetry that . Therefore, .

However, what do we really mean when we say that a result is true "by symmetry?" Is this a legitimate argument? We can pin down the idea of symmetry by exhibiting a correspondence; that is, we show how one set fits with another.

Let's put each outcome in in correspondence with an outcome in by swapping the color of the dice. So, for any outcome in , we can swap the color and get an outcome in . Each outcome in pairs up with exactly one outcome in , with none left over. Thus, .

Correspondences

We can make the notion of correspondences more precise by introducing a technical vocabulary to express such relationships.

Let be a function from a set to a set . The function is described as injective (1 to 1) if and only if , . In other words, every element in goes to something different in . So, has to be at least as big as : .

The function is surjective (onto) if and only if , such that . In other words, every element of is taken care of. In this case, must be at least as big as : .

We can also have the case of a bijection, in which each element of one set is paired up with precisely one and only one element of the other set. The correspondence principle holds that, if a bijection exists between two finite sets, then they have the same size. This is one of the most important mathematical ideas of all time and much used in computer science.

Let's apply these ideas to the question: How many n-bit sequences are there? We can try to count these sequences by representing them as a different but corresponding set that is clearly countable. In effect, we look for a change in representation to simplify our counting problem by changing the underlying set being counted. Note that, when using correspondences, we don't even need to know actual numbers to use the notions of "equal," "more," or "less."

Here's a correspondence between n-bit sequences and natural numbers.

n-bit sequence	natural number
000000	0
000001	1
000010	2
000011	3
. . .	. . .
1 . . . 11111

Altogether, there must be sequences.

Example

has many subsets: Note that the empty set is a valid set.

Question: How many subsets can be formed from the elements of a 5-element set?

Here's one way to establish a correspondence that will help us count the number of subsets. We express each subset as a 5-bit sequence, using a "take it or leave it" code, in which 1 means "take it" and 0 means "leave it." For example, the subset would correspond to the sequence 01101.

Based on this correspondence, we can say that there are 32 subsets.

We can generalize this result to the set , which corresponds to the binary string . The correspondence is given by the function .

We can see that is injective. Any two distinct binary sequences and have a position at which they differ. Hence, is not equal to because they disagree on element .

The function is also surjective. Let be a subset of . Let if is in ; otherwise. So, .

Hence, the number of subsets of an n-element set is .

We can refine the notion of a 1 to 1 correspondence further. Recall that, if we let be a function from a set to a set , then is a 1 to 1 correspondence if and only if exactly one such that . It is a k to 1 correspondence if and only if exactly such that .

The latter formulation is useful for counting if the correspondence is consistently mapped. It would be like the task of counting the number of horses in a barn by counting the number of hoofs, then dividing by 4 (assuming that all horses have four hoofs each) to get the number of horses.

Indeed, if a finite set has a k to 1 correspondence to the finite set , then the number of items in would equal the number of items in divided by k.

Choice Trees

A restaurant has a menu with 5 appetizers, 6 entrées, 3 salads, and 7 desserts. Altogether, there are 5 + 6 + 3 + 7 = 21 items on the menu, and there are 5 * 6 * 3 * 7 = 630 ways to choose a complete meal. If a customer decides to omit some of the courses, then there are 6 * 7 * 4 * 8 = 1344 ways to order a meal.

Suppose that Hobson's restaurant has only 1 appetizer, 1 entrée, 1 salad, and 1 dessert. If a customer decides not to have some of the courses, then there are 16 ways to order a meal—the number of subsets (as we showed earlier) of the 4-element set {appetizer, entrée, salad, dessert}.

We can also represent choices like those described above as trees (see chapter 3). Recall that a choice tree is a rooted, directed tree with an object called a "choice" associated with each edge and a label on each leaf. A choice tree provides a "choice tree representation" of a set S, if

1. Each leaf label is in S, and each element of S is some leaf label.
2. No two leaf labels are the same.

Example

We can construct a choice tree for -bit sequences and label each leaf with the object constructed by the choices along the path to the leaf. There is then one leaf for each sequence.

There are two choices for first bit, times two choices for second bit, times two choices for third bit . . . times two choices for the bit. The number of leaves is .

We have a recurring picture of a tree of possibilities with labeled paths. Each choice has a meaning, and a sequence of choices defines an object.

In a choice tree representation, it is easy to count the leaves to determine the number of possible choices. Given a tree of depth , where each node at depth has children, the number of leaves of is given by . This is known as the leaf-counting lemma. Note that, at each level, there is a consistent number of branches.

We can now combine the correspondence principle with the leaf-counting lemma to make a powerful counting rule for choice tree representations. This is known as the product rule.

• Product rule: IF has a choice tree representation with possibilities for the first choice, for the second, and so on, THEN there are objects in .

Proof

The leaves of the choice tree are in 1 to 1 onto correspondence with the elements of .

Here is an alternative way of looking at the product rule. Suppose that all objects of a type can be constructed by a sequence of choices with possibilities for the first choice, for the second, and so on. IF (1) each sequence of choices constructs an object of type AND (2) No two different sequences create the same object THEN there are objects of type .

Picking Cards

We can now apply the ideas of correspondence and choice tree to enumerating possibilities for a standard deck of playing cards.

A standard deck contains 52 different cards. How many different orderings of these cards are there?

In this instance, the object that we are making via a sequence of choices is an ordering of the deck. We can construct such an ordering by a sequence of 52 choices: 52 possible choices for the first card, 51 possible choices for the second card, 50 possible choices for the third card, . . . , and 1 possible choice for the 52nd card. By the product rule, represents the number of orderings, or arrangements, of 52 cards.

Recall that a permutation or arrangement of objects is an ordering of the objects. The number of permutations of distinct objects is (see chapter 1).

The English alphabet contains 26 letters. If we allow repeated letters, how many sequences of 7 letters are there? We can picture this situation as a tree with 26 choices at each step. We get possible sequences.

How many sequences of 7 letters contain at least two of the same letter? To get the answer, we can subtract from the total the number of instances in which no letters are the same (26 possibilities for the first letter, 25 for the second letter, and so on): .

This example illustrates the notion that it is sometimes easier to count the number of objects with property by counting the number of objects that do not have property . Counting sets can be viewed as arising out of logic, so we can formalize the process of counting a set by counting its opposite in terms of strings and Boolean functions.

To find the number of ways of ordering, permuting, or arranging out of objects, we have choices for first place, choices for second place, and so on. We have choices.

Example

In a race involving 10 horses, how many orderings of the top three finishers are there?

So far, we have been considering arrangements in which order matters. We can also have situations in which the order doesn't matter.

For example, from a deck of 52 cards, we can form 52 * 51 = 2652 ordered pairs. To find the number of unordered pairs, we must divide the number of ordered pairs by the overcount. Each unordered pair is listed twice on a list of the ordered pairs, but we consider the ordered pairs to be the same. In other words, we have a 2 to 1 map from ordered pairs to unordered pairs. Hence, the number of unordered pairs equals the number ordered pairs divided by 2. So, in a deck of 52 cards, there are (52 * 51)/2 = 1326 unordered pairs.

Example

From a deck of 52 cards, how many ordered 5-card sequences can be formed?

52 * 51 * 50 * 49 * 48

How many orderings of 5 cards?

5! = 120

How many unordered 5-card hands?

52*51*50*49*48/5! = 2,598,960 (the number of different 5-card hands)

Combinations

A combination or choice of r out of n objects is an (unordered) set of r of the n objects. The number of r combinations of n objects is the same as number of subsets of size r that can be formed from an -element set:

Consider the problem of determining how many 8-bit sequences have two 0s and six 1s? It might be tempting to say that there are 8 ways to place the first 0 and 7 ways to place the second 0. That's incorrect, however, because it violates the product rule, which requires a 1 to 1 onto correspondence. Choosing position i for the first 0 and then position j for the second 0 gives the same sequence as choosing position j for the first 0 and position i for the second. So there are two different ways to make each sequence. From a choice tree viewpoint, we have to make sure that each object comes up only once.

Instead, we can choose the set of 2 positions to put the 0s: . The 1s must then occupy the remaining slots. Or we can choose the set of 6 positions to put the 1s: . The 0s are forced. Hence, there are 8*7/2=28 possible sequences.

Note that (choosing things in the set) gives the same result as (choosing things not in the set). The formula is symmetric.

It is easy to go wrong in counting arguments. Take a close look at the following counting arguments for finding the number of 5-card hands that have at least 3 aces.

Argument 1:

• ways of picking three of four aces.
• ways of picking 2 cards from the remaining 49 cards.
• .

Argument 2:

• How many hands have exactly 3 aces? ways of picking three of the four aces. ways of picking two cards that are not aces. .
• How many hands have exactly 4 aces? way of picking four of the four aces. There are 48 ways of picking one of the remaining cards. 4512+48=4560

The results of arguments 1 and 2 should match, but they don't: . Hence, at least one of the two counting arguments is incorrect. Where is the problem?

One useful guideline for detecting fallacious reasoning is to make sure that the product rule's condition that no two leaves of a choice tree have the same label is met. For any choice tree object, it should be possible to reconstruct the sequence of choices that leads to it. So, given an arbitrary object in S, we should be able to reverse-engineer the choices that created it.

In argument 1, in choosing 3 of 4 aces, then choosing the 2 remaining cards, we can't determine which cards come from which choice because many different sequences of choices actually produce the same hand.

The first argument must be incorrect.

Applying the same sleuthing criteria, it is easy to see that the second argument is correct. In (), the aces came from the first choice and the non-aces came from the second choice.

In summary, the two big mistakes that people make in associating a choice tree with a set S are:

1. Creating objects not in S.
2. Creating the same object in two different ways.

To be sure we are on the correct path, we should always check whether we are creating objects of the right type. And we should be able to reverse-engineer the choice sequence from any given object.