Some examples

Let us consider here some applications of the inclusion/exclusion principle. In this first example, we want to count in how many ways we can form a hand of 10 cards from a deck of 52 so it contains four cards with the same value, say four aces, of four cards equal to 2, or four cards equal to 3, up to four cards equal to 10, or to jack or to the queen or to the king.

So as I said, x we are considering the subset of 10 cards among 52. And sets Ai, well for each i belonging to one of the values which is from ace equal to 1 to king equal to 13, we consider the hands of 10 cards that contain four cards of value equal to i. So A1 will be the set of hands of cards that is subset of 10 elements among 52 that contains four cards equal to an ace. So what we want to count is the cardinality of the union of A1, with A2, with A13. Well, we apply the inclusion/exclusion principle.

We have to count sigma 1 and then to subtract sigma 2, add sigma 3, and so on, up to sigma 13 with the signs plus because 13 is odd. Let us count these quantities. Well sigma 1 is the sum of the cardinalities of the sets. What is the cardinality of one of these sets, say A1. Well, we have a set that contains four aces, so we just have to choose six other elements among the deck of cards, minus the four aces. So among 48 cards. And this holds for every one of these sets, A1, A13. So we get 13 times the binomial 52 minus 4 over 10 minus 4, which is 13 times the binomial 48 over 6.

Let us compute sigma 2. Well, sigma 2 is the sum of the number of elements of the pairwise intersection of these sets. Let us count, for instance, the number of elements of A1 intersection A2. A1, hands of 10 cards that contain four aces. A2, hands of 10 cards that contains four 2s. So the intersection are the hands of 10 cards that contain both four aces and four 2s. So it is enough to choose two cards among the remaining cards. So there are 52 minus 8 over 10 minus 8 cards. And this is equal for any pairwise intersection. How many are there?

Well, there are as many intersection 2 by 2 as are the choices of two elements among 13, so binomial 13 over two choices, which gives sigma 2 equal to binomial 13 over 2 times binomial 44 over 2. Of course, if k is strictly greater than 2, sigma k equal to 0 because we have intersection of more than three sets, and every intersection of three sets is empty. There are no hands of 10 cards that contain say, four aces, four 2s, and four 3s. So the application of inclusion/exclusion principle gives 13 times binomial 48 over 6, minus binomial 13 over 2 times 44 over 2 elements.

As an application, let us count the anagrams of TAMTAM that have at least two consecutive letters that are equal, say to T, or to M, or to A. So let us define by x the set of anagrams of TAMTAM, that is, the permutations of the sequence T-A-M-T-A-M. And by AT we denote the anagrams of TAMTAM that have two T one near to the other. And the same by we denote A-A and A-M in a similar way. So we want to count the cardinality of the union of these three sets. And of course, we will apply the inclusion/exclusion principle, which gives us sigma 1 minus sigma 2 plus sigma 3. Let us count sigma 1.

Well, sigma 1 is the sum of the elements of the three sets. Of course, each side has the same cardinality, so it is enough to compute the cardinality of AT and multiply it by 3. What is AT? Well, AT is the set of anagrams that contain T-T and then A-M-A-M. So it’s the set of anagrams of the five sequence formed by T-T-A-M-A-M. So we get the number of elements, which is factorial of 5 divided by factorial of 2 to the square. So sigma 1 is 3 times this quantity.

Sigma 2, the sum of the elements of pairwise intersections. Let us count, for instance, the number of elements of AT intersection AA, which is the set of anagrams of the sequence– of the fourth sequence– T-T-A-A-M and M. So we have four letters with two repetitions, so it is equal to factorial of 4 divided by factorial of 2. And then we get immediately sigma 2, multiply this quantity by 3. Finally the intersection of the three sets. Well, it is the set of anagrams of the three sequence T-T-A-A-M-M, and it has factorial of 3 elements.

So in order to find the number of anagrams that we are looking for, we apply the inclusion/exclusion principle, and so we add with alternate signs sigma 1, sigma 2 and sigma 3.