Lecture 13: Counting Problems continued

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.

More Counting problems are explained.

• 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?