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

二项式反演

时间:2024-11-06 21:41:36浏览次数:2  
标签:aligned dbinom limits sum infin 反演 二项式

基本反演推论

对于 \(|F|=n,|G|=m\),要证明 \(F[x] = \sum_\limits{i=0}^{+\infin} A[x,i] G[i] \iff G[x]=\sum_\limits{i=0}^{+\infin} B[x,i] F[i]\)。

\(F\) 为 \(G\) 的前缀和,

\(F[x]=\sum_\limits{i=0}^{+\infin} [i\leq x]G[i] , G[x] = \sum_\limits{i=0}^{\infin} [i=x]F[i] - [i=x-1]F[i]\)

\((A*B)[x,y] = \sum_\limits{i=0}^{+\infin} A[x,i] B[i,y] = \sum_\limits{i=0}^x B[i,y] = \sum_\limits{i=0}^x [y=i]-[y=i-1] = [x=y]\) (注意,这里 \(i,y\) 的顺序)。

\(-1\) 的幂的移动:乘上你需要的,根据条件来。

二项式反演

代数:

要证 \(F(x) = \sum_\limits{i=0}^x (-1)^i\dbinom {x} {i} G(i) \iff \cdots(对称)\),那么有 \(A[x,i]=B[x,i](-1)^i \dbinom {x} {i}\) ,即证明 \(A*B=I\)。

\[\begin{aligned} (A*B)[x,y] & = \sum_\limits{i=0}^{+\infin} A[x,i] B[i,y] \\ & = \sum_\limits{i=0}^{+\infin} (-1)^i \dbinom {x} {i} (-1)^y \dbinom {i} {y} \\ & = \sum_\limits{i=0}^x (-1)^i \dbinom {x} {i} (-1)^y \dbinom {i} {y} \\ & = \sum_\limits{i=0}^x (-1)^{i+y} \dbinom {x} {i} \dbinom {i} {y} \\ & = \sum_\limits{i=y}^x (-1)^{i+y} \dbinom {x} {y} \dbinom {x - y} {i - y} \\ & = \dbinom {x} {y} \sum_\limits{i=y}^x (-1)^{i+y} \dbinom {x - y} {i - y} \\ & = \dbinom {x} {y} \sum_\limits{i=0}^{x-y} (-1)^{i+2y} \dbinom {x - y} {i} \\ & = \dbinom {x} {y} (1-1)^{x-y} \\ & = [x=y] \end {aligned} \]

考虑移动 \(-1\) 的幂。

\[(A*B)[x,y] = \textcolor{red}{\sum_\limits{i=0}^{+\infin} (-1)^i \dbinom {x} {i} (-1)^y \dbinom {i} {y}} = [x=y] \\ \begin{aligned} \textcolor{red}{RED} & = \sum_\limits{i=0}^{+\infin} \dbinom {x} {i} (-1)^{y+i} \dbinom {i} {y} \\ \end {aligned} \]

组合意义(这块结合题目理解):

错位排列:

钦定法考虑 \(|p|=n,f(n,k):\sum [p_i=i]=k,g(n,k):钦定k个,剩下随便\)。

考虑每个 \(g(n,k)\) 究竟统计到了哪些。

\[\begin{aligned} g(n,k)=\sum_\limits{i=k}^n \dbinom {i} {k} f(n,i) \iff f(n,k)&=\sum_\limits{i=k}^n (-1)^{i-k}\dbinom {i} {k} g(n,i) \\ & = \sum_\limits{i=k}^{n} (-1) ^ {i-k} \dbinom {i} {k} \dbinom {n} {i} (n-i)! \\ & = \sum_\limits{i=k}^{n} (-1) ^ {i-k} \dbinom {i} {k} \frac {n!} {i!} \end{aligned} \]

标签:aligned,dbinom,limits,sum,infin,反演,二项式
From: https://www.cnblogs.com/TongKa/p/18531115

相关文章

  • 反演
    反演“反演”的本质:两个函数之间的双向关系。我们通常可以用矩阵来描述这种关系。\[F=G*A\\F*A^T=G\]\(A\)即为关系矩阵。所谓反演就是关系矩阵的逆。\[B=A^T\\F*B=F*A^T=G\]利用关系矩阵,我们就可以实现两个矩阵(函数)的来回变化。二项式反演:形式一:\[A[n,i]=(-1)......
  • 基于Python星载气溶胶数据处理与反演分析技术
    Python作为一种强大且易于学习的编程语言,已广泛应用于数据科学和大气科学领域,Python凭借其强大的数据处理能力,可以高效处理海量的气溶胶数据。例如,通过Pandas库,研究人员可以进行高效的数据清洗、整理和分析;NumPy库则提供了强大的数值计算功能,能够快速进行各种数学和统计运算;Ca......
  • 二项式反演
    两年前学的东西,今天补一下笔记。Intro考虑\(n\)个有标号的元素。令\(f_n\)表示恰好\(n\)个元素满足条件(这里的条件取决于具体问题)的方案数,\(g_n\)表示指定\(n\)个元素满足条件的方案数。那么显然有\[g_n=\sum_{i=n}^mC_i^nf_i\]比如说,对于\(f_i\),可以选出\(n......
  • 基于Python星载气溶胶数据处理与反演分析
    Python作为一种强大且易于学习的编程语言,已广泛应用于数据科学和大气科学领域,Python凭借其强大的数据处理能力,可以高效处理海量的气溶胶数据。例如,通过Pandas库,研究人员可以进行高效的数据清洗、整理和分析;NumPy库则提供了强大的数值计算功能,能够快速进行各种数学和统计运算;Car......
  • 反演法控制(简单数学模型逐步推导)
    反演法(backstepping)设计思想是将复杂非线性的系统分解成不超过系统阶数的子系统,然后为每一个子系统分别设计Lyapunov函数和中间虚拟控制量,一直后退到整个系统,直到完成整个控制律的设计。解法:1,控制系统方程的导数最高阶次为n阶,含有系统输入项2,从0次阶逐级设计到n阶,其中用误......
  • 莫比乌斯反演
    前置知识积性函数积性函数指对于所有互质的整数$a$和$b$有性质$f(ab)=f(a)f(b)$的数论函数。若对于所有整数$a$和$b$都有性质$f(ab)=f(a)f(b)$成立,则称$f(n)$是完全积性的。例如$\phi(n)$为积性函数。数论函数定义数论函数(或称算术函数)指定......
  • 唐氏儿学莫比乌斯反演
    不会莫比乌斯反演,所以来学。很多博客看不懂/kk。题目P2522\[\sum\limits^b_{i=a}\sum\limits_{j=c}^{d}[\gcd(i,j)=k]\]容斥,\[\sum\limits^b_{i=a}\sum\limits_{j=c}^{d}[\gcd(i,j)=k]= \sum\limits^b_{i=1}\sum\limits_{j=1}^{d}[\gcd(i,j)=k]- \sum\limits^b_{i=1}\s......
  • 遥感技术在生态系统碳储量、碳收支、碳循环以及人为源排放反演等领域的技术发展
    以全球变暖为主要特征的气候变化已成为全球性环境问题,对全球可持续发展带来严峻挑战。2015年多国在《巴黎协定》上明确提出缔约方应尽快实现碳达峰和碳中和目标。2019年第49届 IPCC全会明确增加了基于卫星遥感的排放清单校验方法。随着碳中和目标以及全球碳盘点的现实压力,基于......
  • 组合数学(容斥与反演)
    前言校测被数学干碎了,赶紧来补一点容斥和反演的东西,能补多少算多少吧。特别说明:这一篇学习笔记是组合数学的第二篇。反演这是一个听着很高大上,实际不简单(因为wtcl)的东西。反演的实质对于形如下面的式子,我们称左右两式互为反演式:\[f_i=\sum^{i}_{j=1}A_{i,j}g_j\Leftrightar......
  • 二项式定理来源
    这是国庆作业。很巧的是我的二项式定理学习笔记正好是去年国庆时写的。因为是发视频作业,所以这算是稿子。在中国,成书于1世纪的《九章算术》提出了世界上最早的多位正整数开平方、开立方的一般程序。11世纪中叶,贾宪在其《释锁算书》中给出了“开方作法本原图”,满足了三次以上开......