Fichas
Discrete Structures - Counting
Fichas del conjunto (15)
- 1Addition Principle- If a task can be accomplished by performing either procedure P1 in M1 ways, or procedure P2 in M2 ways, then the task can be accomplished in M1 + M2 ways.
- 2Addition Principle (Example 1)There are 3 bus routes from NYC to Boston and 5 rail routes.
How many ways are there of reaching Boston from NYC?
- There are 8 ways of reaching Boston from NYC - 3Multiplication Principle- If a task is accomplished by performing procedure P1 in M1 ways, followed by performing procedure P2 in M2 ways, then the task can be accomplished in M1 x M2 ways,
- 4Multiplication Principle (Example 1)How many 3-digit numbers are there?
9 x 10 x 10 = 900 - 5Multiplication Principle (Example 2)How many 3-digit numbers with distinct digits are there?
9 x 9 x 8 = 648 - 6Multiplication Principle (Example 3)How many social security numbers are there?
10 x 10 x 10 x 10 x 10 x 10 x 10 x 10 x 10 = 10^9 - 7Multiplication Principle (Example 4)A test consists of 10 questions with 4 possible choices, followed by 5 questions with 5 choices for each. How many answer sheets are possible?
= 4^10 x 5^5 - 8Multiplication and Additional Principle (Example) (Also see notebook for additional explanation)How many 3 digit numbers divisible by 5 are there?
0 --> 9 x 10 x 1 = 90
5 --> 9 x 10 x 1 = 90
90 + 90 = 180 3 digit #'s divisible by 5
S - 9PermutationA permutation of distinct objects is an arrangement of objects in which the order of objets matters
Ex of permutation for a, b, c:
-abc
-acb
-bac
-bca
-cab
-cba - 10Permutations (Example of Factorial) (See notebook for additional examples)Give a distinct, how many permutations of K objects out of N are there? (0<= K <= N)
(n)(n-1)(n-2)...(n-k+1) = n! / n-k!
P(n,k) = n! / n-k!
Ex: P(n,0) = n! / (n-0)! = n!/n! = 1 - 11CombinationA combination is an arrangement of objects in which the order of the objects does not matter
C(n,k) = total # of permutations / number pertaining in our combinations
C(n,k) = P(n,k) / k! = n! / k!(n-k)! - 12Combinations (Examples)- C(3,2) = 3! / 2! (3-2)! = 3! / (2!)(1!) = 3!/2! = 3
- C(3,0) = 3! / 0! (3-0!) = 3!/3! = 1
- C(n,0) = n! / 0! (n-0)! = n!/n! = 1
- C(n.n) = n! / n! (n-n)! = n!/n! = 1
- C(n,1) - n! / 1! (n-1)! - 13Example (Palindrome)A palindrome is a string of characters that reads the same forward and backwards. How many 5 letter english palindromes are possible?
26*26*26*1*1 - 14Combination and Permutation ExampleA set of four coins is selected from a box containing 5 dimes, and 7 quarters.
a. Find the number of sets of 4 coins.
i. C(12,4)
b. find the number of sets in which two are dimes and two are quarters
i. C(5,2)*C(7,2)
c. Find the number of sets composed of all dimes or all quarters
i. C(5,4)+C(7,4)
d. Find the number of sets with 3 or more quarters
i. C(7,3)*C(5,1)+C(7,4)*C(5,0) - 15Additional ExamplesSee notebook (Committee of 8 students example) and HW # 5)
Información
- Descripción
- Fichas sobre Discrete Structures - Counting, creado por Spencer Ross el 17/12/2018.
- Creado por
- Spencer Ross
- Visitas
- 0
- Valoración