Transcript Basic Combinatorics

What is Probability?
• Quantification of uncertainty.
• Mathematical model for things that occur randomly.
• Random – not haphazard, don’t know what will happen on
any one experiment, but has a long run order.
• The concept of probability is necessary in work with physical
biological or social mechanism that generate observation that
can not be predicted with certainty. Example…
• The relative frequency of such ransom events with which they
occur in a long series of trails is often remarkably stable.
Events possessing this property are called random or
stochastic events
week 1
1
Relative Frequency
• The relative frequency concept of probability does not provide
a rigorous definition of probability.
• For our purpose, an interpretation based on relative frequency
is a meaningful measure of out belief in the occurrence of the
event.
• Relative frequency = proportion of times the even occurs.
• Goal: present an introduction to the theory of probability,
which provides the foundation for modern statistical inference.
week 1
2
Basic Set Theory
• A set is a collection of elements. Use capital letters, A, B, C to
denotes sets and small letters a1, a2, … to denote the elements
of the set.
• Notation: a1  A means the element a1 is an element of the set A
A = {a1, a2, a3 }.
• The null, or empty set, denoted by Ф, is the set consisting of no
points. Thus, Ф is a sub set of every set.
• The set S consisting of all elements under consideration is called
the universal set.
week 1
3
Relationship Between Sets
• Any two sets A and B are equal if A and B has exactly the
same elements. Notation: A=B.
• Example: A = {2, 4, 6}, B = {n; n is even and 2 ≤ n ≤ 6}
• A is a subset of B or A is contained in B, if every point in A is
also in B. Notation: A  B
• Example: A = {2, 4, 6}, B = {n; 2 ≤ n ≤ 6} = {2, 3, 4, 5, 6}
week 1
4
Venn Diagram
• Sets and relationship between sets can be described by using
Venn diagram.
• Example: We toss a fair die. What is the universal set S? …
week 1
5
Union and Intersection of sets
• The union of two sets A and B, denoted by A  B, is the set of all
points that are in at least one of the sets, i.e., in A or B or both.
•
Example 1: We toss a fair die…
• The intersection of two sets A and B, denoted by A  B or AB, is
the set of all points that are members of both A and B.
• Example 2: The intersection of A and B as defined in example 1
is …
week 1
6
Properties of unions and intersections
Unions and intersections are:
• Commutative, i.e., AB = BA and A  B  B  A.
• Associative, i.e., A  B  C    A  B  C
• Distributive, i.e., A  B  C    A  B   A  C 
A  B  C    A  B   A  C 
• These laws also apply to arbitrary collections of sets (not just
pairs).
week 1
7
Disjoint Events
• Two sets A and B are disjoint or mutually exclusive if they
have no points in common. Then A  B   .
• Example 3: Toss a die. Let A = {1, 2, 3} and B = {4, 5}.
week 1
8
Complement of a Set
• The complement of a set, denoted by Ac or A’ makes sense
only with respect to some universal set. Ac is the set of all
points of the universal set S that are not in A.
• Example: the complement of set A as defined in example 3
is…
• Note: the sets A and Ac are disjoint.
week 1
9
De Morgan’s Laws
• For any two sets A and B:
 A  B C
 A  B C
 AC  B C
 AC  B C
• For any collection of sets A1, A2, A3, … in any universal set S
C



C
  An     An 
n 1
 n 1 
week 1
10
Finite, Countable Infinite and Uncountable
• A set A is finite if it contains a finite number of elements.
• A set A is countable infinite if it can be put into a one-to-one
correspondence with the set of positive integers N.
• Example: the set of all integers is countable infinite because …
• The whole interval (0,1) is not countable infinite, it is
uncountable.
week 1
11
The Probability Model
• An experiment is a process by which an observation is made.
For example: roll a die 6 times, toss 3 coins etc.
• The set of all possible outcomes of an experiment is called the
sample space and is denoted by Ω.
• The individual elements of the sample space are denoted by ω
and are often called the sample points.
• Examples ...
• An event is a subset of the sample space. Each sample point is
a simple event.
• To define a probability model we also need an assessment of
the likelihood of each of these events.
week 1
12
σ – Algebra
• A σ-algebra, F, is a collection of subsets of Ω satisfying the
following properties:
 F contains Ф and Ω.
 F is closed under taking complement, i.e., A  F  AC  F .
 F is closed under taking countable union, i.e.,
A1 , A2 ,...  F  A1  A2  ...  F
• Claim: these properties imply that F is closed under countable
intersection.
• Proof: …
week 1
13
Probability Measure
A probability measure P mapping F  [0,1] must satisfy
• For A  F, P(A) ≥ 0 .
• P(Ω) = 1.
• For A1 , A2 , A3 ,...  F , where Ai are disjoint,
P A1  A2  A3  ...  P A1   P A2   P A3   
This property is called countable additivity.
• These properties are also called axioms of probability.
week 1
14
Formal Definition of Probability Model
• A probability space consists of three elements (Ω, F, P)
(1) a set Ω – the sample space.
(2) a σ-algebra F - collection of subsets of Ω.
(3) a probability measure P mapping F  [0,1].
week 1
15
Discrete Sample Space
• A discrete sample space is one that contains either a finite or a
countable number of distinct sample points.
• For a discrete sample space it suffices to assign probabilities to
each sample point.
• There are experiments for which the sample space is not
countable and hence is not discrete. For example, the
experiment consists of measuring the blood pressure of
patients with heart disease.
week 1
16
Calculating Probabilities when Ω is Finite
• Suppose Ω has n distinct outcomes, Ω = {ω1, ω2,…, ωn}. The
probability of an event A is P A   Pi 
i A
• In many situations, the outcomes of Ω are equally likely,
1


P


.
then,
i
n
1
• Example, when rolling a die Pi   for i = 1, 2, …, 6.
6
• In these situations the probability that an event A occurs is
P A 
# of outcomes for which A occurs na

n
n
• Example:
week 1
17
Basic Combinatorics
• Multiplication Principle
Suppose we are to make a series of decisions. Suppose there are c1
choices for decision 1 and for each of these there are c2 choices for
decision 2 etc. Then the number of ways the series of decisions can
be made is c1·c2·c3···.
• Example 1:
Suppose I need to choose an outfit for tomorrow and I have 2 pairs
of jeans to choose from, 3 shirts and 2 pairs of shoes that matches
with this shirts. Then I have 2·3·2 = 12 different outfits.
week 1
18
• Example 2:
The Cartesian product of sets A and B is the set of all pairs (a,b) where
a  A, b B. If A has 3 elements (a1,a2,a3) and B has 2 elements (b1,b2),
then their Cartesian product has 6 members; that is
A  B = {(a1,b1), (a1,b2), (a2,b1), (a2,b2), (a3,b1), (a3,b2)}.
• Example 3:
The number of subsets of a set of size n is 2n. E.g. if A = (a1,a2) then all the
possible subsets of A are: {a1}, {a2}, {a1,a2}, .

• Exercises: 2.30, 2.42 in textbook.
• Some more exercise:
1. We toss R different dies, what is the total number of possible outcome?
2. How many different digit numbers can be composed of the digits 1-7 ?
3. A questioneer consists of 5 questions: Gender (f / m), Religion
(Christian, Muslim, Jewish, Hindu, others), living arrangement
(residence, shared apartment, family), speak French (yes / no), marital
status. In how many possible ways this questioneer can be answered?
week 1
19
Permutation
• An order arrangement of n distinct objects is called a permutation.
• The number of ordered arrangements or permutation of n objects is
n! = n · (n – 1) · (n – 2) · · ·1 (“n factorial”).
• By convention 0! = 1.
• The number of ordered arrangements or permutation of k subjects selected
from n distinct objects is n · (n – 1) · (n – 2) · · · (n – k +1). It is also the
number of ordered subsets of size k from a set of size n. Notation:
Pkn  n  (n  1)  (n  2)    (n  k  1) 
n!
(n  k )!
• Example: n = 3 and k = 2
• The number of ordered arrangements of k subjects selected with
replacement from n objects is n k.
week 1
20
Examples
1.
How many 3 letter words can be composed from the English Alphabet s.t:
(i) No limitation
(ii) The words has 3 different letters.
2.
How many birthday parties can 10 people have during a year s.t.:
(i) No limitation
(ii) Each birthday is on a different day.
3.
10 people are getting into an elevator in a building that has 20 floors.
(i) In how many ways they can get off ?
(ii) In how many ways they can get off such that each person gets off on a
different floor ?
4.
We need to arrange 4 math books, 3 physics books and one statistic book on
a shelf.
(i) How many possible arrangements exists to do so?
(ii) What is the probability that all the math books will be together?
week 1
21
Combinations
•
•
The number of subsets of size k from a set of size n when the order does not
matter is denoted by  n  or C kn (“ n choose k”) .
 
k 
The number of unordered subsets of size k selected (without replacement) from n
available objects is
n
n!
  
 k  k!(n  k )!
Important facts:
n n
       1
0 n
n  n 
  n
    
1
n

1
  

n  n 

    
k  n  k 
•
Exercise: Prove the above.
week 1
22
Examples
1.
Exercise 2.54 from the textbook
2.
Exercise 2.55 from the textbook
3.
Exercise 2.56 from the textbook
4.
We need to select 5 committee members form a class of 70 students.
(i) How many possible samples exists?
(ii) How many possible samples exists if the committee members all have
different rules?
week 1
23
The Binomial Theorem
• For any numbers a, b and any positive integer n
a  b 
n
 n  i n i
   a b
i 0  i 
n
• The terms  n  are referred to as binomial coefficient .
 
k 
week 1
24
Multinomial Coefficients
• The number of ways to partitioning n distinct objects into k
distinct groups containing n1, n2,…,nk objects respectively,
k
where each object appears in exactly one group and  ni  n is
n


n!

 
 n1 n2 ... nk  n1!n2 !  nk !
i 1
• It is called the multinomial coefficients because they occur in
the expansion
n
a1  a2      ak 
n

 n1 n2
a1 a 2    a knk
  
 n1 n2    nk 
k
ni
Where the sum is taken over all ni = 0,1,...,n such that 
i 1
week 1
n
25
Examples
1.
A small company gives bonuses to their employees at the end of the year.
15 employees are entitled to receive these bonuses of whom 7 employees
will receive 100$ bonus, 3 will receive 1000$ bonus and the rest will
receive 3000$ bonus.
In how many possible ways these bonuses can be distributed?
2.
We need to arrange 5 math books, 4 physics books and 2 statistic book on
a shelf.
(i) How many possible arrangements exists to do so?
(ii) How many possible arrangements exists so that books of the same
subjects will lie side by side?
week 1
26
Rules of Probability
•
PA   1  P A
for all A F.
• Corollary: P  0.
• The probability of the union of any two events A and B is
P A  B  P A  PB  P A  B
Proof: …
• If A  B then, P A  PB.
Proof:
week 1
27
• Inclusion / Exclusion formula:
For any finite collection of events A1 , A2 ,..., An
 n
 n
n 1
P  Ai    P Ai    PAi  A j    PAi  A j  Ak      1 P A1  A2     An 
i j
i  j k
 i 1  i 1
• For any finite collection of events A1 , A2 ,..., An
 n
 n
P  Ai    P Ai 
 i 1  i 1
Proof: By induction
week 1
28