12.25

1. We define \(\binom{n}{r} = |P_r([n])|\). Prove the following identities:

   1. \(\binom{n}{r} = \binom{n}{n-r}\)

      • By proposition, we know that \(\binom{n}{r} = \frac{n!}{r!(n-r)!}\)

      \(\binom{n}{n-r} = \frac{n!}{(n-r)!(n-(n-r))!} = \frac{n!}{(n-r)!r!}\)

      So \(\binom{n}{r} = \binom{n}{n-r}\) * For example: \(\binom{5}{3} = \binom{5}{2}\)

      Here \(\binom{n}{r}\) = the amount of subsets of \([n]\) that I can form that have \(r\) elements.

      And \(\binom{n}{n-r}\) = how many subsets of \([n]\) I can form with \(n-r\) elements. 2. \(\sum_{r=0}^n \binom{n}{r} = 2^n\)

      \(\sum_{r=0}^{n}\binom{n}{r}=\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n-1}+\binom{n}{n}=\bigcup_{r=0}^{n}\mathcal{P}_{r}([n])=\mathcal{P}([n])\)

      • \(\binom{n}{0}\): subsets of \(0\) elements
      • \(\binom{n}{1}\): subsets of \(1\) element
      • \(\binom{n}{2}\): subsets of \(2\) elements
      • \(\cdots\)
      • \(\binom{n}{n}\): subsets of \(n\) elements

      Thus, \(\sum_{r=0}^n \binom{n}{r} = |\mathcal{P}([n])|\), which equals \(2^n\). 3. \(\binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1}\)

      \(\binom{n}{r} = |\mathcal{P}_r([n])|\)

      \(\mathcal{P}_r([n]) = \mathcal{P}_r([n-1]) \cup \{n \cup A \,|\, A \in \mathcal{P}_{r-1}([n-1])\}\)

      • The term \(\mathcal{P}_r([n-1])\): groups of \(r\) students where the teacher is not in the subset.
      • The term \(\{n \cup A \,|\, A \in \mathcal{P}_{r-1}([n-1])\}\): groups where the teacher is in the subset, combined with \(r-1\) students.

      Thus, the recursive relation is derived by considering subsets of \(r\) elements either including or excluding the teacher.

2. Prove the binomial theorem \((a+b)^n = \sum_{r=0}^n \binom{n}{r} a^r b^{n-r}\)

   By induction:

   • Case \(n = 1\) : For \(n=1\): \((a+b)^1 = \sum_{r=0}^1 \binom{1}{r} a^r b^{1-r}=\binom{1}{0} b + \binom{1}{1} a = a+b\) ✅
   • Suppose \(P(n)\) is true, so \((a+b)^n = \sum_{r=0}^n \binom{n}{r} a^r b^{n-r}\).

   Let's prove for \(n+1\):

   \((a+b)^{n+1} = (a+b)^n \cdot (a+b)\)​\(= \left( \sum_{r=0}^n \binom{n}{r} a^r b^{n-r} \right) \cdot (a+b)\)​\(= \sum_{r=0}^n \binom{n}{r} a^r b^{n-r} a + \sum_{r=0}^n \binom{n}{r} a^r b^{n-r} b\)

   \(=\sum_{r=0}^{n}\binom{n}{r}a^{r+1}b^{n-r}+\sum_{r=0}^{n}\binom{n}{r}a^{r}b^{n+1-r}\)

   \(=\binom{n}{0}a^1b^{n}+\binom{n}{1}a^2b^{n-1}+\binom{n}{2}a^3b^{n-2}+\dots+\binom{n}{n}a^{n+1}b^0\quad+\quad\binom{n}{0}a^0b^{n+1}+\binom{n}{1}a^1b^{n}+\binom{n}{2}a^2b^{n-1}+\dots+\binom{n}{n}a^{n}b^1\)

   \(=\binom{n}{n}a^{n+1}+\binom{n}{0}b^{n+1}+\sum_{r=1}^{n}\binom{n+1}{r}a^{r}b^{n+1-r}=\sum_{r=0}^{n+1}\binom{n+1}{r}a^{r}b^{n+1-r}\)

3. How many subsets of \([10]\) are there that contain at least one odd number?

   I will calculate the complement of this: "subsets of \([10]\) that only have even numbers."

   \(2^{10} - 2^5\)

   • \(2^{10}\): total amount
   • \(2^5\): those subsets formed only by even numbers.

4. There is a group of 11 people, formed by 4 teachers and 7 students. In how many ways can I form a committee of 5 people if:

   a) there are no restrictions?

   \(\binom{11}{5}\)

   b) the committee must have exactly 2 teachers?

   \(\binom{4}{2} \cdot \binom{7}{3}\)

   c) the committee must have at least 3 teachers?

   \(= \text{exactly 3 teachers} + \text{exactly 4 teachers}\)​\(\binom{4}{3} \cdot \binom{7}{2} + \binom{4}{4} \cdot \binom{7}{1}\)

   d) The teacher \(X\) and student \(Y\) cannot be together in the committee?

   \(2 \cdot \binom{9}{4} + \binom{9}{5}\)

‍