Combinations
Choosing without order, n choose k (C(n,k)), binomial coefficients, and Pascal triangle basics.
Lessons
1. Intro
(The goal)
2. When Order Doesn't Matter
(The core idea)
3. Combinations vs Permutations
(The critical difference)
4. The Combinations Formula
(C(n,k) defined)
5. Why Divide by k!
(Removing duplicates)
6. Example: C(6,2)
(Computing step by step)
7. Example: C(10,3)
(Another computation)
8. Symmetry: C(n,k) = C(n,n-k)
(Choosing vs leaving)
9. Boundary Cases
(Edge values)
10. Pascal's Triangle
(Visual representation)
11. Building Pascal's Triangle
(Row by row)
12. Pascal's Identity
(The recursive formula)
13. Why Pascal's Identity Works
(Algebraic verification)
14. Binomial Theorem
(Expanding (a+b)^n)
15. Binomial Expansion Example
((x+y)^3)
16. Counting Subsets
(Total is 2^n)
17. Why 2^n Subsets
(Binary choice argument)
18. Combinations with Repetition
(Stars and bars)
19. Stars and Bars Method
(Visual explanation)
20. Quiz: Basic Combinations
(Knowledge check)
21. Combinatorial Identities
(Useful formulas)
22. Hockey Stick Identity
(Diagonal sums)
23. Quiz: Pascal's Triangle
(Knowledge check)
24. Quiz: Advanced Combinations
(Final check)
25. Real World Applications
(Where combinations appear)
26. Computing Large Combinations
(Avoiding overflow)
27. Combinations Modulo M
(For competitive programming)
28. Combinations in Probability
(Counting outcomes)
29. Problem - Combinations
Generate C(n,k)
30. Combinations - Building Strategy
Choose or skip pattern
31. Combinations - Implementation
The pseudocode
32. Lessons from Combinations
summary
33. Problem - Combination Sum
Target sum with reuse
34. Combination Sum - Reuse Strategy
Same index or skip
35. Combination Sum - Implementation
The pseudocode
36. Lessons from Combination Sum
summary
37. Problem - Subsets
All possible subsets
38. Subsets - Include or Exclude
Decision tree approach
39. Subsets - Implementation
The pseudocode
40. Lessons from Subsets
summary
41. Problem - Subsets II
Subsets with duplicates
42. Subsets II - Insight
Skip duplicates
43. Subsets II - Implementation
The pseudocode
44. Section Recap
What we learned