关于二项式反演处理“至少”转“恰好”的情况有这么个式子:
g(x)=i=1∑x(ix)f(i)↔f(x)=i=1∑x(−1)x−i(ix)g(i)
代数意义证明问题不是很大,现在就不是很明白如何从组合意义去理解左侧这个式子。
现在我的理解是,g(x) 表示 n 个元素中只有 x 个元素可能为状态 A,余下的都为状态 B 的方案数,也就是至多 x 个的方案数。f(x) 表示恰好有 x 个元素为状态 A 的方案数。
那么对于每一个 f(i) 的容斥系数不应该是考虑每种恰好的情况做出了几次贡献,也就是被多少个“至多”包含,那样系数不应该是 (x−in−i) 吗,为什么是 (ix) 呢,不是很理解。