General Statement of the Principle of Inclusion and Exclusion
In Chapter 13, we introduced the Principle of Inclusion and Exclusion (PIE) by first deriving the identity
for two finite sets A1 and A2, and then extending it to the following identity:
for three finite sets A1, A2 and A3. Naturally, one would like to know whether (14.1) and (14.2) could be extended to an identity involving any n (≤ 2) finite sets Ai, A2,…,An and if so, what identity would one get in general. The main objective of this chapter is to deal with this problem. We shall first extend (14.2) to an identity involving four sets, and then by observing these special cases, we will obtain the general statement of the (PIE) for any finite number of finite sets. Finally, two examples will be given to illustrate the application of the general statement of the (PIE).
Suppose that four finite sets A1, A2, A3 and A4 are given. By applying (14.1), (14.2) and some basic laws for sets, we have
Now, let us look at the identities (14.1)–(14.3) carefully and make some observations on the patterns of the terms on the RHS of the identities.
For the sum of the terms within the first grouping, we have:
For the sum of terms within the second grouping, we have:
For the sum of terms within the third grouping, we have:
We also notice that the groupings alternate in sign, beginning with a (+) sign
Suppose now that we are given n finite sets: A1, A2, … , An. By generalising the above observations, what identity would you expect for 
The first grouping should be the sum of 
terms, each involving a single set:
The second grouping should be the sum of 
terms, each involving the intersection of two sets:
in abbreviation,
The third grouping should be the sum of 
terms, each involving the intersection of three sets:
in abbreviation,
Likewise, the fourth grouping should be the sum of 
terms, each involving the intersection of four sets:
and so on.
Bearing in mind that the groupings alternate in sign, beginning with a “+” sign, one would expect that the following holds:
Indeed, it can be proved (for instance, by mathematical induction) that (14.4) holds for any n finite sets A1, A2,…, An.
We shall now show an application of (14.4) by considering the following:
Example 14.1 How many ways are there to arrange n (≥2) married couples in a row so that at least one couple are next to each other?
Discussion and Solution Denote the n husbands and the n wives of the n couples by H1, W1, H2, W2,…, Hn, Wn. Thus, when n = 4 for example, the following arrangements are allowed:
Solving the above problem by dividing it into cases such that exactly one couple are next to each other, exactly two couples are next to each other, and so on would be very complicated. Let us try to apply (14.4).
For each i = 1,2,… ,n, let Ai be the set of arrangements of the n couples such that Hi and Wi are adjacent (next to each other). The problem is thus to enumerate 
To apply (14.4), we compute each grouping on its RHS.
To compute 
we first consider |A1| . A1 is the set of arrangements of n couples such that H1 and W1 are adjacent. This is the same as arranging the 2n – 1 objects:
in a row where H1W1 can be permuted in two ways: H1W1 and W1H1. Thus,
Similarly, 
for each i = 2,3,…,n. Thus,
To compute 
we first consider |A1 ∩ A2|. A1 ∩ A2 is the set of arrangements of the n couples such that H1 and W1 are adjacent and H2 and W2 are adjacent. This is the same as arranging the 2n – 2 objects:
in a row where both H1W1 and H2W2 can be permuted by themselves. Thus,
Similarly, for 
Thus,
We now leave it to the reader to show that
and so on to obtain the following final result that
For the case when n = 4, we have
Next, we shall introduce an old problem regarding decks of cards. Two decks X, Y of cards, with 52 cards each, are given. The 52 cards of X are first laid out. Those of Y are then placed randomly, one each on top of each card of X, so that 52 pairs of cards are formed. The question is: what is the probability that no cards in each pair are identical (i.e. having the same suit and rank)? This problem, known as “le probleme des rencontres” (the matching problem), was introduced and studied by the Frenchman Pierre Remond de Montmort (1678–1719) around the year 1708. The number of ways of distributing the cards of Y to form 52 pairs of cards with those in X is clearly 52!. Thus, to find the desired probability, we need to find out the number of ways of distributing the cards of Y such that each card in Y is placed at the top of a different card in X.
Instead of solving the above problem directly, let us generalise it and consider the following more general problem. A permutation a1a2 … an of 
is called a derangement of if ai ≠ i for each i ≠ 1,2,… ,n. Thus 54132 is a derangement of 
and 32154 are not. For n = 1, 2, 3, 4, all the derangements of are shown in the following table.
| n | Derangements |
| 1 | None |
| 2 | 21 |
| 3 | 231, 312 |
| 4 | 2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, 4321 |
Let Dn denote the number of derangements of . It follows from the table above that D1 =0, D2 = 1, D3 = 2 and D4 = 9. Returning back to the matching problem, it is now clear that its answer is given by 
. How do we evaluate Dn for each n? After some thought, you may realise that this is not a trivial problem. Well, we are given a good opportunity to show our second application of (PIE).
Before proceeding any further, let us first derive an equivalent form of (14.4).
For a subset A of a universal set S, recall that A denotes its complement. It was pointed out in Chapter 13 that (14.2) is equivalent to the following: For any subsets A1, A2, A3 of S,
In general, for any n (≥ 2) subsets A1, A2, …,An of S, one can show that (14.4) is equivalent to the following:
We shall now evaluate Dn by applying (14.5). Let us first identify what the universal set is. We are now concerned with derangements, which are special types of permutations of . So, let the universal set S be the set of all permutations of .
For each i = 1,2,…,n, let Ai be the set of permutations a1a2 … an in S such that ai = i. Thus, 
is the set of permutations in S such that ai ≠ i, and so 
is the set of permutations in S such that ai = i for all i = 1,2,…,n, which is exactly the set of derangements of . We thus have
To evaluate Dn by (14.5), we evaluate each grouping on the RHS of (14.5). Clearly, as S is the set of all permutations of , we have 
Observe that A1 is the set of permutations of the form 1a2a3 … an. Thus, 
Similarly, |Ai| = (n – 1)! for each i = 2,3,… ,n, and so
As 
is the set of permutations of the form 12a3a4 …an, we have 
Similarly, 
for all i, j∈ {1,2,…, n} with i < j. There are 
number of ways of choosing i and j from {1,2,…, n} with i <j, and so
We now leave it to the reader to show that
and so on to obtain the following final result by (14.5) that
Note that for r = 1,2,…,n,
Thus,
Suppose we generate a permutation of at random. The probability that this permutation is a derangement is given by 
which by the above result is
When n gets larger and larger, it is known that the quotient gets closer and closer to 
where the constant e, called the natural exponential base, is defined by 
It is known that e ≈ 2.718281828459045. (The letter “e” was chosen in honour of the great Swiss mathematician Leonhard Euler (1707–1783) who made some significant contributions to the study of problems related to the limit above.)
We make a final remark which is useful when considering whether to use the general statement of the (PIE) to enumerate |A| for a finite set A. In the event that it is not easy to partition A, i. e. to divide it into cases of mutually exclusive subsets, we may ask the question: Can we find sets Ai, i = 1,2,…,n, which are “easy” to count but with no necessity for them to be mutually exclusive, such that either 
Exercise
14.1 Show that the number of ways to seat n(≥2) married couples round a table so that at least one couple are next to each other is
14.2 A lottery is run with each ticket bearing a distinct 7-digit number. Every digit is chosen from the digits 1, 2, 3, 4, 5, 6, 7 and all digits in the number are distinct. Only one prize is given. If all possible tickets are sold, what is the probability that a randomly chosen ticket has at least 4 digits matching those of the winning ticket?
14.3 Show that the number of integer solutions to the equation (see Chapter 7)
such that 0 ≤ xr ≤ 9 for each r = 1, 2,…, 11 is given by
14.4 Each of ten ladies checks her hat and umbrella in a cloakroom and the attendant gives each lady back a hat and an umbrella at random. Show that the number of ways this can be done so that no lady gets back both of her possessions is
14.5 Show that the number of onto mappings from 
where m ≥ n ≥ 1, is given by
14.6 A football team has five different jerseys. The team takes part in a tournament where they have to play 8 matches.
(i) Find the number of ways the team wear their jerseys for the 8 matches
(a) if there are no restrictions on the choices,
(b) if the team never wears the same jersey on consecutive matches,
(c) if the team uses at most three jerseys.
(ii) Given that each jersey is used at least once, show that the number of ways the team can choose their jerseys is
(iii) State what the following expression represents as far as choosing jerseys is concerned:
Hence find the value of this expression for 1 ≤ n < 5.
(iv) Show that
