求助,关于二项式反演
  • 板块学术版
  • 楼主SDNetFriend
  • 当前回复8
  • 已保存回复8
  • 发布时间2021/12/16 18:32
  • 上次更新2023/11/3 21:56:23
查看原帖
求助,关于二项式反演
206258
SDNetFriend楼主2021/12/16 18:32

关于二项式反演处理“至少”转“恰好”的情况有这么个式子:

g(x)=i=1x(xi)f(i)f(x)=i=1x(1)xi(xi)g(i)g(x)=\sum_{i=1}^x{x\choose i}f(i)\leftrightarrow f(x)=\sum_{i=1}^x(-1)^{x-i}{x\choose i}g(i)

代数意义证明问题不是很大,现在就不是很明白如何从组合意义去理解左侧这个式子。

现在我的理解是,g(x)g(x) 表示 nn 个元素中只有 xx 个元素可能为状态 AA,余下的都为状态 BB 的方案数,也就是至多 xx 个的方案数。f(x)f(x) 表示恰好有 xx 个元素为状态 AA 的方案数。

那么对于每一个 f(i)f(i) 的容斥系数不应该是考虑每种恰好的情况做出了几次贡献,也就是被多少个“至多”包含,那样系数不应该是 (nixi){n-i\choose x-i} 吗,为什么是 (xi){x\choose i} 呢,不是很理解。

2021/12/16 18:32
加载中...