CS2050 L20 Combinatorics
Overview
Abrahim Ladha introduces combinatorics as counting finite sets, developing the product and sum rules into formulas for bit strings, permutations, combinations, and lattice paths. He emphasizes combinatorial and visual proofs, then applies stars and bars to count integer solutions, including examples with four variables summing to 10: 286 unrestricted solutions, 1001 with sum at most 10, 84 with every variable positive, and 202 with at least one zero.
Key takeaways
- The product rule makes independent choices multiply: n binary positions produce 2^n bit strings, while three letters followed by four digits produce 26^3 × 10^4 possible plates.
- The number of length-n bit strings without consecutive ones satisfies A(n) = A(n−1) + A(n−2), because strings beginning with 1 must begin with 10.
- Combinations count unordered subsets, so C(n,k) = P(n,k)/k!; complementing each subset proves C(n,k) = C(n,n−k).
- Counting an n-element set's subsets by size and by inclusion decisions gives Σ(i=0 to n) C(n,i) = 2^n.
- For n nonnegative integer variables summing to k, stars and bars gives C(n+k−1,k); four variables summing to 10 therefore have 286 solutions.
- Constraints on integer solutions can be handled by transformations: a slack variable counts sums at most 10, while subtracting 1 from each positive variable reduces the total from 10 to 6.
Chapters
- For finite sets A and B, the product rule gives |A × B| = |A||B|.
- A bit string of length n has 2 choices at each of n positions, giving 2^n strings.
- Georgia's example plate format has 3 letters and 4 digits, yielding 26^3 × 10^4 = 175,760,000 possible plates.
- A rough Georgia population estimate of about 11 million illustrates how an order-of-magnitude estimate can check whether plate capacity seems sufficient.
- When sets A and B are disjoint, the sum rule gives |A ∪ B| = |A| + |B|.
- Let A(n) count length-n bit strings with no consecutive ones; the empty string gives A(0) = 1, and A(1) = 2.
- Strings beginning with 0 leave A(n−1) choices, while strings beginning with 1 must begin with 10 and leave A(n−2) choices.
- The recurrence A(n) = A(n−1) + A(n−2) produces Fibonacci numbers with an offset in indexing.
- A permutation is an ordering of distinguishable elements; arranging n elements gives n! possible orders.
- An r-permutation selects and orders r elements from n, with P(n,r) = n!/(n−r)!.
- For 100 people, choosing first, second, and third places gives 100 × 99 × 98 outcomes.
- Sanity checks confirm P(n,n) = n! and P(n,1) = n.
- The binomial coefficient C(n,k), read “n choose k,” counts k-element subsets of an n-element set.
- Unlike an r-permutation, a combination ignores order, so each selected k-element set is counted k! times by permutations.
- Dividing P(n,k) by k! gives C(n,k) = n!/[k!(n−k)!].
- Useful checks are C(n,0) = 1, C(n,1) = n, C(n,n) = 1, and C(n,2) = n(n−1)/2.
- A combinatorial proof establishes equality by describing two ways to count the same finite set.
- The underlying justification is that a bijection between sets implies equal cardinalities, even when the bijection is described informally.
- Ladha contrasts these proofs with algebraic manipulation, emphasizing that the key task is choosing and explaining the object being counted.
- Examples use distinguishable objects such as people to make the counting interpretation clear.
- Choosing k people from n is equivalent to specifying the n−k people not chosen.
- The bijection maps each k-element subset to its complement, an (n−k)-element subset.
- This gives the symmetry identity C(n,k) = C(n,n−k) without expanding factorials.
- An n-element set has 2^n subsets because each element is either included or excluded.
- Alternatively, count subsets by size: there are C(n,i) subsets of size i for each i from 0 through n.
- Equating the two counts proves Σ(i=0 to n) C(n,i) = 2^n.
- Including i = 0 is essential because the empty set is one of the subsets.
- To arrange A, B, C, D, E, F, G with A, B, C consecutive and in that order, treat ABC as a single composite symbol.
- The resulting objects are ABC, D, E, F, and G, which can be ordered in 5! ways.
- Replacing the block with ABC gives a direct bijection between these five-symbol orders and the original valid strings.
- The block method avoids counting all 7! strings and subtracting invalid arrangements.
- Arrange 1 + 2 + … + n as a staircase and pair it with a reversed copy; each of n positions then sums to n + 1.
- The paired arrangement has total 2S = n(n+1), proving 1 + 2 + … + n = n(n+1)/2.
- Successive odd-number L-shapes extend a square, showing 1 + 3 + … + (2n−1) = n².
- Both diagrams prove identities by rearranging the same counted objects into shapes that are easier to evaluate.
- A path from (0,0) to (m,n) using only right and down moves consists of m moves in one direction and n in the other.
- Represent each path as a length-(m+n) string containing exactly m of one move and n of the other.
- Choosing which m positions hold one move gives C(m+n,m) paths, equivalently C(m+n,n).
- The count follows from a bijection between paths and selections of move positions.
- Solutions to x₁ + … + xₙ = k with each xᵢ ≥ 0 correspond to placing k indistinguishable stars into n labeled bins.
- Represent the bins with n−1 dividers; the resulting string has k stars and n−1 bars, for n+k−1 total positions.
- Choosing the star positions gives C(n+k−1,k), equivalently C(n+k−1,n−1), solutions.
- For four variables summing to 10, stars and bars gives C(13,10) = 286 solutions.
- Convert x₁ + x₂ + x₃ + x₄ ≤ 10 into an equality by adding a nonnegative slack variable s.
- The equation x₁ + x₂ + x₃ + x₄ + s = 10 has five nonnegative variables.
- Stars and bars gives C(14,10) = 1001 solutions with the original four-variable sum at most 10.
- The slack value is uniquely determined by the original variables, so this transformation does not overcount.
- For x₁ + x₂ + x₃ + x₄ = 10 with every variable at least 1, set yᵢ = xᵢ−1.
- Then y₁ + y₂ + y₃ + y₄ = 6 with each yᵢ ≥ 0, giving C(9,6) = 84 solutions.
- Solutions with at least one zero equal all 286 nonnegative solutions minus the 84 solutions with no zero.
- The complement count is 286−84 = 202, illustrating how a change of perspective can avoid separately counting overlapping empty-bin cases.
Transcript excerpt
0:01 All right. Welcome to uh CS 2050. The topic of today is combinatorics or an introduction at least to combinatorics. We all kind of know a little bit of basics about combinatorics. Um we learned it in school. Combinatorics is alleged allegedly easy, but you'll see it gets pretty interesting and pretty advanced. Um uh it's it's just a math the mathematics that involves counting. That's all combinatorics is. Um and yeah, it was simple for a while and it was the case that it was not really considered a serious branch of mathematics. Most much of discrete math didn't really exist. I mean like so we had known about uh calculus and limits and things like this much earlier
0:48 uh than we than like Newton and things. We had some version of that uh dating back to Archimedes and things like this. Um we didn't really discover most of discrete math until like 20th century. Most things didn't were not known or it was trivial, like a triangle has three sides kind of trivial. Um uh so combinatorics is relatively new, but it's about a relatively old topic. And it was the case that if you were like someone who seriously stud studied combinatorics, you're not considered like a real mathematician. You know, people would be like racist to you or whatever. And uh that's not the case today at all anymore. It's like definitely a very serious branch. I think the last um Fields Medalist was for deep connections between uh combinatorics and other branches of of mathematics.
1:34 Um but today we're just going to do the super easy intro stuff and then we'll see uh just so we're on all on the same page about what it is. We're really talking about finite sets, right? So we're
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.