蒟蒻求二项式反演的组合理解,急
  • 板块学术版
  • 楼主HugoHu
  • 当前回复11
  • 已保存回复11
  • 发布时间2023/7/16 11:40
  • 上次更新2023/11/3 09:34:18
查看原帖
蒟蒻求二项式反演的组合理解,急
68456
HugoHu楼主2023/7/16 11:40

集合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)。重点是对于二项式反演的意义理解。

2023/7/16 11:40
加载中...