组合计数学习笔记

Million1000 · 2023-07-14 10:03:07 · 个人记录

组合数的原理、应用与求法

数论函数，是指定义域为自然数，值域为复数的一类函数，每个数论函数可以视为复数的序列。

积性函数，是指对所有互质的整数 a 和 b 都有 f(ab)=f(a)f(b) 的数论函数。

完全积性函数是指对所有数a 和 b 都有 f(ab)=f(a)f(b) 的数论函数.

以下为积性函数的例子：

\mu(x) =\begin{cases}0,\quad\exists b_i>1\\1\quad\ otherwise\end{cases}
Id_k(x) = x^k \qquad Id(x) = x\qquad 1(x) = 1
\varphi(x) = \sum\limits_{i=1}^{x}[x \perp i]
\sigma_k(x) = \sum\limits_{d\mid x}{d^k}\qquad \sigma(x) = \sum\limits_{d\mid x}{d}
d(x) = \sum\limits_{d\mid x}{1} = \prod\limits_{i=1}^{cnt}{(b_i+1)}

根据容斥原理可证：

\varphi(x) = n\prod\limits_{p\mid n}{(1-\frac{1}{p})}\qquad p\in \mathbb{P}

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

定义式为：

(f*g)(n) = \sum\limits_{d \mid n}{f(d)g(\frac{n}{d})}

根据（4）可知 1 是 \mu 的狄利克雷逆

由此可以推出莫比乌斯反演公式：

g = f*1 \Leftrightarrow f=g*\mu

比如：

Id = \varphi*1 \Leftrightarrow \varphi=Id*\mu

斯特林数：2023.10.11.T4 noip模拟2