The Inclusion-Exclusion principle

The Inclusion-exclusion principle computes the cardinal number of the union of multiple non-disjoint sets. For two sets A and B, the principle states −
|A∪B|=|A|+|B|−|A∩B|
For three sets A, B and C, the principle states −
|A∪B∪C|=|A|+|B|+|C|−|A∩B|−|A∩C|−|B∩C|+|A∩B∩C|
The generalized formula -
|⋃ni=1Ai|=∑1≤i<j<k≤n|Ai∩Aj|+∑1≤i<j<k≤n|Ai∩Aj∩Ak|−⋯+(−1)π−1|A1∩⋯∩A2|
Problem 1
How many integers from 1 to 50 are multiples of 2 or 3 but not both?
Solution
From 1 to 100, there are 50/2=25
numbers which are multiples of 2.
There are 50/3=16
numbers which are multiples of 3.
There are 50/6=8
numbers which are multiples of both 2 and 3.
So, |A|=25
, |B|=16 and |A∩B|=8.
|A∪B|=|A|+|B|−|A∩B|=25+16−8=33
Problem 2
In a group of 50 students 24 like cold drinks and 36 like hot drinks and each student likes at least one of the two drinks. How many like both coffee and tea?
Solution
Let X be the set of students who like cold drinks and Y be the set of people who like hot drinks.
So, |X∪Y|=50
, |X|=24, |Y|=36 |X∩Y|=|X|+|Y|−|X∪Y|=24+36−50=60−50=10
Hence, there are 10 students who like both tea and coffee.

Discrete Mathematics - The Pigeonhole Principle

The Pigeonhole Principle

Suppose that a flock of 20 pigeons flies into a set of 19 pigeonholes to roost. Because there are
20 pigeons but only 19 pigeonholes, a least one of these 19 pigeonholes must have at least two
pigeons in it. To see why this is true, note that if each pigeonhole had at most one pigeon in it,
at most 19 pigeons, one per hole, could be accommodated. This illustrates a general principle
called the pigeonhole principle, which states that if there are more pigeons than pigeonholes,
then there must be at least one pigeonhole with at least two pigeons in it.

Theorem:

I) If “A” is the average number of pigeons per hole, where A is not an integer then

• At least one pigeon hole contains ceil[A] (smallest integer greater than or equal to A) pigeons
• Remaining pigeon holes contains at most floor[A] (largest integer less than or equal to A) pigeons

                                                                              Or

II) We can say as, if n + 1 objects are put into n boxes, then at least one box contains two or more objects.
The abstract formulation of the principle: Let X and Y be finite sets and let f: X –> Y be a function.

• If X has more elements than Y, then f is not one-to-one.
• If X and Y have the same number of elements and f is onto, then f is one-to-one.
• If X and Y have the same number of elements and f is one-to-one, then f is onto.

Pigeonhole principle is one of the simplest but most useful ideas in mathematics. We will see more applications that proof of this theorem.

Example 1: If (Kn+1) pigeons are kept in n pigeon holes where K is a positive integer, what is the average no. of pigeons per pigeon hole?

Solution: average number of pigeons per hole = (Kn+1)/n = K + 1/n
Therefore at least a pigeonholes contains (K+1) pigeons i.e., ceil[K +1/n] and remaining contain at most K i.e., floor[k+1/n] pigeons.
i.e., the minimum number of pigeons required to ensure that at least one pigeon hole contains (K+1) pigeons is (Kn+1).

Example 2: A bag contains 10 red marbles, 10 white marbles, and 10 blue marbles. What is the minimum no. of marbles you have to choose randomly from the bag to ensure that we get 4 marbles of same color?

Solution: Apply pigeonhole principle.
No. of colors (pigeonholes) n = 3
No. of marbles (pigeons) K+1 = 4
Therefore the minimum no. of marbles required = Kn+1
By simplifying we get Kn+1 = 10.
Verification: ceil[Average] is [Kn+1/n] = 4
[Kn+1/3] = 4
Kn+1 = 10
i.e., 3 red + 3 white + 3 blue + 1(red or white or blue) = 10

Pigeonhole principle strong form.

Theorem: Let q₁, q₂, . . . , q_n be positive integers.
If q₁+ q₂+ . . . + q_n − n + 1 objects are put into n boxes, then either the 1st box contains at least q₁ objects, or the 2nd box contains at least q₂ objects, . . ., the nth box contains at least q_n objects.

Application of this theorem is more important, so let us see how we apply this theorem in problem solving.

Example 1: In a computer science department, a student club can be formed with either 10 members from first year or 8 members from second year or 6 from third year or 4 from final year. What is the minimum no. of students we have to choose randomly from department to ensure that a student club is formed?

Solution: we can directly apply from the above formula where,
q₁ =10, q₂ =8, q₃ =6, q₄ =4 and n=4
Therefore the minimum number of students required to ensure department club to be formed is
10 + 8 + 6 + 4 – 4 + 1 = 25

Example 2: A box contains 6 red, 8 green, 10 blue, 12 yellow and 15 white balls. What is the minimum no. of balls we have to choose randomly from the box to ensure that we get 9 balls of same color?
 

Solution: Here in this we cannot blindly apply pigeon principle. First we will see what happens if we apply above formula directly.
From the above formula we have get answer 47 because 6 + 8 + 10 + 12 + 15- 5 + 1 = 47
But it is not correct. In order to get the correct answer we need to include only blue, yellow and white balls because red and green balls are less than 9. But we are picking randomly so we include after we apply pigeon principle.
i.e., 9 blue + 9 yellow + 9 white – 3 + 1 = 25
Since we are picking randomly so we can get all the red and green balls before the above 25 balls. Therefore we add 6 red + 8 green + 25 = 39
We can conclude that in order to pick 9 balls of same color randomly, one has to pick 39 balls from a box.
 

Discrete Mathematical Structures - Functions

Function – Definition
A function or mapping (Defined as f: X→Y) is a relationship from elements of one set X to elements of another set Y (X and Y are non-empty sets). X is called Domain and Y is called Codomain of function ‘f’.

Function ‘f’ is a relation on X and Y s.t for each x ∈X, there exists a unique y ∈ Y such that (x,y) ∈ R. x is called pre-image and y is called image of function f.
A function can be one to one, many to one (not one to many). A function f: A→B is said to be invertible if there exists a function g: B→A

Injective / One-to-one function
A function f: A→B is injective or one-to-one function if for every b ∈ B, there exists at most one a ∈ A such that f(s) = t.
This means a function f is injective if a1 ≠ a2 implies f(a1) ≠ f(a2).

Example
1. f: N →N, f(x) = 5x is injective.
2. f: Z+→Z+, f(x) = x² is injective.
3. f: N→N, f(x) = x ² is not injective as (-x)² = x²

Surjective / Onto function
A function f: A →B is surjective (onto) if the image of f equals its range. Equivalently, for
every b ∈ B, there exists some a ∈ A such that f(a) = b. This means that for any y in B,
there exists some x in A such that y = f(x).
Example
1. f : Z+→Z+, f(x) = x² is surjective.
2. f : N→N, f(x) = x² is not injective as (-x)² = x²
Bijective / One-to-one Correspondent
A function f: A →B is bijective or one-to-one correspondent if and only if f is both injective
and surjective.

Problem:
Prove that a function f: R→R defined by f(x) = 2x – 3 is a bijective function.

Explanation: We have to prove this function is both injective and surjective.
If f(x1) = f(x2), then 2x1 – 3 = 2x2 – 3 and it implies that x1 = x2.
Hence, f is injective.
Here, 2x – 3= y
So, x = (y+5)/3 which belongs to R and f(x) = y.
Hence, f is surjective.
Since f is both surjective and injective, we can say f is bijective.

Composition of Functions
Two functions f: A→B and g: B→C can be composed to give a composition g o f. This is a
function from A to C defined by (gof)(x) = g(f(x))

Example
Let f(x) = x + 2 and g(x) = 2x, find ( f o g)(x) and ( g o f)(x)

Solution
(f o g)(x) = f (g(x)) = f(2x) = 2x+2
(g o f)(x) = g (f(x)) = g(x+2) = 2(x+2)=2x+4
Hence, (f o g)(x) ≠ (g o f)(x)

Some Facts about Composition
* If f and g are one-to-one then the function (g o f) is also one-to-one.
* If f and g are onto then the function (g o f) is also onto.
* Composition always holds associative property but does not hold commutative property.