Discrete Structures: Permutations and Combinations
The concepts of permutations and combinations in the realm of discrete structures, unraveling the use of factorial in both scenarios. Dive into examples like rolling a die and flipping a coin, arranging letters, and solving combinations involving lock codes. Discover the formulas and methods behind calculating permutations and combinations, including circular permutations.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
SE (Comp.Engg.) Unit VI Discrete Structures Permutations and Combinations
BOTH PERMUTATIONS AND COMBINATIONS USE A COUNTING METHOD CALLED FACTORIAL
Lets start with a simple example. A student is to roll a die and flip a coin. How many possible outcomes will there be?
1H 2H 3H 4H 5H 6H 1T 2T 3T 4T 5T 6T
The number of ways to arrange the letters ABC: ____ ____ ____ 3 ____ ____ 32 ___ 321 Number of choices for first blank? Number of choices for second blank? Number of choices for third blank?
Permutations A Permutation is an arrangement of items in a particular order. The number of Permutations of n items chosen r at a time, is given by the formula ! n = where 0 . n p r n r ( )! n r
Arrange 2 alphabets from a,b,c. ab, ba, ac,ca,bc,cb 3P2=3!/(3-2)!=6
A combination lock will open when the right choice of three numbers (from 1 to 30, inclusive) is selected. How many different lock combinations are possible assuming no number is repeated?
30 ! 30! = = = = 30 * 29 * 28 24360 p 30 3 ( 30 3 )! 27!
CIRCULAR PERMUTATIONS When items are in a circular format, to find the number of different arrangements, divide: n! / n
Six students are sitting around a circular table in the cafeteria. How many different seating arrangements are there?
Combination A Combination is an arrangement of items in which order does not matter. The number of Combinations of n items chosen r at a time, is given by the formula ! n = where )! 0 . n C r n r ( ! r n r
To play a particular card game, each player is dealt five cards from a standard deck of 52 cards. How many different hands are possible?
52 ! 52! = = = C 52 5 ( ! 5 52 5 )! 5!47! 52 * 51 * 50 * 49 * 48 = , 2 598 960 , 5 * 4 * 3 * 2 * 1
A student must answer 3 out of 5 essay questions on a test. In how many different ways can the student select the questions?
! 5 5 * 4 5! = = = = 10 C 5 3 5 ( ! 3 3 )! 2 * 1 3!2!
Product and Sum Rules Product Rule: If we need to perform procedure 1 AND procedure 2. There are n1 ways to perform procedure 1 and n2 ways to perform procedure 2. There are n1 n2 ways to perform procedure 1 AND procedure 2.
Sum Rule: If need to perform either procedure 1 OR procedure 2. There are n1 ways to perform procedure 1 and n2 ways to perform procedure 2. There are n1+n2 ways to perform procedure 1 OR procedure 2. This OR is an exclusive OR. One choice or the other, but not both.
How many vehicle number plates can be made if each plate contains two different letters followed by three different digits
Two different letters are made in 26P2 ways. 3 different digits are combined in 10P3ways Total no. of number plates= 26P2 * 10P3 =26!*10!/(24!*7!) =26*25*10*9*8 =468000
An 8 member team is to be formed from a group of 10 men and 15 women. In how many ways can the team be chosen if : (i) The team must contain 4 men and 4 women (ii) There must be more men than women (iii) There must be at least two men
The team must contain 4 men and 4 women = 286650 (ii) There must be more men than women = (iii) There must be at least two men
Passwords consist of character strings of 6 to 8 characters. Each character is an upper case letter or a digit. Each password must contain at least one digit. How many passwords are possible?
Total number is # passwords with 6 char. + # passwords with 7 char. + # pws 8 char. (=P6+P7+P8).
P6: # possibilities without constraint : 366 # exclusions is # passwords without any digits is 266 And so, P6 = 366-266
How many bit-strings of length 8 either begin with 1 or end with 00?
A = 8-bit strings starting with 1 |A| = # of 8-bit strings starting with 1 is 27 B = 8-bit strings starting with 00 |B| = # of 8-bit strings ending with 00 is 26 # of bit-strings begin with 1 and end with 00 is 25.
# of 8-bit strings starting with 1 or ending with 00 is 27+ 26- 25
|A B| = |A| + |B| - |A B| Inclusion Exclusion Principle
Permutations with non-distinguishable objects The number of different permutations of n objects, where there are non-distinguishable objects of type 1, non-distinguishable objects of type 2, , and non-distinguishable objects of type k, is ! n n 1n 2n kn ! n !... ! n 1 2 k i.e., C(n, )C(n- , ) C(n- - - - , ) + 1n 1n 1n + 2n 2n n kn kn 1 + = ... n n n 1 2 k 33
How many different strings can be made by reordering the letters of the word OFF
3!/2!=3 OFF FFO FOF
ONE OEN NEO NOE ENO EON
How many different strings can be made by reordering the letters of the word SUCCESS
Generating Permutations Lexicographic method
For the following 4 combinations from the set f= {1;2;3;4;5;6;7} find the combination that immediately follows them in lexicographic order 1234 is followed by 3467 is followed by 4567 is followed by
What is probability? Probability is the measure of how likely an event or outcome is. Different events have different probabilities!
How do we describe probability? You can describe the probability of an event with the following terms: certain (the event is definitely going to happen) likely (the event will probably happen, but not definitely) unlikely (the event will probably not happen, but it might) impossible (the event is definitely not going to happen)
probabilities are expressed as fractions. The numerator is the number of ways the event can occur. The denominator is the number of possible events that could occur.
Random Experiment a random experiment is an action or process that leads to one of several possible outcomes. For example: Experiment Outcomes Flip a coin Heads, Tails Exam Marks Numbers: 0, 1, 2, ..., 100 Assembly Time t > 0 seconds Course Grades F, D, C, B, A, A+ 6.43
What is the probability that I will choose a red marble? In this bag of marbles, there are: 3 red marbles 2 white marbles 1 purple marble 4 green marbles
Probability example Sample space: the set of all possible outcomes. Probabilities: the likelihood of each of the possible outcomes (always 0 P 1.0). 0 P ( + ) 1 P E = ( ) ( ) 1 E P E = ( ) 1 ( ) P E P E = ( ) 1 ( ) P E P E
Probabilities List the outcomes of a random experiment This list must be exhaustive, i.e. ALL possible outcomes included. Die roll {1,2,3,4,5} Die roll {1,2,3,4,5,6} The list must be mutually exclusive, i.e. no two outcomes can occur at the same time: Die roll {odd number or even number} Die roll{ number less than 4 or even number} 6.46
A and B are independent if and only if P(A&B)=P(A)*P(B) A and B are mutually exclusive events: P(A or B) = P(A) + P(B)
Events & Probabilities The probability of an event is the sum of the probabilities of the simple events that constitute the event. E.g. (assuming a fair die) S = {1, 2, 3, 4, 5, 6} and P(1) = P(2) = P(3) = P(4) = P(5) = P(6) = 1/6 Then: P(EVEN) = P(2) + P(4) + P(6) = 1/6 + 1/6 + 1/6 = 3/6 = 1/2 6.48
e.g. 1. The following table gives data on the type of car, grouped by petrol consumption, owned by 100 people. Low Medium High Total 12 33 7 Male 23 21 4 Female 100 One person is selected at random. L is the event the person owns a low rated car F is the event a female is chosen . Find (i) P(L) (ii) P(F L) (iii) P(F|L)
Low Medium High Total Solution: Male 12 33 7 Female 23 21 4 100 Find (i) P(L) (ii) P(F L) 35 100 (iii) P(FL) 7 7 = = (i) P(L) = 20 23 100 20 Notice that 1 7 23 23 = = = = (ii) P(F L) = P(L) P(F L) 20 35 100 5 23 35 =P(F L) (iii) P(F L) = = So, P(F L)= P(F|L) P(L)
