组合数有两个基本性质:对称性和递推性。
对称性指的是当选取k个元素的组合时,与其补集中选取n-k个元素的组合是等价的。
递推性则指的是组合数可以用递归的方式计算,即C(n,k)=C(n-1,k)+C(n-1,k-1),即从n-1个元素中选取k个元素和选取k-1个元素的组合数之和。
这两个性质可以相互推导,即将递推式中的C(n-1,k)和C(n-1,k-1)代入到对称性中,得到C(n,k)=C(n,n-k)。
这个式子也可以通过代入n=k的情况,即C(n,n)=1,来证明。
组合数性质2推导过程
组合数有两个基本性质:对称性和递推性。
对称性指的是当选取k个元素的组合时,与其补集中选取n-k个元素的组合是等价的。
递推性则指的是组合数可以用递归的方式计算,即C(n,k)=C(n-1,k)+C(n-1,k-1),即从n-1个元素中选取k个元素和选取k-1个元素的组合数之和。
这两个性质可以相互推导,即将递推式中的C(n-1,k)和C(n-1,k-1)代入到对称性中,得到C(n,k)=C(n,n-k)。
这个式子也可以通过代入n=k的情况,即C(n,n)=1,来证明。
不妨从这个公式出发,结合组合数的定义,看看我们可以得出什么样的结论,加入最终的结论显而易见,那么我们沿着相反的推导方向就可以得出组合数的这个性质第二个约去相同因子即可得到第三个公式,最后的结果是显而易见的,