Lecture 13: Counting Problems continued

Sick of ads?‚Äč Sign up for MathVids Premium
Taught by ArsDigita
  • Currently 4.0/5 Stars.
4690 views | 1 rating
Lesson Summary:

In this lecture, the instructor continues discussing counting problems and focuses on the inclusion-exclusion principle, which is a complement principle used to solve problems that are difficult to solve otherwise. Additionally, the instructor introduces the pigeonhole principle, which is a separate principle and explains it through examples. The lesson concludes with the application of constraints to counting problems and different methods to solve such problems.

Lesson Description:

More Counting problems are explained.

More information about this course:
Licensed under Creative Commons Attribution ShareAlike 2.0:

Additional Resources:
Questions answered by this video:
  • In how many ways can you distribute 5 non-distinct objects into 2 boxes?
  • How many different solutions are there to x1 + x2 + x3 = 3?
  • How many different solutions are there to x1 + x2 + x3 = 8 if x1 < 3
  • What is the inclusion / exclusion principle, and how is it used to solve counting problems?
  • How many base 10 numbers have at least 1 zero and 1 one?
  • How many permutations are there of aaabbbccc without having three consecutive of the same letter?
  • How can you use the complement of a set to count the number of things in a set?
  • What is a derangement in combinatorics and how do you count them up?
  • In the hat check problem in which everyone gets a random hat, in how many ways does nobody get his hat back?
  • What is the pigeonhole principle and what are some problems that use it?
  • How can you prove that two people in a room were born on the same day of the month?
  • How can you prove that two people in the USA have the same number of hairs on their body?
  • If a test has a possible range of 0-100, how many people need to take the test to guarantee that at least 3 people get the same score?
  • If there are 51 houses on a street with addresses between 1000 and 1099, how can you prove that there are at least two houses with consecutive addresses?
  • If there are n computers on a network, prove that at least two computers are connected to the same number of other computers?
  • If a computer goes down at least one time each day, and during a 30-day month, it goes down at most 45 times, how can you prove that the computer goes down exactly 14 times in some consecutive period of days?
  • Staff Review

    • Currently 4.0/5 Stars.
    This lecture deals with some more classic combinatorics problems. The inclusion / exclusion principle, permutations, combinations, and the pigeonhole principle are some well-known topics that are dealt with in this lesson. All of the examples that are done really solidify the concept of counting objects in different situations.