Transcript counting_old - Lyle School of Engineering

EMIS 7370/5370 STAT 5340
NTU MA-520-N
Probability and Statistics for Scientists and Engineers
Probability
Counting Techniques
UPDATED 9/8/03
Dr. Jerrell T. Stracener,
SAE Fellow
1
Counting Techniques
• Product Rule
• Tree Diagram
• Permutations
• Combinations
2
Product Rule
• Rule
If an operation can be performed in n1 ways, and if for each of
these a second operation can be performed in n2 ways, then the
two operations can be performed in n1n2 ways.
• Rule
If an operation can be performed in n1 ways, and if for each of
these a second operation can be performed in n2 ways, and for
each of the first two a third operation can be performed in n3
ways, and so forth, then the sequence of k operation can be
performed in n1, n2, …, nk ways.
3
Tree Diagrams:
Definition:
A configuration called a tree diagram can be used to represent
pictorially all the possibilities calculated by the product rule.
Example:
A general contractor wants to select an electrical contractor and a
plumbing contractor from 3 electrical contractors, and 2 plumbing
contractors. In how many ways can the general contractor choose
the contractor?
4
Tree Diagrams:
Selection
Plumbing
Contractors
P1
P2
Electrical
Contractors
Outcome
E1
E2
P1E1
P1E2
E3
P1E3
E1
E2
P2E1
P2E2
E3
P2E3
By observation there are 6 ways for the contractor to choose
the two subcontractors. Using the product rule, the number is
2x3=6
5
Tree Diagrams:
Selection
Plumbing
Contractors
E1
E2
E3
Electrical
Contractors
Outcome
P1
E1P1
P2
P1
E1P2
E2P1
P2
P1
P2
E2P2
E3P1
E3P2
6
Factorial:
• Definition:
For any positive integer m, m factorial, denoted by
m!, is defined to be the product of the first m positive integers, i.e.,
m! = m(m - 1)(m - 2) ... 3  2  1
Rules:
0! = 1
m! = m(m - 1)!
7
Permutations:
• Definition
A permutation is any ordered sequence of k objects taken from a
set of n distinct objects
• Rules
The number of permutations of size k that can be constructed from
n distinct objects is:
n
Pk  n(n  1)(n  2)...( n  k  2)(n  k  1)
n!
n Pk 
(n  k )!
8
Combinations:
• Definition
A combination is any unordered subset of size k taken
from a set of n distinct elements.
• Rules
The number of combinations of size k that can be formed
from n distinct objects is:


 n
n!
  n Ck 
k!(n  k )!
k 
 n  n Pk
  
 k  k!
9
Example:
Five identical size books are available for return to the
book shelf. There are only three spaces available. In how many
ways can the three spaces be filled?
Example:
Five different books are available for weekend reading.
There is only enough time to read three books. How many
selections can be made?
10