21-228: Discrete Mathematics
Official course webpage
Class meetings:
| Lecture | §A | §B | §C |
| MWF 1:30–2:20 | T 8:30–9:20 | T 9:30–10:20 | T 4:30–5:30 |
| Hamerschlag B131 | Posner 146 | Scaife 219 | Baker 235A |
Office hours:
| Tom | Chris | Sunny |
| W 2:30–4:30 | R 12:30–2:30 | R 4:30–5:30 |
| Wean 6113 | Wean 6201 | Wean 6215 |
Recitation notes
I'll do my best to write notes about what was covered in recitation each week and post them here. However, due to my schedule, I'll likely be unable to do this some weeks and other weeks may have only very brief notes.
I type these up quickly, so please let me know if you find any mistakes!
- Recitation 1 — 01/14/20
- Recitation 2 — 01/21/20
- Recitation 3 — 01/21/20: I didn't have time to type detailed notes this week, but here's a list of what we covered:
- If $H_n:=\sum_{k=1}^n{1\over k}$, then $H_n\approx\int_1^n{dx\over x}=\log n$. ($H_n$ is known as the $n$th harmonic number)
- More precisely, we can bound $\log(n+1)\leq H_n\leq\log n + 1$.
- Since ${1\over x}$ is convex, the lower bound can be improved to $H_n\geq\log n + {1\over 2}+{1\over 2n}$ by using trapezoids instead of rectangles.
- If $d(n)$ denotes the number of divisors of $n$, then $\text{ave}_{k\in[n]}d(k)\approx\log n$ (see Recitation 2).
- Using the same ideas, for any $d>-1$, we have $\sum_{k=1}^n k^d\approx {n^{d+1}\over d+1}$.
- If $H_n:=\sum_{k=1}^n{1\over k}$, then $H_n\approx\int_1^n{dx\over x}=\log n$. ($H_n$ is known as the $n$th harmonic number)
- Recitation 4 — 02/04/20
- We did not cover this in class, but these notes include proof that the number of derangements of $[n]$ is precisely the closest integer to ${n!\over e}$, a fact that was mentioned in Recitation 2.
- Recitation 5 — 02/11/20 (Review day)
- I'm out of town Mon–Wed this week
- Recitation 6 — 02/18/20 (These notes were scrapped last-minute so that we could focus on reviewing troublesome topics from the exam. However, since I'd already written them, they're here for your reading pleasure!)
- I'm out of town Wed–Fri this week
- Consequently, I'll be holding office hours instead on Mon 11:30–1:30
- Recitation 7 — 02/25/20
- Recitation 8 — 03/03/20
- 03/17/20: Recitation is canceled this week as CMU transitions to remote teaching amid COVID-19 concerns
- Recitation 9 — 03/24/20
- I made a remark in recitation about how Claim 1 in the notes changes if we require only pairwise independence instead of mutual independence.
There was enough curiosity about this that I wrote up a proof.
This proof can be modified to show that if $A_1,\dots,A_n\subseteq\Omega$ are nontrivial and have the property that any set of at most $k$ of them is independent, then $|\Omega|\geq\sum_{j=0}^{\lfloor k/2\rfloor}{n\choose j}$.
- The proof here probably appears to be very ad hoc; this is not actually the case. Once we learn about random variables (which are simply the elements of $\mathbb{R}^{\Omega}$) and expectations, it will be clear that $\langle X,Y\rangle=\operatorname{\mathbb{E}}XY$ is a natural inner product on $\mathbb{R}^{\Omega}$. This is all that's going on in the proof, using the random variables $X_i=\mathbf{1}_{A_i}-\operatorname{\mathbb{E}}\mathbf{1}_{A_i}$ and $X_0=1$. In fact, the proof is much cleaner when phrased this way.
- With this terminology, in order to prove the fact about $k$-wise independent events mentioned above, first define $X_i=\mathbf{1}_{A_i}-\operatorname{\mathbb{E}}\mathbf{1}_{A_i}$ for $i\in[n]$. Then, for a set $I\subseteq[n]$ with $|I|\leq k/2$, define $Y_I=\prod_{i\in I}X_i$. With just a bit of work, it can be shown that the $Y_I$'s are non-zero and pairwise orthogonal. If $k$ is odd, then the bound can be improved slightly by considering also $Z_I=X_n\prod_{i\in I}X_i$ for $I\in{[n-1]\choose\lfloor k/2\rfloor}$.
- I made a remark in recitation about how Claim 1 in the notes changes if we require only pairwise independence instead of mutual independence.
There was enough curiosity about this that I wrote up a proof.
This proof can be modified to show that if $A_1,\dots,A_n\subseteq\Omega$ are nontrivial and have the property that any set of at most $k$ of them is independent, then $|\Omega|\geq\sum_{j=0}^{\lfloor k/2\rfloor}{n\choose j}$.
- Recitation 10 — 03/31/20
- A few of you asked about the footnote remark in the exercise in these notes, so here's a proof sketch. (Note: this has nothing to do with probability)
- Recitation 11 — 04/07/20
- Recitation 12 — 04/14/20
- Recitation 13 — 04/21/20 (Review day)
- Recitation 14 — 04/28/20 (Last recitation! Exam review)
Supplementary materials
- Here is yet another proof of the inclusion-exclusion formula and the Bonferonni inequalities. The proof is essentially identical to the one Tom gave in lecture; it is simply a different way to phrase that idea.