求证组合恒等式
首先Dk表示k个元素的错位排列。
1。n个元素的全排列有两种方案:
a)。n!种方法;
b)。分为n+1类:
恰有0个元素在原来的位置,有C(n,0)D0;
恰有1个元素在原来的位置,有C(n,1)D1;
恰有2个元素在原来的位置,有C(n,2)D2;
恰有3个元素在原来的位置,有C(n,3)D3;
。 。。。。。。。
恰有n个元素在原来的位置,有C(n,n)Dn,
所以第一个结论成立。
2。∑(k=0,n)kC(n,k)D(n-k)
=∑(k=1,n)k*n!/[k!*(n-k)!]*D(n-k)
=∑(k=1,n)n(n-1)!/[(k-1)!(n-k)!]*D(n-k)
=n∑(k...全部
首先Dk表示k个元素的错位排列。
1。n个元素的全排列有两种方案:
a)。n!种方法;
b)。分为n+1类:
恰有0个元素在原来的位置,有C(n,0)D0;
恰有1个元素在原来的位置,有C(n,1)D1;
恰有2个元素在原来的位置,有C(n,2)D2;
恰有3个元素在原来的位置,有C(n,3)D3;
。
。。。。。。。
恰有n个元素在原来的位置,有C(n,n)Dn,
所以第一个结论成立。
2。∑(k=0,n)kC(n,k)D(n-k)
=∑(k=1,n)k*n!/[k!*(n-k)!]*D(n-k)
=∑(k=1,n)n(n-1)!/[(k-1)!(n-k)!]*D(n-k)
=n∑(k=1,n)(n-1)!/[(k-1)!(n-1-k+1)]*D(n-k)
=n∑(k=1,n)C(n-1,k-1)D(n-k)
=n∑(k=1,n)C(n-1,n-k)D(n-k)
=n∑(i=0,n-1)C(n-1,i)D(n-i)
(因为n-k=i,k=1,2,3。
。。。n,则i=n-1,n-2,。。。3,2,1,0)
=n*(n-1)!=n!
即第二个等式成立。
。收起