Lecture 11: Combinations and Permutations
10506 views
|
3
ratings
Lesson Description:
Learn about the two most basic counting principles in discrete math, permutations and combinations, how they differ, and how to use them to count.
More information about this course:
http://www.aduni.org/courses/discrete
Licensed under Creative Commons Attribution ShareAlike 2.0:
http://creativecommons.org/licenses/by-sa/2.0/
Additional Resources:
- Lecture Notes - Lecture Notes from the course
- Problem Set 5 Solutions - Solutions to the Problem Set
- Card Trick Problem Set - A problem set with some problems from this lecture
- Card Trick Problem Set Solutions - Solutions to the Problem Set
- Thoughts on teaching combinations and permutations - An article detailing how one person would teach combinations and permutations.
- Problem Set 5 - A problem set with some problems from this lecture
Questions answered by this video:
- 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?
-
Staff Review
Combinatorics is discussed in depth in this lecture. Many different counting principles are explained with some examples. Then, combinations and permutations are explained mostly using examples. Certain counting problems are exactly equivalent, so some problems are simplified to more easily understood problems. This lesson is central to the entire course, and possibly the most important lecture so far. -
