CS2050 L21 Binomial Theorem
Overview
Abrahim Ladha develops the binomial theorem from counting: first deriving the multinomial permutation count, then proving that each coefficient in (x + y)^n counts the ways to choose positions for x. He uses Pascal's triangle to establish identities and applications, including Fermat's little theorem, then derives inclusion-exclusion and applies it to count the integers from 1 to 100 that are not divisible by 2, 3, or 5.
Key takeaways
- When objects repeat, divide the total n! arrangements by the factorial of each repeated type's count; SUCCESS therefore has 7!/(3!2!1!1!) = 420 distinct arrangements.
- In (x + y)^n, the coefficient of x^i y^(n−i) is n choose i because it counts which i of the n factors contribute x.
- Pascal's identity follows by splitting k-person committees from n students and one teacher into committees that include the teacher and those that do not.
- For prime p, every interior coefficient p choose i is divisible by p, which makes the binomial expansion prove a^p ≡ a (mod p) by induction.
- Inclusion-exclusion counts each element appearing in exactly k sets with an alternating binomial sum; the binomial theorem makes that total exactly 1.
- Among the integers 1 through 100, inclusion-exclusion finds 74 divisible by at least one of 2, 3, or 5, leaving 26 divisible by none of them.
Chapters
- The four distinct letters in CAKE have 4! permutations, but SUCCESS has repeated letters that make 7! an overcount.
- For 3 S's, 2 C's, 1 U, and 1 E, the count is 7! / (3!2!1!1!) = 420.
- For letter types with multiplicities n1 through nk and total n, the distinct arrangements number n! / (n1! ··· nk!).
- Abrahim Ladha states (x + y)^n = Σ from i = 0 to n of (n choose i)x^i y^(n−i), for n ≥ 0.
- The small expansions of (x + 1)^n show coefficient rows such as 1, 4, 6, 4, 1 for n = 4.
- The theorem lets you find a specific coefficient in a large expansion, such as (x + y)^100, without multiplying every factor out.
- Treat (x + y)^n as n separate factors and choose either x or y from each, producing 2^n length-n strings.
- After using commutativity to group products, every string with i x's contributes x^i y^(n−i).
- Choosing which i of the n positions contain x gives n choose i strings, establishing the binomial coefficient.
- Rows of Pascal's triangle list the coefficients n choose i from each binomial expansion.
- The edge entries are 1, the entries next to the edges form the counting sequence 1, 2, 3, 4, and the next diagonal gives shifted triangular numbers.
- Each row sums to 2^n by setting x = y = 1 in the binomial theorem, and each row reads the same in reverse because n choose i = n choose n−i.
- The identity (n + 1 choose k) = (n choose k−1) + (n choose k) counts k-person committees from n students and one teacher.
- Committees containing the teacher need k−1 students; committees without the teacher need k students.
- The two cases are disjoint and exhaustive, so the sum rule gives the next row of Pascal's triangle.
- The diagonal sum (k choose k) + (k+1 choose k) + ··· + (n choose k) equals (n+1 choose k+1).
- Count subsets of size k+1 from {1, 2, ..., n+1} by their largest element.
- If the largest element is i+1, the other k elements can be chosen from 1 through i in i choose k ways; summing these cases proves the identity.
- For prime p and 0 < i < p, p divides p choose i because the numerator p! contains a factor p that cannot cancel against i!(p−i)!.
- The endpoints p choose 0 and p choose p equal 1, so they are exceptions to the divisibility property.
- This divisibility fact supplies the key cancellation step in a binomial-theorem proof of Fermat's little theorem.
- For prime p, the proof establishes a^p ≡ a (mod p) by induction on a, starting with a = 0.
- Expand (a + 1)^p using the binomial theorem; every interior term contains a coefficient p choose i divisible by p.
- Modulo p, only a^p and 1 remain, and the induction hypothesis gives (a + 1)^p ≡ a + 1 (mod p).
- The equality n choose i = n choose n−i explains why every row of Pascal's triangle is a palindrome.
- Rows with an even number of entries have a central pair of equal coefficients, while rows with an odd number of entries have a single central entry.
- This symmetry follows directly from choosing i positions versus choosing the n−i positions left over.
- For two sets, |A ∪ B| = |A| + |B| − |A ∩ B| corrects the double count of elements in both sets.
- For three sets, add the three set sizes, subtract the three pairwise intersections, then add the triple intersection back.
- The alternating signs ensure that each element in the union is ultimately counted exactly once.
- For sets A1 through An, inclusion-exclusion alternates sums of single-set sizes, pairwise intersections, triple intersections, and higher intersections.
- The terms for intersections of an odd number of sets are added; terms for an even number are subtracted.
- The proof checks how many times an element appearing in exactly k sets is counted on the right-hand side.
- An element belonging to exactly k of the sets appears in k single-set terms, (k choose 2) pairwise terms, and (k choose 3) triple terms, continuing through (k choose k).
- Its signed total is Σ from i = 1 to k of (−1)^(i−1)(k choose i).
- The binomial theorem gives this alternating sum as 1, so each element in the union is counted exactly once.
- There are 50 multiples of 2, 33 of 3, and 20 of 5 between 1 and 100.
- The pairwise intersections contain 16 multiples of 6, 10 of 10, and 6 of 15; the triple intersection has 3 multiples of 30.
- Inclusion-exclusion gives 50 + 33 + 20 − 16 − 10 − 6 + 3 = 74 divisible numbers, leaving 100 − 74 = 26 not divisible by any of 2, 3, or 5.
Transcript excerpt
0:01 Uh this is CS 2050. The topic of today is the binomial theorem. Um before we do that, there's one last little theorem that we need to talk about. Uh how many permutations are there of the letters cake? For the word cake, this is a warm-up. Yeah. Uh, nope. Four factorial. Why? You choose one first letter, you choose a second letter, you choose third letter, choose a fourth letter. Right? There's four choices for the first, three for the second, uh, two for the third and one last one is the last, right? Okay. So,
0:48 it's basically if you have if you want to consider the number of permutations of something, it's just the factorial usually. What about the letters of success? There's a problem with this one that doesn't exist for the other. Right? The problem is different because of this notion of distinguishability and indistinguishability. So two objects are said to be distinguishable if you could tell them apart. Up to counting you say I can tell these apart. two objects are set to be indistinguishable is I don't want to over count by trying to tell these apart. In fact, I can't tell them apart. So here we're counting permutations of
1:36 these letters. But notice that some of them look the same. There are three S's. Now I could just this letter is this word is seven long seven long. I could just say seven factorial. But that overounts because if I swap these two I'm counting that as two different permutations, but I should only count it once. So we need a different formula for this. [snorts] Here's what we'll do. If there are seven spots, what we'll do is just choose the uh spots for each letter up to distinguishability and indistinguishability. So the S's cannot
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
In this course
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Abrahim Ladha.