2.4.3 组合恒等式组合恒等式有关二项式系数的恒等式至今已发现的就有上千个,而且还在不断地发展这些组合恒等式在许多算法分析中起着重要的作用,这里给大家介绍常用的几个等式 1201nnnnn L证明 方法 1 其组合意义的证明见定理 2.2.4方法 2 在二项式定理中令即可1xy等式 2:(2.4.9)024135nnnnnn LL证明 方法 1 在二项式定理中令,得:(2.4.10)1,1xy 0( 1)0n kkn k 将(2.4.10)式整理一下即得(2.4.9)式方法 2 等式(2.4.9)的组合意义是:在 n 个元素的集合中取 r 组合,r 为奇数的组合数目等于 r 为偶数的组合数目(包含 0 组合在内) 下面我们来建立 r 为偶数的组合与 r 为奇数的组合之间的一一对应,从而证明(2.4.9)式以 4 个元素构成的集合的一切组合为例,r 为奇数的组合有:, , ,a b c d, , , ,,,,;a b c d abc abd acd bcdr 为偶数的组合有:,,,,,,,ab ac ad bc bd cd abcd其中,表示取零个元素的组合。
从 n 个元素的集合中取 r 组合,r 可以有不同的值,但就元素而言,a只有含有元素和不含有元素两类若 r 为奇数的组合中含有,去掉便得一个 r 为偶数的组合例aaaa如,去掉得若 r 为奇数的组合中不含有,加上元素便构成一个 r 为偶数的组合例如,abcabcaa加上得见表 2.4.1bcdaabcd表表 2.4.1r 为奇数的组合abcdabcabdacdbcdr 为偶数的组合abacadbcbdcdabcd等式 3 112212nnnnnnn L证明 对等式:0(1)n niinxxi 两边在处求导数,得1x 11 11112nnn xxxnxn 1 11 011nnn jj xx iiinnnxxiii 从而:112212nnnnnnn L等式 4:0111nnkkkk L证明,用数学归纳法很容易证明此结论,下面通过其组合意义来分析其正确性。
是元集合的元子集的个数,这些子集可以分成如下类:1 1n k 1n121,,,nnAa aa aL1k 1n第(0)类:元子集中含,这相当于的 k 元子集再加上构成 A 的元子集,共1k 1a 1Aa1a1k 个;nk 第(1)类:不含的元子集,共有个;……;1a1k 1n k 第(n)类:不含,但含的元子集,共有个12,,na aaL1ka1k 0k 由加法原则知:1101nnnkkkk L等式 5:202nknn kn 证明 : 是元集合 A 的 n 组合和,把集合 A 分成两个集合和,使,则 A2n n 2n1A2A12AAn的 n 元子集可以分成如下类:从中选取个元素,从中选取个元素,将的1n1A(0)iin 2Ani1A个元素与的个元素并到一起构成 A 的第 i 类 n 元子集,而第 i 类子集的个数为i2Ani2 (0)nnnininii 由加法原则,有:202ninn in 利用上面的方法,可以证明下面更一般的公式:(2.4.11)0rimnmnirir恒等式(2.4.11)称为 Vandermonde 恒等式。
等式 6:0mimnmnirimr证明 利用的对称性和 Vandermonde 恒等式,有:m i mm imi00mmiimnmn irimiri0mj mj mmnmnmnjmijmrijmrimr 令。