集合A有元素:1,4,7,9,14
集合B有元素:2,3,5,8,10
现A,B两集合元素两两配对,求:配完后恰好有n对使得ai>bj有多少种情况。
我们现设f(n)表示恰好配成n对的方案数
根据二项式反演,我们应该得到下列式子
g(n)=i=0∑n(in)f(i)
但是按我们最初的定义,g(i)既然表示至少选i种,不应该等于恰好选0种+恰好选1种+恰好选2种...的所有情况吗?f(i)不是已经包含了恰好要选i种的所有情况了吗?,为什么还要乘上一个组合数呢?
PS1:本人会代数证明二项式反演,但是不明白其中的组合意义
PS2:g(i)怎么求不是重点,原题P4859 已经没有什么好害怕的了,是dp求至少配成i对有多少种情况,然后g(i)反演f(i)。重点是对于二项式反演的意义理解。