Notes

Power set: P(A):
Set of all subsets of a set A, denoted by P(A).
Ex: Find the power set of A={1,0,-1}
Cartesian Product: A cross B (AXB)
AXB={(a,b)/ a ЄA and bЄB }
Ex: Let A={x,y} and B={1,2,3} and C={ a,b}
a) Find AXB b) AXBXC
AXB={ (x,1),(x,2), (x,3), (y,1), (y,2), (y,3)}
Ex: Let A={nЄZ| n=2p, for some integer p}
B={ Set of all EVEN integers}
D={ kЄZ| k=3r+1, for some integers r}
a) Is A=B b) Is A=D Justify with reasons.
SET BUILDER FORM

Ex2: Write the following set in set builder form:
A={ 1,4,9,16,25,………}

HW:
1) Write the following set in set builder form:
B={ 2, 4, 6, 8, 10, 12, …….}
C={1,8, 27, 64,………..}










COUNTING AND PROBABILITY

1 2 3 4 5 6 7
SUN MON TUE WED THU FRI SAT

SAMPLE SPACE: A set of all possible outcomes of a random process or experiment.
EVENT: An event is a subset of a sample space.
Equally likely probability formula:
S is finite sample space. E is an event.
Probability P(E) : number of outcomes in E/total number of outcomes in S
P(E)=N(E )/N(S)
COUNTING THE ELEMENTS OF A LIST:
How many integers are there from 5 to 12?
List: 5 6 7 8 9 10 11 12
Count: 1 2 3 4 5 6 7 8
Answer is 8

Example1:
a) How many two digit integers (integers from 10 to 99 inclusive) are divisible by 5?
b) What is the probability that a randomly chosen two-digit integer is divisible by 5?

Example2:
c) How many two digit integers (integers from 10 to 99 inclusive) are divisible by 3?
d) What is the probability that a randomly chosen two-digit integer is divisible by 3?
Example3: Home Work
e) How many three digit integers (integers from 100 to 999 inclusive) are divisible by 6?
f) What is the probability that a randomly chosen three-digit integer is divisible by 6?
Example4:
g) How many two digit integers (integers from 10 to 99 inclusive) are divisible by 4?
h) What is the probability that a randomly chosen two-digit integer is divisible by 4?

Ex: A coin was tossed twice. What is the probability of obtaining
A head and a tail.
H means Head
T means Tail.
Write all the possible sample space.
What is the probability of obtaining a head?
What is the probability of obtaining a tail?
Ex: Two coins were tossed. Write all the sample space.
a) What is the probability of obtaining exactly one head?
b) What is the probability of obtaining exactly one tail?
c) What is the probability of obtaining exactly two head?
d) What is the probability of obtaining at least one head?
HW
Ex1: Suppose that a coin is tossed three times and the side showing face upon each toss is noted. Suppose also that on each toss heads and tails are equally likely. Let HHT indicate the outcome heads on the first two tosses and tails on the third, THT the outcome tails on the first and third tosses and heads on the second, and so forth.
a) List the eight elements in the sample space whose outcomes are all possible head-tail sequences obtained in the three tosses.
b) Write each of the following event as a set and find its probability:
i) The event that exactly one toss results in a head.
ii) The event that at least two tosses result in a head.
iii) The event that no head is obtained.
Ex2: Three people have been exposed to a certain illness. Once exposed, a person has a 50-50 chance of actually becoming ill.
XX)Write all the sample space for the above.
a.) What is the probability that exactly one of the people becomes ill?
b.) What is the probability that at least two of the people become ill?
c.) What is the probability that none of the three people/ becomes ill?
d.) HW
Ex3: Suppose that each child born is equally likely to be boy or a girl. Consider a family with exactly three children. Let BBG indicate that the first two children born are boys and the third child is a girl, let GBG indicate that the first and third children born are girls and the second is a boy, and so forth.
a.) List the eight elements in the sample space whose outcomes
are all possible genders of the three children.
b.) Write each of the following events as a set and find its probability.
i)The event that exactly one child is a girl.
ii)The event that at least two children are girls.
iii)The event that no child is a girl.


Permutations:
A permutation of a set of objects is an ordering of the objects in a row. For example the set {a, b, c} has six permutations.
abc acb cba bac bca cab

Theorem: For any integer n>=1, the number of permutations of a set of n elements is n!
n!=n(n-1)(n-2)….3.2.1
Ex1: a.) How many ways can the letters in the word COMPUTER be arranged in a row?
b.) How many ways can the letters in the word COMPUTER be arranged if the letters CO must remain next to each other (in order) as a unit?
c.) If the letters of the word COMPUTER are randomly arranged in a row, what is the probability that the letters CO remain next to each other (in order) as a unit?

r-permutations
: r-permutation of a set of n elements is an ordered selection of r elements taken from the set of n elements.
P(n,r)=n!/(n-r)!
Ex1: a.) Evaluate P(5,2)
b.)How many 4-permutations are there of a set of seven objects?
c.) How many 5-permutations are there of a set of five objects?
Ex2: a.) How many different ways can three of the letters of the word BYTES be chosen and written in a row?
b.)How many different ways can this be done if the first letter must be B?
c.) How many different ways can this be done if the first two letter must be BY?

Ex3: Prove that for all integers n>=2, P(n,2)+P(n,1)=n2







HW
i)Evaluate: a.)P(6,4) b.) P(6,6) c.)P(6,3) d.)P(6,1)
A) How many 3-permutations are there of a set of five objects?
B) How many 2-permutations are there of a set of eight objects?
Ex4 a.) How many ways can three of the letters of the word ALGORITHM be selected and written in a row?
b.)How many ways can six of the letters of the word ALGORITHM be selected and written in a row?
c.)How many ways can six of the letters of the word ALGORITHM be selected and written in a row if the first letter must be A?
d.) How many ways can six of the letters of the word ALGORITHM be selected and written in a row if the first two letter must be OR?
EX5: Prove that for all integers n>=2, P(n+1,3)=n3-n
HW
1) Prove that for all integers n>=2, P(n+1,3)-P(n,3)=3P(n,2)
2) Prove that for all integers n>=2, P(n+1,2)-P(n,2)=2P(n,1)
3) How many ways can the letters of the word QUICK be arranged in a row?


COMBINATION
R-COMBINATION: C (n, r) = n! / r! (n-r)!
Ex1: Compute C(8,5)

Ex2: Consider a problem of choosing 5 members from a group of 12 members to work as a team on a special project. How many distinct 5 person team can be chosen?
Ex3: How many eight-bit strings have exactly three 1's ?

Ex4: Consider various ways of ordering the letters in the word MISSISSIPPI:
IIMSSPISSIP, ISSSPMIIPIS , PIMISSSSIIP , and so on.
How many distinguishable orderings are there?
HW
EX1: A computer Programming team has 13 members.
a.) How many ways can a group of seven be chosen to work on a project?
b.) Suppose seven team members are women and six are men. How many groups of seven can be chosen that contain four women and three men?
RECURSION
A recurrence relation for a sequence a0 , a1 , a2 , ….is a formula that relates each term ak to certain of its predecessors ak-1 , ak-2 , …..

EX1: Define a sequence c0 , c1 , c2 ,…..recursively as follows: For all integers k>=2,
i.) Ck = ck-1 + kck-2 + 1 recurrence relation
ii.) C0 = 1 and c1 = 2 initial conditions.
Find c2 , C3 , and c4 .

Ex2: Find the first four terms of each of the recursively defined sequences:
a) Ak = 2ak-1 + k , for all integers k>=2 where a1=1.
b) Bk = bk-1 + 3k , for all integers k>=2 where k>=2.
c) Ck = k( ck-1)2 , for all integers k>=1 where c0=1
d) Dk=k(dk-1)2 , for all integers k>=1 where d0=3
e) Sk = sk-1 + 2sk-2 , for all integers k>=2 where s0=1, s1=1
f) Tk = tk-1 + 2tk-2 , for all integers k>=2 where t0=-1 , t1=2m ,,,,,,,



Ex1: Write the Fibonacci series which satisfies the following
Recurrence relation:
Fk = Fk-1 + Fk-2 recurrence relation
Where F0 = 0 and F1 = 1
Compute the series F2 , F3 , F4 , …….
Explicit Formulae:
Ex2: Find the explicit formula for the following sequence:
j) 1 , 4 , 9 , 16 , ……
k) 2 , 5 , 10 , 17 , ….
l) 1 , 8 , 27 , 64 , ……
m) 1 , -1 , 1 , -1 , 1 , -1 ,……

Graphs and Trees
Graph: A graph consists of two finite sets:
V(G) set of vertices and E(G) set of edges
A graph with no vertices is called Empty graph.
A vertex on which no edges are incident is called isolated.
a)
Edge Endpoints
E1 {v1 , v2}
E2 {v1 , v3}
E3 {V3}




b)
Edge Endpoints
E1 {V1 , V2}
E2 {V1 , V3}
E3 {V1 , V3}
E4 {V1 , V3}






Ex2: Consider the graph specified as follows:
V(G)={v1 , v2 , v3 , v4 }
E(G) = {e1 , e2 , e3 , e4 }
Edge-endpoint function:


Edge Endpoints
E1 {v1 , v3 }
E2 {v2 , v4 }
E3 { v2 , v4 }
E4 {v3}






Draw the pictorial representation of this graph.