组合数学
组合数学课程笔记（四）：容斥原理
$$一切繁复都洗涤，却染上重叠的星$$ 容斥原理 是容斥原理的基本公式。 但是我们并不经常的使用这个公式本身，我们一般使用这个公式的推论： 具体的理解这个式子，就是在全集 $\mathbb{U}$ 中，我们有若干个子集 $A_i$，其中的元素是坏的。现在我们需要找到不被任何子集包含的元素个数。 容斥 ......
【数论与组合数学 3】Hensel 引理、原根
Hensel 引理、原根 一、Hensel 引理 Hensel 引理：$\mathsf{f(x)}$ 是一个整系数多项式 $\mathsf{(\ f(x) \in Z(x)\ )}$，对于素数 p，整数 a 使得 $\mathsf{p^{k} \mid f(a)}$，$\mathsf{(\ f^{' ......
组合数学笔记-排列与组合
排列与组合 排列 排列的定义与基本性质 定义 设一个集合 $S$ 中有 $n$ 个元素，从中有序地取出 $m(0\leq m \leq n)$ 个元素排成一列， 称为 $S$ 的一个 $m$ 排列。两个排列相同，当且仅当元素相同且顺序相同。我们记 $\text{P}_n^m$ 、 $\text{A} ......
组合数学笔记-特殊计数数列
特殊计数数列 斐波那契数列 斐波那契数列的定义与基本性质 历史背景 斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。 定义 斐波那契数列 $F_n$ 有递推定义 $ ......