Discrete Mathematics
# Principle of Inclusion and Exclusion

**do not** include any red squares?

We have 7 people and 7 pairs of distinct shoes. In how many ways can these shoes be distributed so that no person gets a proper pair?

**Note:** The left shoe is considered distinct from the right one and a distribution consists of each person getting a left shoe and a right shoe.

Two positive integers $x$ and $y$ are chosen at random from the first 100 positive integers with replacement. The probability that $xy$ is divisible by 6 is $\eta$.

Calculate $\lfloor 1000\eta\rfloor$.

**Bonus:** You might like to calculate the probability without replacement for fun.

Santa is running out of time distributing presents to everyone, so he has asked a helper to help him.

However the helper is lazy. When he arrives at a street with seven houses (which each get one present) he randomly throws one unique present into each house (all the presents he throws belong to the houses), And having beginner's luck, he gets **at least two** presents in the correct houses.

How many ways are there to distribute the presents?

Five couples like to go to the movies together; they always sit in a row of ten adjacent seats. To shake things up a bit, they have a rule that nobody is allowed to sit next to their partner. How many seating arrangements are there for this party?

I thought of this problem while watching a bad (Hollywood) movie on a bad date ;)