Some refresher of motivation(s) and simple applications of the inclusion-exclusion principle. Remember that: (1) We owe a lot to the Indians who taught us how to count. — Albert Einstein. (2) Everything that can be counted is countable, but everything that is countable does not count. — Albert Einstein.
We will derive and apply an important counting formula called the inclusion-exclusion principle. Recall that the addition principle gives a simple formula for counting the number of objects in a union of sets, provided that the sets do not overlap (that is, provided that the sets determine a partition). The inclusion-exclusion principle gives a formula for the most general of circumstances in which the sets are free to overlap without restriction. The formula is necessarily complicated, but, as a result is more widely applicable.
1. The Inclusion-Exclusion Principle:
We know of several examples in which it is easier to make an indirect count of the number of objects in a set rather than to count the objects directly. Below are two more examples:
Example:
Count the permutations of
in which 1 is not in the first position (that is,
).
We could make a direct count by observing that the permutations with 1 not in the first position can be divided into parts according to which of the
integers k from
is in the first position. A permutation with k in the first position consists of k followed by a permutation of the
element set
. Hence, there are
permutations of
with k in the first position. By the addition principle, there are
permutations of
with 1 not in the first position.
Alternatively, we could make an indirect count by observing that the number of permutations of with 1 in the first position is the same set as the number
of permutations of
. Since the total number of permutations of
is n!, the number of permutations of
in which 1 is not in the first position is
.
Example:
Count the number of integers between 1 and 600, inclusive, which are not divisible by 6.
We can do this indirectly as follows: The number of integers between 1 and 600 which are divisible by 6 is 600/6 which is equal to 100 since every sixth integer is divisible by 6. Hence, of the integers between 1 and 600 are not divisible by 6.
Some further notes:
The rule used to obtain an indirect count in these examples is the following: If A is a subset of a set S, then the number of objects in A equals the number of objects in S minus the number not in A. Recall that
is the complement of A in S: that is, the set consisting of those objects in S which are not in A. The rule can then be written as
, or equivalently,
. This formula is the simplest instance of the inclusion-exclusion principle.
We shall formulate the inclusion-exclusion principle in a manner in which it is convenient to apply. As a first generalization of the preceding rule, let S be a finite set of objects, and let and
be two “properties” that each object in S may or may not possess. We wish to count the number of objects in S that have neither property
nor property
. We can do this by first including all objects of S in our count, then excluding all objects that have property
and excluding all objects which have property
, and then, noting that we have excluded objects having both properties
and
twice, readmitting all such objects once. We can write this symbolically as follows: Let
be the subset of objects of S that have property
, and let
be the subset of objects of S that have property
. Then,
consists of those objects of S not having property
and let
consists of those objects of S not having property
. The objects of the set
are those having neither property
nor property
. We then have
.
Since the left side of the preceding equation counts the number of objects of S that have neither property nor property
, we can establish the validity of this equation by showing that an object with neither of the two properties
and
makes a net contribution of 1 to the right side, and every other object makes a net contribution of zero. If x is an object with neither of the properties
and
, it counted among the objects of S, not counted among the objects of
or of
, and not counted among the objects of
. Hence, its net contribution to the right side of the equation is
.
If x has only the property , it contributes
to the right side, while it has only the property
, it contributes
to the right side. Finally, if x has both properties
and
, it contributes
to the right side of the equation. Thus, the right side of the equation also counts the number of objects of S with neither property
nor property
.
More generally, let ,
,
,
,
be m properties referring to the objects in S, and let
, and
be the subset of objects of S that have property S (and possibly other properties). Then, is the subset of objects that have both properties
and
(and, possibly others),
is the subset of objects which have properties
,
,
and so on. The subset of objects having none of the properties is
. The inclusion exclusion principle shows how to count the number of objects in this set by counting objects according to the properties they do have. Thus, in this sense, it “inverts” the counting process.
Theorem 1.1:
The number of objects of S that have none of the properties ,
,
,
is given by:
,
where the first sum is over all 1-combinations of
, the second sum is over all 2-combinations
of
, the third sum is over all 3-combinations
of
, and so on.
Reference:
Introductory Combinatorics (Fourth Edition), Richard A. Brualdi:
For example, available at Amazon India:
Also, for example, available at Flipkart:
To be continued further,
Nalin Pithwa.