前言
笔者打ACM时候接触过一点组合数学，但没有系统的去学习。最近在学堂在线上找到一门《组合数学》的网课，于是以笔记形式总结记录所学组合数学知识。
本系列以每一章节形式发表，更新时间尽量半个月一更。（立个flag，督促学习）
排列组合
无重排列
从n个不同元素中取r个无重组合，并考虑顺序。
记： A n r A_{n}^{r} Anr? 或 P n r P_{n}^{r} Pnr?
性质：
- P n r = n ! ( n ? r ) ! P_{n}^{r} = \frac{n!}{(n-r)!} Pnr?=(n?r)!n!?
- 全排列 P n n = n ! P_{n}^{n} = n! Pnn?=n!
放球模型：把n个不同球放入r个不同盒子，每个盒子只能装一个球。
- P n r = n P n ? 1 r ? 1 P_{n}^{r} = nP_{n-1}^{r-1} Pnr?=nPn?1r?1? （选一个球放入第一个盒子，剩余n-1个球放入r-1个盒子内）
- P n r = P n ? 1 r + r P n ? 1 r ? 1 P_{n}^{r} = P_{n-1}^{r} + rP_{n-1}^{r-1} Pnr?=Pn?1