Introduction to Combinatorics

Prepared by:
Isra Elamin
Lecturer in Computer Science Dept.
 Types of Combinatorics
 Combinatoics is concerned with the study of arrangements, patterns,
designs, assignments, schedules, connections and configurations.
 There are three basic problems of combinatorics:
1. Existence Problem: Is there at least one arrangement of a particular kind?
2. Counting Problem: How many arrangements are there?
3. Optimization Problem: is concerned with choosing the best among all
possible arrangements according to some criterion.
SETS
 SETS
A set is a collection of well defined objects.

Some standard notations to represent sets :

N: the set of natural numbers W: the set of whole numbers

Z or I : the set of integers Z+ : the set of positive integers

Z- : the set of negative integers Q: the set of rational numbers

R: the set of real numbers C: the set of complex numbers

REPRESENTATION OF SETS
1. Roster method (Tabular form/ Enumerated Form)

In this method a set is represented by listing all its elements, separating these by commas

and enclosing these in curly bracket (elements are not to be repeated) .

(i) If V be the set of vowels of English alphabet, it can be written in Roster form as :
V = { a, e, i, o, u}.

(ii) If A be the set of natural numbers less than 7, then A={1, 2, 3, 4, 5, 6}, is in the Roster
form.

(iii) if A be the set of letters used in the word mathematics, then A = {m, a, t, h, e, i, c, s}.
REPRESENTATION OF SETS
2. Set-builder form
In this form elements of the set are not listed but these are represented by some
common property.
(i) Let V be the set of vowels of English alphabet then V can be written in the set
builder form as:
V = {x : x is a vowel of English alphabet}
(ii) Let A be the set of natural numbers less than 7.
then A = {x : x  N and 1  x < 7}
Note : Symbol ':' read as 'such that'
Membership
 Membership means that an element is a member of a set.

 If D= {x: x is an integer, 5<x<10} then:

 6 is a member of D.

 6 belong to D.

 It is written as : 6 ∈ D

 While 5 ∉ D denote that 5 is not a member of D.

CLASSIFICATION OF SETS
1. Finite and infinite sets

Let A and B be two sets where: A = {x : x is a natural number}

B = {x : x is a student of your university}

As it is clear that the number of elements in set A is not finite (infinite) while number of
elements in set B is finite. A is said to be an infinite set and B is said to be is finite set.

A set is said to be finite if its elements can be counted and it is said to be infinite if it is
not possible to count up to its last element.
CLASSIFICATION OF SETS
2.Empty (Null) Set

A set without members/elements is said to be an empty set, denoted by Ø.

Ø = { }

Ø is a subset of any other set.

Let S= { x1 x is an integer, x<5 , x>10} = { } = Ø

There is no such number which is less than 5 and greater than 10. Such a set is
said to be a null (empty) set.
CLASSIFICATION OF SETS
3. Singleton Set

 Consider the following set :

A = {x : x is an even prime number}

 As there is only one even prime number namely 2, so set A will have only one element.
Here A = {2}.

 Such a set is said to be singleton.

 A set which has only one element is known as singleton.

 CLASSIFICATION OF SETS
4. Equal and equivalent sets

 Consider the following Sets:

A={1,2,3}
B={2,1,3}
D={1,2,3}
E={a , b , c}
(i) Sets A and B have the same elements. Such sets are said to be equal sets and it is
written as A = B.
(ii) set D and E have the same number of elements but elements are different. Such sets
are said to be equivalent sets and are written as D  E.
CLASSIFICATION OF SETS
4. Equal and equivalent sets (Cont…)

Two sets A and B are said to be equivalent sets if they have same number
of elements but they are said to be equal if they have not only the same
number of elements but elements are also the same.
CLASSIFICATION OF SETS
5. Disjoint Sets

 Two sets are said to be disjoint if they do not have any common element.

 Consider sets A= {1,3,5} and B = { 2,4,6 } are disjoint sets.

SUBSETS
 Let set A be a set containing all students of your university and B be a set containing all
students of class 5 of the school. In this example each element of set B is also an element of set
A. Such a set B is said to be subset of the set A. It is written as B  A

 Consider D = {1, 2, 3, 4,........}

E = {..... -3, -2, -1, 0, 1, 2, 3,.......}

 Clearly each element of set D is an element of set E also so D  E.

 If A and B are any two sets such that each element of the set A is an element of the set B also,
then A is said to be a subset of B.
SUBSETS
Remarks
 Each set is a subset of itself i.e. A  A.
 Null set has no element so the condition of becoming a subset is
automatically satisfied. Therefore null set is a subset of every set.
 If A  B and B  A then A = B.
 If A  B and A  B then A is said to be a proper subset of B and B is said to be a super

set of A. i.e. A  B or B  A .
Cardinality of Sets
Definition

Let S be a set. If there are exactly n distinct elements in S where n is a

nonnegative integer, we say that S is a finite set and that n is the
cardinality of S. The cardinality of S is denoted by |S|.

 Remark: The term cardinality comes from the common usage of the
term cardinal number as the size of a finite set.
Cardinality of Sets
Example

 Let A be the set of odd positive integers less than 10. Then |A| = 5.

Example

Let S be the set of letters in the English alphabet. Then |S| = 26.

Example

Because the null set has no elements, it follows that |∅| = 0.

POWER SET
 Let A = {a, b}

 Subset of A are f , {a}, {b} and {a, b}.

 If we consider these subsets as elements of a new set P(A) (say) then

 P(A) ={f, {a}, {b}, {a,b} }

 P(A) is said to be the power set of A.

UNIVERSAL SET
 Consider the following sets:

A = {x : x is a student of your university}

B = {y : y is student of class 3 in your university}

C = {z : z is student of class 5 in your university}

D = {a : a is a student of class 7 in your university}

 Clearly the set B, C, D are all subsets of A.

 UNIVERSAL SET
 A can be considered as the universal set for this particular example. Universal set is
generally denoted by U.

 In a particular problem a set U is said to be a universal set if all the sets in that problem
are subsets of U.

Remarks

(i) Universal set does not mean a set containing all objects of the universe.

(ii) A set which is a universal set for one problem may not be a universal set for another
problem.
VENN DIAGRAM
British mathematician John Venn (1834 1883 AD) introduced the concept of
diagrams to represent sets. According to him universal set is represented by the
interior of a rectangle and other sets are represented by interior of circles.

Diagrammatical representation of sets is known as a Venn diagram.

VENN DIAGRAM
For example if U= {1, 2, 3, 4, 5}, A = {2, 4} and B = {1,3}, then these sets can be
represented as:
 DIFFERENCE OF SETS
Consider the sets

A = {1, 2, 3, 4, 5} and B= {2, 4, 6}.

A new set having those elements which are in A but not B is said to be the difference of sets A and B and
it is denoted by A-B.

A -B= {1, 3, 5}

Similarly a set of those elements which are in B but not in A is said to be the difference of B and A and it
is denoted by B - A.

B - A = {6}
DIFFERENCE OF SETS
In general, if A and B are two sets then:

A-B = { x : x  A and x B }

B-A = { x : x  B and x A }

Difference of two sets can be represented using Venn diagram as :

COMPLEMENT OF A SET
If U is the universal set and A is its subset then the complement of A is a set of those
elements which are in U which are not in A. It is denoted by A' or Ac.

A' = U-A = {x : x U and xA}

The complement of a set can be represented using Venn diagram as :

Remarks
Difference of two sets can be found even if none is a subset of the other but
complement of a set can be found only when the set is a subset of some
universal set.

 fc =U. (iii) Uc = f.
INTERSECTION OF SETS
 Consider the sets: A = {1, 2, 3, 4} and B = { 2, 4, 6}

 Set of these common elements is said to be intersection of A and B and is denoted by

A B .

 Here A  B = {2, 4 }

 If A and B are two sets then the set of those elements which belong to both the sets is
said to be the intersection of A and B. It is denoted by A  B .

A  B = {x : x  A and x  B}
INTERSECTION OF SETS
A  B can be represented using Venn diagram as :
Remarks
If A  B= f then A and B are said to be disjoint sets. In Venn diagram disjoint
sets can be represented as:
UNION OF SETS
 If A and B are only two sets then union of A and B is the set of those elements
which belong to A or B.
 In set builder form :
A  B = {x : x A or xB}
OR
A  B = {x : x A -B or x  B -A or x  A  B }
UNION OF SETS
 A  B can be represented using Venn diagram as :
CARTESIAN PRODUCT OF TWO SETS
 Consider two sets A and B where
A={1, 2}, B= {3, 4, 5}.
Set of all ordered pairs of elements of A and B This set is denoted
by A ×B and is called the Cartesian product of sets A and B.
i.e. A×B ={(1, 3), (1, 4),(1, 5),(2, 3),(2, 4),(2, 5)}
 Cartesian product of B sets and A is denoted by A×B.
CARTESIAN PRODUCT OF TWO SETS
 In the present example, it is given by:
B×A = {(3, 1),(3, 2),(4, 1),(4, 2),(5, 1),(5, 2)}
 Clearly A×B  B×A.
 In the set builder form :
A×B = {(a,b) : a  A and b  B }
B×A = {(b,a) : b  B and a  A }
 Note : If A = f or B = f or A,B = f then A×B = B×A = f.
RELATIONS AND FUNCTIONS
 RELATIONS
 Consider the following example : A={Mohamed, Ahmed, Ali, Hassan}
B={Reem, Mariam, Fatima}
 Suppose Reem has two brothers Mohamed and Ahmed, Mariam has one brother Ali, and
Fatima has one brother Hassan. If we define a relation R " is a brother of" between the
elements of A and B then clearly:
Mohamed R Reem, Ahmed R Reem, Ali R Mariam, Hassan R Fatima.
 After omitting R between two names these can be written in the form of ordered pairs as :
(Mohamed, Reem), (Ahmed, Reem), (Ali, Mariam), (Hassan, Fatima).
 The above information can also be written in the form of a set R of ordered pairs as:
R= {(Mohamed, Reem), (Ahmed, Reem), (Ali, Mariam), (Hassan, Fatima)}
RELATIONS
 Clearly R  A×B, i.e. R = {(a,b): aA, bB and aRb}
 If A and B are two sets then a relation R from A to B is a sub set of A×B.
 If (i) R = f, R is called a void relation.
(ii) R=A×B, R is called a universal relation.
(iii) If R is a relation defined from A to A, it is called a relation defined on A.
(iv) R = { (a,a) " a  A } , is called the identity relation.
Domain and Range of a Relation
 If R is a relation between two sets then the set of its first elements (components)
of all the ordered pairs of R is called Domain and set of second elements of all
the ordered pairs of R is called range, of the given relation.

Consider previous example given above.

Domain = {Mohamed, Ahmed, Ali, Hassan}

Range = {Reem, Mariam, Fatima}

 Example
Given that A = {2, 4, 6}, B = {2, 3}.

R is a relation from A to B defined by: R = {(a, b) : a  A, b  B and a is divisible by b}

Find:

(i) R in the roster form

(ii) Domain of R

(iii) Range of R

(iv) Represent R diagrammatically.

 Solution
(i) R = {(2, 2), (4, 2), (6, 2), (6, 3)}

(ii) Domain of R = {2, 4, 6}

(iii) Range of R = {2, 3}

(iv)
2
4 2

6 3
Example
If R is a relation 'is greater than' from A to B, where:

A= {2, 3, 4, 5} and B = {1,2}.

Find:

(i) R in the roster form.

(ii) Domain of R.
(iii) Range of R.
(iv) Represent R diagrammatically.
 Solution
(i) R = {(2,1),(3, 1), (3, 2), (4, 1), (4, 2), (5, 1), (5, 2)}

(ii) Domain of R = {2, 3, 4, 5}

(iii) Range of R = {1, 2}

2
1
3
4
2
5
FUNCTIONS
 Consider the relation:

f : {(a, 1), (b, 2), (c, 3), (d, 5)}

 In this relation we see that each element of A has a unique image in B.

This relation f from set A to B where every element of A has a unique image in B is
defined as a function from A to B.

 So in a function no two ordered pairs have the same first element.

FUNCTIONS
 We also see that $ an element  B, i.e., 4 which does not have its pre image in A.
Thus here:

(i) the set B will be termed as co-domain and

(ii) the set {1, 2, 3, 5} is called the range.

 From the above we can conclude that range is a subset of co-domain.

 Symbolically, this function can be written as: f : A  B.

CLASSIFICATION OF FUNCTIONS
 Let f be a function from A to B. If every element of the set B is the image
of at least one element of the set A i.e. if there is no unpaired element in
the set B then we say that the function f maps the set A onto the set B.
Otherwise we say that the function maps the set A into the set B.

Functions for which each element of the set A is mapped to a different

element of the set B are said to be one-to-one.
CLASSIFICATION OF FUNCTIONS
 One-to-one function

The domain is { A , B , C}

The co-domain is {1, 2 , 3 , 4}

The range is {1,2,3}

CLASSIFICATION OF FUNCTIONS
 A function can map more than one element of the set A to the same
element of the set B. Such a type of function is said to be many-to-one.

 The domain is { A , B , C}

 The co-domain is {1, 2 , 3 , 4}

 The range is {1, 4 }

CLASSIFICATION OF FUNCTIONS
 A function which is both one-to-one and onto is said to be a bijective function.

 Fig. 1 shows a one-to-one function mapping

A , B , C into 1, 2 , 3 , 4 .
 Fig. 2 shows a one-to-one function mapping
A , B , C onto 1,2,3 .
 Fig. 3 shows a many-to-one function mapping
A , B , C into 1, 2 , 3 , 4 .
 Fig. 4 shows a many-to-one function mapping
A , B , C onto 1, 2.
Note
 Relations which are one-to-many can occur, but they are not functions.
The following figure illustrates this fact.