社区讨论

蒟蒻求二项式反演的组合理解,急

学术版参与者 3已保存回复 11

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
11 条
当前快照
1 份
快照标识符
@lo27mr00
此快照首次捕获于
2023/10/23 09:19
2 年前
此快照最后确认于
2023/11/03 09:34
2 年前
查看原帖
集合A有元素:1,4,7,9,141,4,7,9,14
集合B有元素:2,3,5,8,102,3,5,8,10
现A,B两集合元素两两配对,求:配完后恰好有n对使得ai>bja_i>b_j有多少种情况。
我们现设f(n)f(n)表示恰好配成n对的方案数
根据二项式反演,我们应该得到下列式子 g(n)=i=0n(ni)f(i)g(n)=\sum\limits_{i=0}^n\dbinom{n}{i}f(i)
但是按我们最初的定义,g(i)g(i)既然表示至少选ii种,不应该等于恰好选0种+恰好选1种+恰好选2种...的所有情况吗?f(i)f(i)不是已经包含了恰好要选i种的所有情况了吗?,为什么还要乘上一个组合数呢?
PS1:本人会代数证明二项式反演,但是不明白其中的组合意义
PS2:g(i)怎么求不是重点,原题P4859 已经没有什么好害怕的了,是dp求至少配成i对有多少种情况,然后g(i)g(i)反演f(i)f(i)。重点是对于二项式反演的意义理解。

回复

11 条回复,欢迎继续交流。

正在加载回复...