首页 > 其他分享 >二项式反演小记

二项式反演小记

时间:2024-06-07 19:11:52浏览次数:22  
标签:begin 二项式 end sum 反演 choose delta aligned 小记

篇幅有限,仅记录公式及极简证明。

定义

\[\begin{aligned} &f(n)=\sum_{i=0}^n(-1)^i{n\choose i}g(i)\Leftrightarrow g(n)=\sum_{i=0}^n(-1)^i {n\choose i} f(i) & (1) \\ &f(n)=\sum_{i=0}^n{n\choose i}g(i)\Leftrightarrow g(n)=\sum_{i=0}^n(-1)^{n+i} {n\choose i} f(i) & (2) \\ &f(n)=\sum_{i=0}^m{i\choose n}g(i)\Leftrightarrow g(n)=\sum_{i=0}^m(-1)^{n+i}{i\choose n} f(i),m\ge n & (3) \end{aligned} \]

注意 \((2)(3)\) 式的 \((-1)\) 的指数可能和别处不一样,但是本质是一样的,而且我更倾向用这种表述,理由见下。

证明

\((1)\)

实际上组合意义同样而可以证明,但是并不完美。

因此从代数角度证明:

\[\begin{aligned} &\sum_{i=0}^n (-1)^i {n\choose i} f(i) \\ =&\sum_{i=0}^n(-1)^i{n\choose i}\sum_{j=0}^i(-1)^j{i\choose j}g(j) \\ =&\sum_{i=0}^n(-1)^{n}\sum_{j=0}^i (-1)^{j} (-1)^{n-i}{n\choose i}{i\choose j}g(j) \end{aligned} \]

这里可以很容易发现不同的意义,\((-1)^{n-i}{n\choose i}\) 的意义是 \((x-1)^n\) 中 \(x^{i}\) 中的系数;而 \(i\choose j\) 表示 \((x+1)^i\) 中 \(x^{j}\) 的系数,也可以表示 \(x^i\) 中 \((x-1)^j\) 的系数。合在一起可以容易得到意义是 \((x-1)^n\) 中 \((x-1)^j\) 的系数,显然等于 \(\delta_{nj}\),因此有:

\[\begin{aligned} &\sum_{i=0}^n (-1)^i {n\choose i} f(i) \\ =&\sum_{i=0}^n(-1)^{n}\sum_{j=0}^i (-1)^j (-1)^{n-i}{n\choose i}{i\choose j}g(j) \\ =&\sum_{i=0}^n(-1)^{n}\sum_{j=0}^i (-1)^j \delta_{nj} g(j) \\ =&\sum_{i=0}^n(-1)^{n}(-1)^i\delta_{ni} g(i) \\ =&g(n) \end{aligned} \]

即证。

\((2)(3)\) 同理。

标签:begin,二项式,end,sum,反演,choose,delta,aligned,小记
From: https://www.cnblogs.com/imcaigou/p/18237738

相关文章

  • 算法随笔——数论之莫比乌斯反演
    链接链接2链接3链接4前置知识:数论分块可以求形如:\(\sumf(i)g(\left\lfloorn/i\right\rfloor)\)的东西。原理如下:比如说求$\sum_{i=1}^{10}\left\lfloor10/i\right\rfloor$得到:10532211111可以发现有一些块的数值是一样的。具体一点可以发现\([l......
  • 嵌入式模块学习小记(未分类)
    L298N电机驱动板模块OutputA:接DC电机1或步进电机的A+和A-;OutputB:接DC电机2或步进电机的B+和B-;5VEnable:如果使用输入电源大于12V的电源,请将跳线帽移除。输入电源小于12V时短接可以提供5V电源输出;+5VPower:当输入电源小于12V时且5VEnable处于短接状态,可以提......
  • 二项式反演
    二项式反演简介二项式反演可以用来解决一些计数问题,是连接至少/至多与恰好两类函数的桥梁。形式一\[f(n)=\sum_{i=0}^n(-1)^i\binom{n}{i}g(i)\\g(n)=\sum_{i=0}^n(-1)^i\binom{n}{i}f(i)\]证明代\(g(n)\)入第一条式子。\[\begin{aligned}f(n)&=\sum......
  • 莫比乌斯函数和莫比乌斯反演
    莫比乌斯函数定义莫比乌斯函数为\(\mu(n)=\begin{cases}1&n=1\\(-1)^r&&n=p_1\timesp_2\timesp_3\cdots\cdotsp_r\\0&\text{其他}\end{cases}\)。定理:\(\sum_{d|n}\mu(d)=\begin{cases}1&n=1\\0&n>......
  • 狄利克雷卷积与莫比乌斯反演
    狄利克雷卷积与莫比乌斯反演主要内容数论函数狄利克雷卷积积性函数莫比乌斯反演数论分块提要\(a\botb\)表示\(a\)与\(b\)互质。数论函数数论函数是一类定义域是正整数的函数,可以类比数列。加法,数乘比较简单,略过。狄利克雷卷积定义两个数论函数的狄利克雷卷......
  • 上海咸菜小记
    我在上海的初中念过书,中午的伙食是很好的。分饭菜时,每个人都是一格子饭一大坨菜和一碗汤,荤食往往是肉圆大排,或者是鸡腿大虾,吃的满嘴流油。鲜有剩下的,剩的最多的是咸菜。在那个高乐高横行的时代,咸菜是卑贱的食物,本地人是不吃的,甚至吃饭时会把咸菜一粒粒的挑出来。班主任会......
  • CentOS7.9安装mysql-8.0.36踩坑小记
    前言:最近想在一台测试服务器上,安装下最新的MySQL8.0版本数据库,想着挺简单的一件事,之前也手搓过8.0安装,这不手到擒来,没想到马失前蹄,遇到了一个小坑,耗费了不少时间,简单写篇文档记录下吧。1.排错记录执行./mysqld--initialize初始化命令后,提示报错,如下图所示看报错应该是......
  • 莫比乌斯反演即狄利克雷卷积速通
    莫比乌斯反演速通前言由于请假错过了讲课,所以莫反是我第一个需要自学的难度不小的数学知识。自学的过程的狼狈的,旁边也曾是自学的czn告诉我如果学会“狄利克雷卷积”就可以对“莫比乌斯反演”的理解进行“降维打击”。他还十分热心地带着我速通了一遍狄卷与莫反。一知半解,就......
  • CF1278F Cards(斯特林数+二项式定理)
    题意简述有\(m\)张牌,其中有一张是王牌。你现在可以洗\(n\)次牌(每种牌堆序列等概率出现),然后查看牌堆顶的第一张牌。设\(x\)为\(n\)次洗牌中第一张牌是王牌的次数,则得分为\(x^k\)。求得分的期望值对\(998244353\)取模的值。\(1\len,m<998244353,k\le5000\)分析将......
  • 研发云Git使用小记
    准备工作:1、GIT命令工具(安装方式:无脑下一步)https://xaiohutongxue.lanzouq.com/iUKZ71yvhlrc2、研发云用户名 3、研发云邮箱 4、打开此电脑“C:\Users\用户名”文件夹正式开始一、运行GIT在用户名文件夹下右击运行GIT二、生成SSH密钥1、在GIT命令行中粘贴命令ssh-k......