Lecture 11: Combinations and Permutations

In this lesson on combinations and permutations, the instructor delves into the basics of counting principles in discrete math. They introduce the multiplication principle, addition principle, and the complement principle as the go-to bag of tricks for counting. The instructor provides examples and shows how these principles can be used in various counting problems. They also touch on the connection between counting and probability, making the lesson useful for both math and science students.

Learn about the two most basic counting principles in discrete math, permutations and combinations, how they differ, and how to use them to count.

• What is counting or combinatorics in Discrete Math?
• What is the multiplication principle of combinatorics?
• Where can I find some example problems in combinations and permutations?
• What are permutations and combinations and how are they used in counting?
• How many possible ways are there to roll two dice?
• How many ways are there to put 36 people in a line?
• What is factorial, what does it mean, and how do you calculate it?
• What is the addition principle in combinatorics?
• How many different ways are there to roll an odd sum with two dice?
• What is the complement principle in combinatorics?
• How many ways are there to not roll doubles with two dice?
• When is it easier to count the complement of what you are looking for?
• How does counting relate to probability?
• If the probability of an event occurring is 1%, what is the chance that it does not occur 100 times in a row?
• What is the counting double or multiple counting principle in combinatorics?
• In how many ways can you choose four people from a group of 36?
• How can you tell that two counting problems are the same?
• Why is the number of ways you can multiply square matrices, the number of ways balanced parentheses can be arranged, and the number of nodes in a binary tree the same?
• Why is the maximum number of edges in a graph of n nodes the same as the number of possible pairs chosen from a group?
• What does a funny binary tree look like with the number of nodes at each level being equal to the Fibonacci sequence?
• What are some counting problems that have a one-to-one correspondence with each other?
• How do you calculate P(36, 4)?
• What is a permutation, what is the formula for nPr or P(n, r), and how do you calculate it?
• What is a combination, what is the formula for nCr or C(n, r), and how do you calculate it?
• What is the coefficient of x^3 in (x + 1)^7?
• How can you use combinations to find the coefficients of a binomial?
• How many possible 5-card hands are there using a 52-card deck?
• What do binomial coefficients and Pascal's Triangle have to do with combinations?
• How can you easily expand (x + y)^n?
• What are some patterns in Pascal's Triangle?
• How can you prove that C(n, k) = C(n-1, k-1) + C(n - 1, k)
• How can you prove that C(2n, n) = 2*C(n, 2) + n^2?