排列组合，数论和信息学

几何微粒子 · 2022-08-15 19:38:22 · 个人记录

警告：前方高能

本笔记偏向于信息学。如果您想观看偏向于数学的笔记，请从洛谷出门拐弯到数学领域。

Chapter I 卡特兰数

典型模型：

有一家电影院票价5美刀。
有2n个客人。
其中n个客人有5美刀。
另外n个客人有10美刀。
做生意需要找零钱，所以当客人付出10美刀时，你需要找零5美刀。
问题在于，你一开始没有钱。所以你需要在自己足够的有5美刀钱币时才能收10美刀钱币。
求你能成功找零的情况下，客人来的顺序的方案数。

答案：h_n

解析：

创建一个n*n的矩阵。现在我们在矩阵的(1,1)处。
如图：

n=5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

假设收一个5美刀钱的人等价于向下走一步。
收一个10美刀钱的人等价于向右走一步。
则问题转化为：保证当前位置不在主对角线（左上->右下）上方（可以在线上）。
如图，* 为可走区域：

n=5
* 0 0 0 0
* * 0 0 0
* * * 0 0
* * * * 0
* * * * *

公式：

• h_i=\displaystyle\sum\limits_{i=0}^{n-1} h_i\times h_{n-i-1}
• h_n=\displaystyle\frac{C^n_{2n}}{n+1}
• h_n=C_{2n}^n-C_{2n}^{n-1}
• h_n=h_{n-1}\times(4n-2) /(n+1)

Chapter II 斯特林数

• 第一类

  • 递推公式：$S_{1_{n,m}}=S_{1_{n-1,m-1}}+S_{1_{n-1,m}}\times (n-1)

  • 第一类斯特林数很难想出来

• 第二类

  • 递推公式：$S_{2_{n,m}}=S_{2_{n-1,m-1}}+S_{2_{n-1,m}}\times m

  -第二类斯特林数相对第一类而言，较为简单，但是还是难

斯特林数行列的模板都是黑题

数论没一个简单的东西，全寄吧是废人的题

Chapter III Lucas定理

前置芝士: C_n^m可以表示为\begin{pmatrix}n\\m\end{pmatrix}

然后你就可以这样祖安他人了。正确的

一个质数p，如果n=sp+q，m=tp+r

则\begin{pmatrix}n\\m\end{pmatrix}\equiv\begin{pmatrix}s\\t\end{pmatrix}\begin{pmatrix}q\\r\end{pmatrix}\pmod{p}

引理：

1. p为质数时，\begin{pmatrix}p\\q\end{pmatrix}\equiv0\pmod{p}

2. 多项式\displaystyle f(x)=\sum\limits_{i=0}^{N}a_ix_i，g(x)=\sum\limits_{i=0}^{M}b_ix_i

3. (1+x)^n=\displaystyle \sum\limits_{i=0}^{n}C_n^ix^i

Chapter IV 欧拉函数和素数函数

素数函数：\pi(n) 表示n内质数的个数。

欧拉函数：\varphi(n) 表示n内和n互质的数的个数。

• 欧拉函数计算公式：\varphi(m)=m\displaystyle\prod\limits_{p\mid m}(1-\frac{1}{p})

• 欧拉函数的性质：

  • 若p是质数，则\varphi(p)=p-1

  • \forall m \in N^+$，有$\displaystyle\sum\limits_{d\mid m}\varphi(d)=\sum\limits_{d\mid m}\varphi(\frac{m}{d})=m

    • 证明：

    • 对\forall d\mid m，1\le a \le m，设(a,m)=d，则(\displaystyle\frac{a}{d},\frac{m}{d})=1，则(a,m)=d有\varphi(d)种取法。则\displaystyle\sum\limits_{d\mid m}\varphi(\frac{m}{d})=m

Chapter V 素数筛法

不提供证明，因为作者不会微只因分