1.1 Principle of Inclusion and Exclusion
This very important principle is a generalization of the Sum Rule to sets which need not be disjoint. Let’s say that we have 2 sets \(A\) & \(B\). We look at the cardinality of the union of these 2 sets (We assume that students going through this module are familiar with the notions of Unions and Intersections of Sets. If not, we’ll cover them after the important chapters of Algebra are covered).
\(|A\bigcup B|=|A|+|B|-|A\bigcap B|\). The reason being that elements common to both the sets will be accounted for more than once when we count the cardinality of the union of the 2 sets. If we extend this to more than 2 sets we have
\(|A+B+C|=\sum|A|-\sum|A\bigcap B|+\sum|A\bigcap B\bigcap C|\). Finally extending this to \(n\) sets we arrive at
\(\left|\bigcup\limits_{i=1}^{n}A_i\right|=\sum\limits_{i=1}^{n}\left| A_i\right|-\sum\limits_{1\le i< j\le n} |A_i\bigcap A_j|+\sum\limits_{1\le i<j<k\le n}|A_i\bigcap A_j\bigcap A_k|+…+(-1)^{n-1}|A_1\bigcap A_2\bigcap … \bigcap A_n|\)
This is what we call the Principle of Inclusion and Exclusion.
Backtracking a bit, let us derive the proof of the formula that we wrote for Derangements. Suppose that we have the famous problem of n envelopes and n letters that we need to arrange, such that no letter gets the correct envelope.
Now let’s denote the total number of such arrangements possible by \(A\), and let’s denote by \(A_i\) the number of arrangements possible where the ith letter goes to the right envelope. Thus we need to find \(|A|-|A_i\bigcup A_2….\bigcup A_n|\).
Let’s apply the principle that we studied earlier to this case.
\(|A|-|A_1\bigcup A_2\bigcup A_3…\bigcup A_n|=n!-C(n,1)\times (n-1)!+C(n,2)\times (n-2)!-…(-1)^nC(n,n)\times 1!\).
Taking \(n!\) out of the RHS gives us the formula for Derangements.
1.2 Pigeon Hole Principle
The principle states that if there are \(n\) pigeons and there are \(n-1\) available holes for these pigeons, then at least one hole will contain more than 1 pigeon. Popularly, this is also known as the ‘Box Principle’. (Note that if we ignore the third gender for now, among 3 people, there must be at least 2 of the same sex).
Ex -1
There are \(n\) persons seated in a room. Show that there are 2 persons among them who know the same number of people in the room (i.e. there are 2 people with the same number of acquaintances).
Solution:
Note that the number of acquaintances can be an integer between {0,1,2…(n-1)}. So we have \(n\) distinct possible values for the number of acquaintances (holes) any person can have. We also have \(n\) people (pigeons) in the room. So, under this circumstance, we can assign one possible number of acquaintances to each individual person (and thus each hole will contain exactly one pigeon). But note that in the set of possible values for the number of acquaintances, we cannot have 0 and (n-1) occurring simultaneously (If a person knows 0 people, there cannot be any individual who knows all (n-1) people). Thus the number of possible values that the number of acquaintances shrinks to (n-1), and we have n people, thus from the Pigeon Hole Principle, there must be some 2 people who share the same number of acquaintances.
Ex -2:
Consider the Fibonacci sequence defined by \(a_n=a_{n-1}+a_{n-2}\) for \(n \ge 2\), with \(a_1=a_2=1\). Show that, for any given \(n\), we can find a fibonacci number ending with \(n\) zeroes.
Solution:
We’ll first show that this sequence, under a certain mapping is periodic. Let’s consider the numbers modulo 10, i.e instead of considering the actual numbers, we shall consider their remainders when they’re divided by 10.
Thus the sequence becomes \(1,1,2,3,5,8,3,1,4,5,9….\). Let’s consider these numbers in pairs, i.e \((1,1),(1,2),(2,3),(3,5)…\). We consider 100 such pairs. Note that in this series of pairs, we won’t be encountering the pair \((0,0)\). This brings us down to 99 pairs, with one pair repeating itself.
It’s easy to show that the first repeating pair is \((1,1)\) (Try showing this). For example, if we assume that \((8,3)\) is the first repeating pair, then the pair before \((8,3)\) has to be something like \((a,8)\) for some \(0\le a\le 9\). Remember that we’re only considering the remainders of the numbers of the original fibonacci sequence. In this case, the only possible value of \(a\) is \(5\). Thus, we have \((5,8)\) repeating as well, contradicting our claim that \((8,3)\) is the first repeating pair.
Now that we have proved this sequence to be periodic, with \((1,1)\) being the first pair to repeat, we will now consider the sequence modulo \(10^n\) instead of \(10\). If we can show that the term 0 will occur in this sequence, we’re done. Similarly, as before, let’s consider \(10^{2n}+1\) terms of the sequence modulo \(10^n\), and consider them in pairs. As before we can show that the first repeating pair is \((1,1)\). Thus the pair just before this element has to be \((0,1)\), which means 0 occurs in the sequence.
Test Your Concepts:
We have just shown that the fibonacci sequence modulo 10 is periodic. What can be the maximum length of this period?