Transcript Week1

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
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
2
• 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)}.
• Some more exercise:
1. We toss R different die, 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
3
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
4
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
5
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
6
Example
•
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
7
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
8
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
9
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
10