Intro to Combinatorics and Graph Theory

Let $A, B$, and $C$ be finite sets. Justify the equation \(|A|+|B|+|C|+|A \cap B \cap C|=|A \cup B \cup C|+|A \cap B|+|A \cap C|+|B \cap C|\).

A binary string of length $n$ is a sequence with $n$ terms, each of which is either a 0 or a 1. For example, displayed below are the 16 binary strings of length 4. $$\begin{array}{llllllll}0000 & 0001 & 0010 & 0011 & 0100 & 0101 & 0110 & 0111 \\ 1000 & 1001 & 1010 & 1011 & 1100 & 1101 & 1110 & 1111\end{array}$$ A change in a binary string is an occurrence of two consecutive terms in the string that are different (that is, one is a 0 and the other is a 1). For example, in the binary string 1001, there are two changes: the 10 at the beginning and the 01 at the end. In the same arrangement that the strings are presented above, the number of changes in each of the sixteen strings of length 4 is as follows: $$ \begin{array}{llllllll} 0 & 1 & 2 & 1 & 2 & 3 & 2 & 1 \\ 1 & 2 & 3 & 2 & 1 & 2 & 1 & 0 \end{array} $$ How many binary strings of length $n$ have exactly $k$ changes? Justify your answer. (For $n=4$, there are 2 with zero changes, 6 with one change, 6 with two changes, and 2 with three changes.) (Your answers should be expressed in terms of binomial coefficients, rather than in algebraic expressions involving $n$ and $k$.)

Consider binary strings that do not have two consecutive zeros (that is a zero followed by another zero). There are 2 such strings of length 1: 0, 1. There are 3 such strings of length 2: 01, 10, 11. How many such strings are there of length 3? How many of length 4? How many of length \(5\)?