反演 - 版本历史

33DAI：/* 狄利克雷卷积 */

2026-02-28T09:26:36Z

狄利克雷卷积

←上一版本		2026年2月28日 (六) 09:26的版本
第40行：		第40行：

	==狄利克雷卷积==		==狄利克雷卷积==

			数论函数 <math>f(n)</math> 和 <math>g(n)</math> 的 Dirichlet 卷积（Dirichlet convolution），记作 <math>f \ast g</math>，定义为数论函数

			<math>
			(f \ast g)(n) = \sum_{k\mid n}f(k)g\left(\dfrac{n}{k}\right) = \sum_{k\ell=n}f(k)g(\ell).
			</math>

	==莫比乌斯反演==		==莫比乌斯反演==

33DAI：/* 扩展 */

2026-02-28T09:05:55Z

扩展

←上一版本		2026年2月28日 (六) 09:05的版本
第74行：		第74行：
	f(n) = \sum_{n\mid d}g(d) \iff g(n) = \sum_{n\mid d}\mu\left(\dfrac{d}{n}\right)f(d).		f(n) = \sum_{n\mid d}g(d) \iff g(n) = \sum_{n\mid d}\mu\left(\dfrac{d}{n}\right)f(d).
	</math>		</math>


			[[文件:莫比乌斯反演.jpg\|缩略图\|替代=莫比乌斯反演\|莫比乌斯反演]]

33DAI：/* 莫比乌斯函数 */

2026-02-28T08:57:51Z

莫比乌斯函数

←上一版本		2026年2月28日 (六) 08:57的版本
第51行：		第51行：
	\begin{cases}		\begin{cases}
	1,&n=1,\\		1,&n=1,\\
	0,&n\text{是某个质数平方的倍数}\\		0,&n\text{是某个质数平方的倍数},\\
	(-1)^k,&n \text{是} k \text{个不同质数的乘积}.\\		(-1)^k,&n \text{是} k \text{个不同质数的乘积}.\\
	\end{cases}		\end{cases}

33DAI：/* 莫比乌斯函数 */

2026-02-28T08:57:29Z

莫比乌斯函数

←上一版本		2026年2月28日 (六) 08:57的版本
第51行：		第51行：
	\begin{cases}		\begin{cases}
	1,&n=1,\\		1,&n=1,\\
	0,&n\text{ ~~is divisible by a square~~ }~~>1,~~\\		0,&n\text{是某个质数平方的倍数}\\
	(-1)^k,&n\text{ ~~is the product of~~ }k\text{ ~~distinct primes~~}.\\		(-1)^k,&n \text{是} k \text{个不同质数的乘积}.\\
	\end{cases}		\end{cases}
	</math>		</math>

33DAI：/* 扩展 */

2026-02-28T07:53:36Z

扩展

@@ 第73行： / 第73行： @@
 <math>
 f(n) = \sum_{n\mid d}g(d) \iff g(n) = \sum_{n\mid d}\mu\left(\dfrac{d}{n}\right)f(d).
 </math>

33DAI：/* 莫比乌斯反演 */

2026-02-28T07:05:50Z

莫比乌斯反演

@@ 第67行： / 第67行： @@
 <math>
 f(n) = \sum_{d\mid n}g(d) \iff g(n) = \sum_{d\mid n}\mu\left(\dfrac{n}{d}\right)f(d).
 </math>

33DAI：/* 莫比乌斯反演 */

2026-02-28T06:12:06Z

莫比乌斯反演

←上一版本		2026年2月28日 (六) 06:12的版本
第61行：		第61行：
	# 当存在 <math>i</math> 使得 <math>e_i>1</math>，即存在任何素因数出现超过一次时，<math>\mu(n)=0</math>；		# 当存在 <math>i</math> 使得 <math>e_i>1</math>，即存在任何素因数出现超过一次时，<math>\mu(n)=0</math>；
	# 否则，对于所有 <math>i</math> 都有 <math>e_i = 1</math>，即任何素因数都只出现一次时，<math>\mu(n)=(-1)^k</math>，其中，$k$ 就是互异素因子的个数．		# 否则，对于所有 <math>i</math> 都有 <math>e_i = 1</math>，即任何素因数都只出现一次时，<math>\mu(n)=(-1)^k</math>，其中，$k$ 就是互异素因子的个数．

			===莫比乌斯反演===
			设 <math>f(n),g(n)</math> 是两个数论函数．那么，有

			<math>
			f(n) = \sum_{d\mid n}g(d) \iff g(n) = \sum_{d\mid n}\mu\left(\dfrac{n}{d}\right)f(d).
			</math>

33DAI：/* 莫比乌斯反演 */

2026-02-28T06:10:51Z

莫比乌斯反演

←上一版本		2026年2月28日 (六) 06:10的版本
第42行：		第42行：

	==莫比乌斯反演==		==莫比乌斯反演==

			===莫比乌斯函数===

			莫比乌斯函数（Möbius 函数）定义为

			<math>
			\mu(n)=
			\begin{cases}
			1,&n=1,\\
			0,&n\text{ is divisible by a square }>1,\\
			(-1)^k,&n\text{ is the product of }k\text{ distinct primes}.\\
			\end{cases}
			</math>

			具体地，假设正整数 <math>n</math> 有素因数分解 <math>n=\prod_{i=1}^kp_i^{e_i}</math>，其中，<math>p_i</math> 是素数，<math>e_i</math> 是正整数．那么，三种情形分别对应：

			# <math>\mu(1) = 1</math>；
			# 当存在 <math>i</math> 使得 <math>e_i>1</math>，即存在任何素因数出现超过一次时，<math>\mu(n)=0</math>；
			# 否则，对于所有 <math>i</math> 都有 <math>e_i = 1</math>，即任何素因数都只出现一次时，<math>\mu(n)=(-1)^k</math>，其中，$k$ 就是互异素因子的个数．

2026年2月28日 (六) 02:40 33DAI

2026-02-28T02:40:21Z

←上一版本		2026年2月28日 (六) 02:40的版本
第1行：		第1行：
			本页面大量引用 [https://oiwiki.org/ OI Wiki]

	组合数 <math>C_n^m</math> 常用符号 <math>\dbinom{n}{m}</math> 来表示，读作“<math>n</math> 选 <math>m</math>”。		组合数 <math>C_n^m</math> 常用符号 <math>\dbinom{n}{m}</math> 来表示，读作“<math>n</math> 选 <math>m</math>”。

33DAI：/* 二项式反演 */

2026-02-28T02:39:07Z

二项式反演

←上一版本		2026年2月28日 (六) 02:39的版本
第25行：		第25行：
	==二项式反演==		==二项式反演==

	记 <math>f_n</math> 表示恰好使用 $n$ 个不同元素形成特定结构的方案数，<math>g_n</math> 表示从 <math>n</math> 个不同元素中选出 <math>i \geq 0</math> 个元素形成特定结构的总方案数．		记 <math>f_n</math> 表示恰好使用 <math>n</math> 个不同元素形成特定结构的方案数，<math>g_n</math> 表示从 <math>n</math> 个不同元素中选出 <math>i \geq 0</math> 个元素形成特定结构的总方案数．

	若已知 <math>f_n</math> 求 <math>g_n</math>，那么显然有：		若已知 <math>f_n</math> 求 <math>g_n</math>，那么显然有：

反演 - 版本历史

33DAI：​/* 狄利克雷卷积 */

33DAI：​/* 扩展 */

33DAI：​/* 莫比乌斯函数 */

33DAI：​/* 莫比乌斯函数 */

33DAI：​/* 扩展 */

33DAI：​/* 莫比乌斯反演 */

33DAI：​/* 莫比乌斯反演 */

33DAI：​/* 莫比乌斯反演 */

2026年2月28日 (六) 02:40 33DAI

33DAI：​/* 二项式反演 */

33DAI：/* 狄利克雷卷积 */

33DAI：/* 扩展 */

33DAI：/* 莫比乌斯函数 */

33DAI：/* 莫比乌斯函数 */

33DAI：/* 扩展 */

33DAI：/* 莫比乌斯反演 */

33DAI：/* 莫比乌斯反演 */

33DAI：/* 莫比乌斯反演 */

33DAI：/* 二项式反演 */