程序员的数学 - 排列组合

《程序员的数学》读书笔记目录

• 0的作用
• 罗马计数法
• 余数的运用
• 逻辑运算
• 排列组合
• 归纳与递归

认清计数对象

工具--树状图

集合

加法法则

集合间没有重复元素时
$$ |A ∪ B| = |A| + |B| $$

容斥原理

$$ |A ∪ B| = |A| + |B| - |A ∩ B| $$

乘法法则

$$ |A × B| = |A| × |B| $$

置换（substitution）

将N个事物按顺序进行排列

$$ P^N_N = N! $$

阶乘（factorial）

排列（permutation）

从N个事物中取K个按顺序进行排列

$$ P^N_K = \dfrac{N!}{(N - K)!} $$

组合（combination）

不考虑顺序

首先按顺序排列计数，然后除以重复度

$$ C^K_N = \dfrac{P^K_N}{PK_K} $$

置换、排列与组合的关系

置换与组合的结合就是排列

$$ P^K_N = P^K_K × C^K_N $$

---