组合数学

发布时间 2023-09-09 09:31:56作者: Biuld

常用积性函数:

\(\bullet\) 单位函数 \(\varepsilon(n)\text{ = }\begin{cases}\text{1, while n=1}\\\text{0, otherwise}\end{cases}\)
\(\bullet\) 幂函数 \(\begin{cases}Id_k(x)\text{ = }x^k\\Id(x)\text{ = }x\text{, }k\text{ = }1\\1(x)\text{ = }1\text{, }k\text{ = }0\end{cases}\)
\(\circ\) 除数函数 \(\begin{cases}\sigma_k(n)\text{ = }\Sigma_{d\mid{n}}\text{ }d^k\\\sigma(n)\text{ = }\Sigma_{d\mid{n}}\text{ }d\text{, }k\text{ = }1\end{cases}\)
\(\circ\) 欧拉函数 \(\varphi(n)\text{ = }\Sigma_{i = 2}^n\text{ }\left[n\perp i\right]\)

其中 \(\bullet\) 表示完全积性函数

因为这些都是积性函数,它们都满足 \(f(1) = 1\)
(我们常用 \(f, g, h\) 来代表积性函数

狄利克雷卷积

狄利克雷卷积是定义在数论函数间的二元运算。
定义式为:

以下出现的 \(*\) 不是我们常理解的乘,而是卷

\[(f*g)(n)\text{ = }\Sigma_{ij=n}\text{ }f(i)g(j) \]

也会写为:

\[(f *g)(n)\text{ = }\Sigma_{d\mid{n}}\text{ }f(d)g(\tfrac{n}{d}) \]

且若 \(f,g\) 是积性函数,则 \(f * g\) 也是积性函数

特殊函数的卷积:

  1. \(Id_k * 1\text{ = }\sigma_k\)
  2. \(\varphi * 1\text{ = }Id\)

性质:
交换律: \(f * g = g * f\)
结合律: \((f * g) * h = f * (g * h)\)
分配律: \(f * (g + h) = f * g + f * h\)

分配律只在函数加法下有效

单位元:
\((\varepsilon * f)(n)\text{ = }\Sigma_{xy = n}\text{ }\varepsilon(x)f(y)\text{ = }f(n)\) ,所以单位函数 \(\varepsilon\) 是狄利克雷卷积的单位元

逆元:
\(f * g\text{ = }\varepsilon\) ,则称 \(g\)\(f\) 的狄利克雷逆元,记作 \(f^{-1}\)
可证明 \(f^{-1}\) 是积性函数