Knowledge
组合数学知识点
用于复习排列组合、鸽巢原理、容斥原理和递推关系。
排列与组合
排列考虑顺序，组合不考虑顺序。
重要公式
- P(n,r)=n!/(n-r)!
- C(n,r)=n!/(r!(n-r)!)
常见考法
区分 P(n,r) 与 C(n,r)，判断题目是否需要计入顺序。
复习提示
- 先问顺序是否重要，再选公式。
易错提醒
把“选出集合”和“排成序列”混为一谈。
鸽巢原理与容斥
鸽巢原理用于证明必有重复或至少数量，容斥原理用于修正重复计数。
重要公式
- 至少一个盒子不少于 ⌈n/k⌉
- |A∪B|=|A|+|B|-|A∩B|
常见考法
同余类、星期几、抽屉分配、并集计数。
复习提示
- 容斥题先标出每个对象被数了几次。
易错提醒
容斥中交集被多算或少加是最常见错误。