真正的反演笔记

目录

• 真正的反演笔记
  • 前置知识
    • 偏序关系
    • 卷积
    • Kronecker delta 函数
    • Riemann zeta 函数
  • 莫比乌斯函数
    • 性质
  • 不同偏序集上的莫比乌斯函数的性质
• 参考文献

真正的反演笔记

论看书看到自闭是一种怎样的体验
warning：本文可能过于理论化。
本文包含的内容：容斥原理，二项式反演，数论反演

前置知识

偏序关系

偏序关系

卷积

设\(\mathcal F(X)\)是一个只要满足\(x\not \le y\)就有二变量函数\(f(x,y)\)的所有实值函数的集合
设函数\(f,g\in\mathcal F\)
定义这两个函数的卷积为

我们发现，如果这个东西类似于矩阵乘法。（要满足一定的条件）

Kronecker delta 函数

定义Kronecker delta函数\(\delta\)
\(\delta(x,y) = [x=y]\)
如果我们把二元函数看作是矩阵的话，\(\delta\) 相当于是单位矩阵

Riemann zeta 函数

定义 Riemann zeta函数为\(\zeta(x,y)=[x\le y]\)
顺带一提，这个函数实际上是偏序集\(\le\)的一种表现，可以看作是1的上三角矩阵。

莫比乌斯函数

显然有\(f^{-1}*f = \delta\)
我们定义莫比乌斯函数\(\mu=\zeta ^{-1}\)
即\(\mu\)是\(\zeta\)的逆函数

性质

根据逆函数的推倒

在偏序集\((N,≤)\)上的性质

事实上这个结论对于所有可数的全序集而言均符合。

不同偏序集上的莫比乌斯函数的性质

直接粘了Xris大神的blog

参考文献

不一样的反演魔术
Introductory Combinatorics Fifth Edition