Transcript Permutations and Combinations - Sys

Permutations and Combinations
Permutation: The number of ways in which a subset of
objects can be selected from a given set of objects, where
order is important.
Given the set of three letters, {A, B, C}, how many possibilities
are there for selecting any two letters where order is
important?
(AB, AC, BC, BA, CA, CB)
Combination: The number of ways in which a subset of
objects can be selected from a given set of objects, where
order is not important.
Given the set of three letters, {A, B, C}, how many possibilities are there
for selecting any two letters where order is not important?
(AB, AC, BC).
Definition of n Factorial (n !)
• n! = n(n – 1)(n – 2)(n – 3)…1
For example, 5! = 5(4)(3)(2)(1) = 120
• n! = n(n – 1)!
• 0! = 1 by definition.
• Most calculators have an n! key or the
equivalent.
• n! grows very rapidly, which may result
in overload on a calculator.
Example
Vasopressin* is a small polypeptide
composed of 9 amino acids in a particular
order. The order of these amino acids is of
critical to the proper functioning of
vasopressin. If these 9 amino acids were
placed in a hat and drawn out randomly one
by one, how many different arrangements of
these 9 amino acids are possible?
*Retains water in the body and constricts blood vessels
Solution
Solution: Let A, B, C, D, E, F, G, H, I symbolize the 9
amino acids. They must fill 9 slots:
___ ___ ___ ___ ___ ___ ___ ___ ___
There are 9 choices for the first position, leaving 8
choices for the second slot, 7 choices for the third
slot and so on. The number of different orderings is
9(8)(7)(6)(5)(4)(3)(2)(1) = 9! = 362,880
Number of Possible Proteins
Given 21 amino acids, how many different
dipeptides can be formed?
21 possibilities in there first position
21 possibilities in the second position
Therefore there are 21 x 21 = 441 permutations
Number of Possible Proteins in the Universe
Given 21 amino acids, how many different proteins
can be made that are 300
amino acids long?
21 possibilities in the first position
etc
Therefore there are
21300 = 4.6 x 10396 permutations
By comparison, the number of all atoms in the
observable universe is 1080
Permutations and Combinations
Factorial Formula for Permutations
The number of permutations, or arrangements, of n district things taken
r at a time, where r <= n, is calculated using the expression:
n!
.
n Pr 
(n  r )!
Factorial Formula for Combinations
The number of combinations, or subsets, of n district things taken
r at a time, where r <= n, is calculated using the expression:
n Pr
n!

.
n Cr 
r ! r !(n  r )!
Permutations and Combinations
Example How many ways can you order the 4 objects
{A, B, C, D}
Solution:
N = 4! = 4(3)(2)(1) = 24
Here are the orderings.
ABCD
ABDC
ACBD
ACDB
ADBC
ADCB
BACD
BADC
BCAD
BCDA
BDAC
BDCA
CABD
CADB
CBAD
CBDA
CDAB
CDBA
DABC
DACB
DBAC
DBCA
DCAB
DCBA
Permutations and Combinations
Example How many permutations of size 3 can be found in
the group of 5 objects {A, B, C, D, E}
Solution:
5!
= 5  4  3  60
5 P3 
 5  3 !
ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE
ACB
ADB
AEB
ADC
AEC
AED
BDC
BEC
BED
CED
BAC
BAD
BAE
CAD
CAE
DAE
CBD
CBE
DBE
DCE
BCA
BDA
BEA
CDA
CEA
DEA
CDB
CEB
DEB
DEC
CAB
DAB
EAB
DAC
EAC
EAD
DBC
EBC
EBD
ECD
CAB
DBA
EBA
DCA
ECA
EDA
DCB
ECB
EDB
EDC
Permutations and Combinations
Find the number of permutations of 8 elements taken 3 at a
time.
Find the number of permutations of the letters A, B, and C
Using Permutations and Combinations
A PhD examination includes 4 women and 3 male examiners.
How many ways can the be examiners be seated in a row of 7
chairs?
If the male and female examiners have to be seated
alternatively, how many combinations will there be?
Sit a male in the first seat, female next etc.
Using Permutations and Combinations
How many ways can you select two letters followed by three digits for
an ID if repeats are not allowed?
Two parts:
1. Determine the set of two letters. 2. Determine the set of three digits.
26P2
10P3
2625
1098
650
720
650720
468,000
Using Permutations and Combinations
Find the number of different
subsets of size 3 in the set:
{m, a, t, h, r, o, c, k, s}.
9C3
Find the number of arrangements
of size 3 in the set:
{m, a, t, h, r, o, c, k, s}.
9P3
987
504
84
Different subsets
arrangements
Using Permutations and Combinations
Assume a committee of n = 10 people and we want to choose
a chairperson, a vice-chairperson and a treasurer. Suppose
that 6 of the members of the committee are male and 4 of the
members are female. What is the probability that the three
executives selected are all male?
Solution: We select 3 persons (male and female) from the
committee of 10 in a specific order. (Permutations of size 3
from a group of 10).The total number of ways that this can be
done is:
10!
10!

= 10  9 8  720
10 P3 
10  3! 7!
This is the size, N = n(S), of the sample space S. Assume all
outcomes in the sample space are equally likely.
Using Permutations and Combinations
Let E be the event that all three executives are male (6 males in
total)
6!
6!
n  E   6 P3 
 = 6  5 4   120
 6  3! 3!
Hence
nE
120 1
PE 


n  S  720 6
Thus if all candidates are equally likely to be selected to any
position on the executive then the probability of selecting an
all male executive is:
1
6
Application to Lotto 6/49
Here you choose 6 numbers from the integers 1,
2, 3, …, 47, 48, 49.
Six winning numbers are chosen together with a
bonus number.
How many choices for the 6 winning numbers
 49 
 
6
49! 49  48  47  46  45  44 

49 C6 
6!43!
6  5  4  3 2 1
 13,983,816
Software Support
Excel:
• Permutations (in EXCEL =PERMUT(6,2))
• Combinations (in EXCEL =COMBIN(6,2))
Python:
• scipy.special.comb (N, k)
• scipy.special.perm (N, k)
One more thing
An alternative and more common way to denote
an r-combination:
n
C (n, r )   
r
18