二项式反演口胡

由于 wtcl ，所以讲得很基础

反演是什么

假设我们已经知道了 (g(n)=sum_{i=0}^n a_{ni}f(j)) 中的 (a) 这个系数数组

我们想要推求的是某一个 (b) 数组，满足 (f(n)=sum_{i=0}^nb_{ni}g(i))

我们考虑 (a,b) 两个数组有什么关系，假装我们现在已经的确找到了这样一个 (b)

那么：

所以我们只要求 (sum_{j=i}^nb_{nj}a_{ji}=[i=n]) 即可，这里可以把 (n,i) 看成是一个常量

也就是说，只要我们找到了这种 (b) ，就完成了我们的二项式反演，可以从更直观的角度理解上面那个式子的变化

（上图是白嫖的老师课件里老师白嫖的不知道哪位大佬的图）

二项式反演

基础式

我们现在的任务是证明 (sum_{i=j}^n(-1)^{i+j}binom nibinom ij=[j=n])

首先得知道这个东西：

一种方式是直接按照组合数定义展开证明，

另一种是组合数的意义：左式是 (n) 选 (i) ，(i) 选 (j) ，那我不妨直接 (n) 选 (j) ，然后从剩下的 (n-j) 个数中不足没有选的 (i-j) 个

那么：

这个时候我们直接二项式定理，((x+y)^nsum_{i=0}^n binom ni x^i y^{n-i}) 那么

再这里我们令 (0^0=1) ，那么原式显然当且仅当 (j=n) 时为 (1)

由于很难找到这种含 ((-1)^i) 的容斥系数，所以这个基本式作用不大

变式1

很容易证明它，我们的基本式叫做：(g(n)=sum_{i=0}^n(-1)^ibinom nif(i) Leftrightarrow f(n)=sum_{i=0}^n(-1)^ibinom ni g(i))

那么，我们令 (h(x)=(-1)^xf(x)) ，那么，利用基本式，

这里给出一个小应用：

题意：错排问题 ，有多少种排列方式，使得 $ p_i neq ?$

解题：虽然我们可以直接套错排公式，这里还是介绍一下二项式反演怎么做

定义 (?(i)) 表示恰好有 (?) 个错开，(?(i)) 表示至多有 (?) 个元素错开

那么有： $ ?(i) = ?!$ , (?(i) = sum_{j=0}(-1)^{i-j}binom ij f(j))

反演一下：(f(n)=sum_{i=0}^n(-1)^{n-i}binom ni g(i))

变式2

证明略去

推荐这些文章：

数学杂记

二项式反演
形式一：
\[f(n)=\sum_{i=m}^n\binom{n}{i}g(i)\Leftrightarrow g(n)=\sum_{i=m}^n(-1)^{n-i}\binom{n}{i}f(i)
\]形式二：
\[f(n)=\sum_{i=n}^m\binom{i}{n}g(i)\Leftrightarrow g(n)=...

数论 二项式反演 CF1228E题解

设 \(f_{i,j}\) 为恰好 \(i\) 行 \(j\) 列不满足条件的矩阵个数， \(g_{i,j}\) 为钦定 \(i\) 行 \(j\) 列不满足条件的矩阵个数。
容易得到：
\[g_{x,y}=\binom n x \binom n y (k-1)^{n^2-(n-x)(n-y)}k^{(n-x)(n-y)}
\]\[g_...

二项式反演&MIN-MAX容斥目害证

二项式反演
由于用了二项式反演，但是一直没证过，心里一直不踏实于是决定证一下
形式零
首先有多步容斥一开始的柿子：
\[|A_1\bigcup A_2 \bigcup A_3 ..... \bigcup A_n|=\sum\limits_{i=1}^n|A_i|-\sum\limits_{1<=i<j<=n}|A_i\...

关于二维二项式反演的正确性

前言
我第一次看到这个idea是神 \(Fuyuki\) 去年6月份的时候出了一套题目，里面用到了这个东西，不过他当时没有给出证明。后来看到了 \(boshi\) 在 \(Mina\) 上发的计数合集，里面证明了这玩意儿的正确性，我个人认为还是一个非常妙的东西，所以专门开个坑记录一下。
柿子
\[\text{if} \quad f_{n...

「关于我用三个小时推了一遍二项式定理这档事」

前两天考了个模拟赛，有个多项式题中间的递推式形如
\[f_{i,j}=f_{i-1,j-1}+(2^j-1)f_{i-1,j}
\]我一眼看出它其实是个 q-analog 理论的 2-斯特林数，然后调了三个小时发现柿子假了，最后到网上卡了个柿子才写对。于是打算找篇论文学习一下这种柿子都是怎么推的。
然后我就找到了论文 A，然后读 A 发...

CF908G&LOJ6697口胡

为什么我从ACAM做到了数位DP啊
考虑枚举前缀顶着最高位和后缀没有顶着的最高位。
考虑计算一个数对答案的贡献。统计 \(t\) 的出现次数记录到 \(c[t]\) 中。
贡献就是 \(\sum_{i=0}^{9}((\sum_{x=0}^{\sum_{j=i}^{9}c[j]-1}i\times10^{x})-(\sum_{x=0}^...

恒等式日记 2022.3.1

其实是昨天计应数课上的一个东西引出的, 总之, 我们要证明
\[\sum_r \frac 1{n-r} \binom r k = \binom n k (H_n - H_k).
\]首先我们需要证明一个 Lemma:
\[\sum_r \frac{(-1)^{r-1}}r \binom n r = H_n
\]其实很简单:
\[\new...

容斥原理证明

假设有 \(n\) 个基础集合 \(E_1\sim E_n\)，那么有
\[\left|\bigcup_{i=1}^n E_i\right|=\sum_{k=1}^n (-1)^{k+1}\sum_{1\le i_1<i_2<...<i_k\le n}|E_{i_1}\cap E_{i_2}\cap\cdots\cap...

一些公式和定理

公式＆定理：

两个互为反演的关系矩阵互逆

二项式反演 1
\(\large F(n) = \displaystyle\sum_{i=0}^{n} (-1)^i \binom{n}{i} G(i) \Longleftrightarrow G(n)=\sum_{i=0}^{n}(-1)^i \binom{n}{i}F(i)\)

...

莫比乌斯反演artalter级服务

莫比乌斯反演artalter级服务
其实啊，这个莫反非常的简单套路，就那么几个模型
1.公式
\[
\begin{aligned}
\text{莫比乌斯反演公式如下:}\\
&F(n)=\sum_{d|n}{f(d)}\\
\iff &f(n)=\sum_{d|n}{\mu(d)F(\frac{n}{d})}
\...