关于二项式反演的一些思考
关于二项式反演的一些思考
今天T2考了二项式反演，转化之后要求的是n个非负整数的和为m，求其中有至少k个数(geq l)的方案数。
感觉是二项式反演，然后一看题解——至少是恰好的后缀和，仔细想想也没什么问题。可之前看的二项式反演博客里至少和恰好都是这样的关系：
[f(i)_ ext{至少}=sum_{jgeq i}^n {jchoose i} g(j)_ ext{恰好}
]
想了一会之后发现，二项式反演的“至少“不太像”至少"，而应该是”钦定“的关系。在这道题中，(k+1)个数(geq l)的方案减去(k)个(l)成为被组合数统计的非负整数插板，就有(k+1choose k)种情况。由于一种方案可能有多种钦定情况，也就不是后缀和而是二项式反演的组合数加权和形式。
所以应该是
[f(i)_ ext{钦定}=sum_{jgeq i}^n {jchoose i} g(j)_ ext{恰好}
]