Page 188 - DMTH202_BASIC_MATHEMATICS_II

Unit 13: Combinations

r n – r
b will be the
12. In view of the fact that C(n, r) = C(n, n – r), the coefficients of a b and a n – r r Notes
..............................,
13. The coefficient of in the expansion (a + a +… + a ) is .............................., and is called a
n
1 2 m
multinomial coefficient, in analogy with the binomial coefficient.
13.4 Inclusion-Exclusion Principle

Let us begin with considering the following situation: In a sports club with 54 members, 34 play
tennis, 22 play golf, and 10 play both. There are 11 members who play handball, of which 6 play
tennis also, 4 play golf also, and 2 play both tennis and golf. How many play none of the three sports?
To answer this, let S represent the set of all members of the club. Let T represent the set of tennis
playing members, G represent the set of golf playing members, and H represent the set of
handball playing members. Let us represent the number of elements in A by A .

Consider the number S – T – G – H.
Is this the answer to the problem? No, because those who are in T as well as G have been
subtracted twice. To compensate for this double subtraction, we may now consider the number
S  T  G  H  T  G  G  H  H  T .
Is this the answer? No, because those playing all the three games have been subtracted thrice and then
added thrice. But those members have to be totally excluded also. Hence, we now consider the number
S  T  G  H  T  G  G  H  H  T  T  G  H .

This is the correct answer. This reduces to 54 – 34 – 22 – 11 + 10 + 6 + 4 – 2 = 5.
To solve this problem we have made inclusions and exclusions alternately to arrive at the
correct answer. This is a simple case of the principle of inclusion and exclusion.

Did u know? It is also known as the sieve principle because we subject the objects to sieves
of a progressively finer mesh to arrive at a certain grading.
Let us state and prove this principle now.

13.4.1 Inclusion-Exclusion Formula

Let A , A ,…, A be n sets in a universal set U consisting of N elements. Let S denote the sum of
1 2 n k
the sizes of all the sets formed by intersecting k of the A is at a time. Then the number of
elements in none of the sets A , A ,…, A is given by
1 2 n
A  A  ... A n = N – S + S – S +… +(–1) S +… +(–1) S n
k
n
1
2
3
2
k
1
Self Assessment
Fill in the blanks:
14. Inclusion-Exclusion principle is also known as the .............................. principle because we
subject the objects to sieves of a progressively finer mesh to arrive at a certain grading.
15. Inclusion-Exclusion formula is given by A  A  ... A n = .............................. .
1
2

LOVELY PROFESSIONAL UNIVERSITY 183