We often want to know the answer to the question, “How many?” In this chapter we shall look at some of the rules that help us to answer this question.

Some Counting Principles

One obvious question, given a set S, is “how many elements are there in S? We shall denote that number by |S|, the order of S.

We shall start with an example.

Sample Problem 1.1 Suppose there are 30 students in Dr. Green’s finite mathematics course and 40 in his calculus section. If these are his only classes, and if 20 of the students are taking both subjects, how many students does he have altogether?

Solution. We shall use the notation S for the set of students in the finite mathematics class and T for calculus. So |S| = 30 and |T| = 40, and |S∩T| = 20.

We want to know the number of elements of |S∪T|.

If we wrote a list of all the students in the two classes, we would write |S| + |T| = 30+40 names. But we have duplicated the 20 names in |S∩T|. Therefore the total number is

|S∪T| = |S|+|T|−|S∩T| = 30+40−20 = 50,

so he has 50 students.

This is the simplest case of a rule called the principle of inclusion and exclusion,  and you can remember it in the following way. To list all members of the union of two sets, list all members of the first set and all members of the second set. This ensures that all members are included. However, some elements will be listed twice,  so it is necessary to exclude the duplicates. If S is the set of all the objects that have some property A and T is the set of all the objects with property B, then (1.1)  expresses the way to count the objects that have either property A or property B:

(i) count the objects with property A;

(ii) count the objects with property B;

(iii) count the objects with both properties;

(iv) subtract the third answer from the sum of the other two.

Putting it another way, if you list all members of S, then list all the members of T, you will cover all members of S ∪T, but those in S ∩T will be listed twice. To count all members of S∪T, you could count all members of both lists, then subtract the number of duplicates. In other words,

                |S∪T| = |S|+|T|−|S∩T|.                                                                               (1.1)

A similar argument can be applied to three or more sets. For example, suppose you want to know the number of elements in S∪T ∪W. If you add |S|, |T| and |W|, you have added all the elements of S ∩T twice, and similarly those of S ∩W and T ∩W. So subtract the orders of those sets. Then every element of one or two of the sets has been counted twice. But you are missing the elements of S∩T ∩W—they were added three times and subtracted three times. So

                               |S∪T ∪W| = |S|+|T|+|W|−|S∩T|−|S∩W|−|T ∩W|+|S∩T ∩W|.

This can be generalized to any number of sets.

A variation of this rule, called the rule of sum, can be simply expressed by saying  “the number of objects with property A equals the number that have both property A and property B, plus the number that have property A but not property B”; if we again define sets S and T to be the collections of all objects having properties A and B respectively, the rule is

                       |S| = |S∩T|+|ST|.                                                                                      (1.2)

If we rewrite (1.2) as

                          |ST| = |S|−|S∩T|

and substitute into (1.1), we obtain

                            |S∪T| = |T|+|ST|.                                                                                    (1.3)

Sample Problem 1.2 Suppose the set S has 35 elements, T has 17 elements, and S∩T has seven elements. Find |S∪T| and |ST|.

Solution. From (1.1) we see

                                |S∪T| = |S|+|T|−|S∩T| = 35+17−7 = 45.

From (1.2) we get

                                       |ST| = |S|−|S∩T| = 35−7 = 28.

It is sometimes useful to break an event down into several parts, forming what we shall call a compound event. For example, suppose you are planning a trip from Los Angeles to Paris, with a stopover in New York. You have two options for the flight to New York: a direct flight with Delta or an American flight that stops in Chicago.

For the second leg, you consider the direct flight with Air France, a British Airways flight through London, and Lufthansa stopping in Frankfurt. There are two ways to make the first flight and three to make the second, for a total of six combinations.

Suppose S is the set of available flights for the first leg and T is the set of available flights for the second leg. Then the flight combinations correspond to the members of the Cartesian product S×T, and in this example

                               |S| = 2, |T| = 3, |S×T| = |S|×|T| = |2×3| = 6.

The correspondence between compound events and Cartesian products applies in general. If S is the set of cases where A occurs, and T is the set of cases where B occurs, then the possible combinations correspond to the set S × T, which has |S|×|T| elements. This idea is usually applied without mentioning the sets S and T.

Suppose the event A can occur in a ways and the event B can occur in b ways,  then the combination of events A and B can occur in ab ways. This very obvious principle is sometimes called the multiplication principle or rule of product. It can be extended to three or more sets.

Sample Problem 1.3 To open a bicycle lock you must know a three-number combination. You must first turn to the left until the first number is reached,  then back to the right until the second number, then left to the third number.

Any number from 1 to 36 can be used. How many combinations are possible?

Solution. There are 36 ways to choose the first number, 36 ways to choose the second, and 36 ways to choose the third. So there are 36×36×36 combinations.

Sample Problem 1.4 A true–false test consists of four questions. Assuming you answer all questions, how many ways are there to answer the test ?

Solution. There are two ways to answer the first question, two ways to answer the second, two ways to answer the third, and two ways to answer the fourth. So the total is 2×2×2×2= 16.

The multiplication principle only works when the events are performed independently—if the result of A is somehow used to affect the performance of B, some combined results may be impossible. In the airline example, if the Delta flight leaves too late to connect with the Air France flight, then your choices are not independent,  and only five combinations would be available.

Sometimes the order of the elements in a set is unimportant, but sometimes the order is significant. In that case we would like to know how many ways there are to order the elements of the set. For example, if you have three cards, an Ace, King and Queen (abbreviated as A, K, Q), they can be ordered in six ways: AKQ, AQK,  KAQ, KQA, QAK, and QKA. The three-element set {A,K,Q} has six orderings.

So obviously any three-element set has three orderings.

More generally, suppose S is a set with n elements. How many different ways are there to order the elements of S?

We solve this by treating the ordering as a compound event with n parts. There are n ways to choose the first element of the ordered set. Whichever element is chosen,  there remain n − 1 possible choices for the second element. When two elements have been selected, there are n−2 choices for the third element.

In this way, we see that there are n × (n − 1)× n − 2 × ... × 3 × 2 × 1 ways to order S. This number is called n factorial, and denoted n!. So

n! = n ·(n−1)·(n−2)·...· 3 · 2 · 1.

For convenience we define 0! to equal 1.

The different ways of ordering the set S are called permutations of S.

Sample Problem 1.5 Evaluate 10!.

Solution. 10! = 10×9×8×7×6×5×4×3×2×1= 362880.

Sample Problem 2.6 A committee of three people—chair, secretary, and treasurer—is to be elected by a club with 11 members. If every member is eligible to stand for each position, how many different committees are possible?

Solution. We can treat the selection of the committee as a compound event with three parts: choose the chair, choose the secretary, and choose the treasurer. These parts can be performed in 11, 10, and 9 ways respectively. So there are 11×10×9 committees possible.

Sample Problem 1.7 Four boys and four girls are to sit along a bench. The boys must sit together, as must the girls. How many ways can this be done?

Solution. We treat this as a compound event with three parts. First, it is decided whether the boys are to be on the left or on the right. This can be done in two ways. Then the ordering of the boys is chosen. This can be done in 4! = 24 ways.

Finally, the girls are ordered. This can be accomplished in 4! = 24 ways. So there are 2×24×24 = 1152 arrangements.