首先我来说说什么是反演(inversion),对于一个数列来说,如果我们知道另外一个数列
,满足如下条件
反演过程就是利用 来表示出
本质上来说,反演其实是一个解线性方程组的过程,但是你观察后发现,这个矩阵实际上是一个三角矩阵,那必然存在着快捷的方法。对于使得这两个反演公式成立的这些系数应该满足什么条件呢?我们现在就来探讨一番!
我们首先讨论一下在什么情况下能够比较容易建立反演公式,之后介绍二项式反演以及它的两个应用,其中一个是错位排列问题
反演原理
首先我来介绍一个 函数,这个函数被称为 Kronecker's delta,它是这样定义的
这个函数的定义非常简单,我介绍它完全是为了后面叙述的方便
好,我们现在来考虑一下上面的式子,假设对于任意 都满足
那么我们来考虑一下下面这个式子成立应该要满足什么条件
我们可以直接将 代入上式来计算左边的求和
对于最后一步,实际上是变换了求和顺序,为了更容易理解,我按照矩阵的形式写出来
那么,前一个求和是先对行进行,再将各行加起来,后一个就是先对列进行,再将各列加起来
这样的话,等式 成立的充要条件就是
同样地,我们反过来也能知道,整个反演公式要成立还需要满足一个必要条件
也就是,如果你发现某个数列满足上面这个条件,那么你就可以直接建立起反演公式!
事实上,在快速傅立叶变换和逆变换你也可以认为是一个反演的过程,具体可以看这一步的推导,你会发现它和这个很相似。此外,第一类 Stirling 数和第二类 Stirling 数也满足这个条件,不过我暂时没有发现它们建立起的反演公式有什么应用。我下面来介绍一个比较有用的反演公式
二项式反演
下面就来介绍二项式反演(binomial inversion),这可以表示成
你会发现这个式子具有极强的对称性!另外一个更加常见的形式是
现在我们先来给出这个公式的一个容斥解释,之后从代数角度证明一下这个式子,最后介绍两个它的应用
反演?这里就是容斥
实际上,二项式反演是容斥原理(inclusion-exclusion principle)的一种最常见的特例子,让我们先来回忆一下容斥原理
设集合 中具有性质
的对象的集合为
,那么不具有这些性质的对象的集合大小为
那么,考虑这样一种特殊的情况,若对于集族 中任意
个集合的并集的大小都是
,我们不妨设
明显的,在 中一共有
个这样的不同交集。另外,我们定义
这样一来,上面的容斥结果就是
由于 中任意
个集合的交集大小都是
,上面的公式左边的项也只和集合个数有关,我们可以设
同样令 ,那么同样使用容斥原理
这也正是 的表达式,因此,整个证明就完成了!
代数证明
根据文章开头反演原理部分的讨论,加上这个公式的对称性,我们只需要证明
这里
好,现在我们来证明它,首先需要一个二项式系数的知识
如果运用组合推理就相当于是,你有一个 元素集
,现在对
进行计数,其中
且
,首先对
计数,
的
子集有
,然后对
计数,
的
子集有
接下来换一种方式,先对 进行计数,
显然是
的子集,有
种方案,由于要求
,
中
个元素必须在
中,
还剩下
个不确定的元素,
还有
个可以用的元素,一共有
种,于是就得到上面的恒等式,那么可以得到
这样最后就可以得到
于是,反演公式就建立了!
应用
错位排列问题
求有多少个长度为 的排列
,满足对于所有的
,使得
这个问题有很多解法,我们来介绍一个有意思的解法:
为了叙述方便,我们称位置 是不变的当且仅当
首先我们知道,如果不考虑 这个条件,问题是很简单的,长度为
的排列一共有
种。并且这些排列是由恰好有
个位置是不变的排列组成,也就是,如果我们设
为恰好有
个位置是不变的排列的个数,那么可以得到
是否觉得和刚刚的反演公式很相似?这里的 就是
,那么,使用二项式反演可以得到
这也就是我们熟悉的错位排列
球染色问题
有 个球排成一行,你有
种颜色,要求给每一个球染色,相邻两个球颜色不可以相同,并且每种颜色至少使用一次
这是经常在高中数学组合那个部分见到的一个问题,只不过高中题目中数都很小
还是和刚刚的想法一样,如果没有每种颜色至少一次这个条件,那么问题很简单,答案是 。这些方案是由恰好使用了
种颜色的方案组成的,那么设
为恰好使用了
种颜色的方案数,可以得到
经过反演得到
结语
其实不仅仅是二项式反演,很多问题中最经常用到的方法就是把条件放宽,求出一个好计算的问题,之后加上这个条件得到方程,利用反演公式算出答案,思想很类似的一题是 BZOJ-3456. 城市规划
請問二項式反演那邊-1的次方是n+i還是n-i呢
其实没有太大区别,假设
非负的话,
最下面的式子是
吧 qwq
没错… 我打错了QAQ
哇大神很喜欢你的blog, 能加个qq吗...(一个还在路上的oier
作者大大,你在“反演原理”里的“为方便理解写出的矩阵”应该是错误的吧。 你接下来的描述与式子相符,但矩阵无法与你的描述相符。 我自己尝试根据式子写了一下,是否应该是 bn0 a00 f0 bn1 a10 f0 bn1a11f1 bn2 a20 f0 bn2a21f1 bn2a2f2 ...
好像评论里排版有点问题,主要问题在f应是每一行从左至右递增的 不过你的这篇博文真的很不错,十分感谢
没错 是这样。感谢~
请问最后如果是要恰好出现t次t<=k怎么做,我尝试推广了一下,好像有点问题
好吧我sb了
谢谢博主!受教了
代数证明的一开始那个式子是不是$\delta(n, j)$呀...
同问
**不变**的定义是不是写错了,应该是$a_i /neq i$啊,这样$f_n$是错排公式才对
$i \neq a_i$
好文章!谢谢博主
👍 补充个事,(6)(7)两式应该是等价的,都是(3)(4)成立的充要条件,可以看成互逆的下三角矩阵