九至十二年级Discrete Mathematics计划中
Combinatorics
Permutations and combinations, binomial coefficients and Pascal's triangle, the binomial theorem, the pigeonhole principle and inclusion–exclusion, with combinatorial proofs.
math.discrete.combinatorics
本主题的课程尚未编写。下面的提纲是课程地图的一部分，尚未经过审校。
前置知识
15 项必需的前置知识（一直追溯到底）
你将学会
- Compute binomial coefficients and prove identities such as C(n, k) = C(n − 1, k − 1) + C(n − 1, k) by counting in two ways.
- Prove and apply the binomial theorem.
- Apply the pigeonhole principle and inclusion–exclusion to counting and existence problems.
定义
- C(n, k), read 'n choose k', is the number of k-element subsets of an n-element set.
- Pigeonhole principle: if more than n objects are placed in n boxes, some box contains at least two objects.
定理
- C(n, k) = n!/(k!(n − k)!) for 0 ≤ k ≤ n.
- Binomial theorem: (x + y)ⁿ = Σ_{k=0}^{n} C(n, k) xᵏ yⁿ⁻ᵏ.
- Σ_{k=0}^{n} C(n, k) = 2ⁿ.
- Inclusion–exclusion: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.
常见误解
- Using permutations when order does not matter.
- Thinking a pigeonhole argument must say which box contains two objects.
通向
可选发现
- Enumerative combinatorics Generating functions turn counting problems into algebra.
- ← Systematic listing and counting
学习路径
延伸阅读
- Arthur Engel, Problem-Solving Strategies (1998)