「笔记」数学公式杂记

目录

• 写在前面
• 等比数列
• 素数唯一分解定理
• 约数个数定理
• 约数和定理
• 错排公式

写在前面

收录了一些比较杂的定理性质啥玩意的

等比数列

对于所有项，均满足 \(\frac{a_i}{a_{i - 1}} = q\)，其中 \(q\) 是等比

第 \(n\) 项的值：\(a_n = a_1 \times q^{n - 1}\)

前 \(n\) 项的和：\(\sum_{i = 1}^{n}a_i = \frac{a_1 \times (1 - q^n)}{1 - q}\)

如果在模 \(m\) 的意义下，可以利用费马小定理求出 \(1-q\) 的逆元来做

素数唯一分解定理

任意一个数 \(x\) ，均能分解成几个素数的乘积，如果不计顺序，分解方式是唯一的

设每一个素数为 \(p_i\)，则有

\[x = \prod_{i = 1}^{k}p_i^{a_i} \]

其中 \(k\) 表示一共分解为 \(k\) 个素数，\(a_i\) 表示第 \(i\) 个素数出现次数

约数个数定理

对于任意一个数 \(x\) ，它的约数个数为

\[num = \prod_{i = 1}^{k}(a_i + 1) \]

证明：

对于每个质因子都有 \(a_i + 1\) 中选择方式，根据乘法原理将所有质因子的选择方式乘起来即可

约数和定理

对于任意一个数 \(n\) ，它的所有约数的和为

\[S = \prod_{i = 1}^{k}(\sum_{j = 0}^{a_i}p_j) \]

证明（或者是一种理解方式？）：

我们知道每个质因子都有 \(a_i + 1\) 中选择方式，考虑构造一个生成函数 \(F(n)\)

那么第 \(i\) 项为 \((p_i^0 + p_i^1 + ... + p_i^{a_i - 1} + p_i^{a_i}) = \sum_{j = 0}^{a_i}p_i^j\)

考虑生成函数的形式，

\[F(n) = \sum_{j = 0}^{a_0}p_0^j \times \sum_{j = 0}^{a_1}p_1^j \times ... \times \sum_{j = 0}^{a_{k - 1}}p_{k - 1}^j \times \sum_{j = 0}^{a_k}p_k^j \]

即可得到上面的约数和定理

如果把 \(F(x)\) 展开的话，每一项恰好是一个约数，求和恰好是答案

优化：

发现后面的 \(\sum_{j = 0}^{a_i}p_i^j\) 是一个等比数列形式，考虑化简一下，变成

\[S = \prod_{i = 1}^{k}(\frac{p_i^{k+1} - 1}{p_i - 1}) \]

错排公式

• 容斥？

\[n! \times \sum_{i=0}^{n} \frac{-1^i}{i!} \]

• 另一种容斥？（大概和上面的相同）

\[\sum_{k=0}^{n} (-1)^k \binom{n}{k} \times k! \times (n-k)! \]

大概就是考虑有 \(k\) 个位置在原位置上，然后容斥。

• 递推式？

\[f(n) = (n-1)f(n-1)f(n-2) \]

三个公式之间应该可以相互推导。