证明:
其中n≥k≥1。
事实上这是某道题的其中一步,在该题中
数组一共有k个分量。我们称作k-数组。
例如(A1,A2,A3)叫3-数组。
(A1,A2)叫2-数组。
等式左边的要求是
后数>=前数+1
第一个数>=1
最后一个数<=n
所以就是对所有的k-数组,每个数组对应于一个值,也就是P(i,j....r),把所有的P值加起来,每个值计算一次,一共有C(n,k)个数要加
比如
n=4
k=3
P(1,2,3)+P(1,2,4)+P(1,3,4)+P(2,3,4)
比如
n=4
k=2
P(1,2)+P(1,3)+P(1,4)+P(2,3)+P(2,4)+P(3,4)
右边是从n个数里找到k个不同的一共的个数,再乘P(i,j, ... ,r),就是C(n,k)*P(i,j,....r)
因为等式左边的i,j,r是动的,右边是定的,而且不知道P是什么,所以不能回答你的问题。
你可以增加一些条件,比如对于任何的k-数组(a,b,c,..z),P(a,b,c,...z)恒为一个常数。这时等式是对的。
看到了补充,所以我们知道当n,k固定的时候,P()恒为常数1/A(n,k),无论数组是什么,所以证毕。
P(1,2)+P(1,3)+P(1,4)+P(2,3)+P(2,4)+P(3,4)
你知道P(x,y)都彼此相等,1/A(4,2),而且一共有C(4,2)个,就是C(4,2)/A(4,2)
右边就是这个值。追问
对了,还有一个地方不是很明白,左边一共有C(n,k)个数相加是怎么推断出来的?
追答你想,如果该式成立,那么对于任何的一个k-数组,都有这个式子,显然你要求只要满足k-数组的P值相同即可
例如:
P(i)=2
P(i,j)=1
P(i,j,k)=5
是可以的
但是
P(1,2)=3
P(2,3)=4
是不可以的。
所以P是个只与数组元素个数有关的函数。这个式子都是对的。
左边一共C(n,k)个数是你要想像一下从n数中找到k个不同的数的方式。
左边的方式就是
把n个数从左到右排好,你从左边找,当然你知道一共要找k个,所以第一个人必须不能超过n-k+1,当第一个人定了之后,你找第2个,不能重复,所以必须至少要比第一个人的数字多1。依次类推。
恕我愚钝……能写一下详细的类推过程吗?
追答好吧,那我们就是用一个例子讲,比如n=6,k=3
左边的数的要求是
等式左边的要求是
后数>=前数+1
第一个数>=1
最后一个数<=n
所以可以的有
(1,2,3)(1,2,4)(1,2,5)(1,2,6)
(1,3,4)(1,3,5)(1,3,6)
(1,4,5)(1,4,6)
(1,5,6)
(2,3,4)(2,3,5)(2,3,6)
(2,4,5)(2,4,6)
(2,5,6)
(3,4,5)(3,4,6)
(3,5,6)
(4,5,6)
你看一下这些数,在思考一下如果你从1,2,3,4,5,6中选3个不同数,是不是就是这些。
左边的和号有k个,第1个和号表示第一个人的位置,第2个和号表示第2个人的位置,第k个和号表示第k个人的位置。
如果6选3,第一个人的位置就是1,2,3,4这4种。
然后选第2个人,看看在哪里呢?我们以第一个人是2为例子。
(2,3,4)(2,3,5)(2,3,6)
(2,4,5)(2,4,6)
(2,5,6)
第2个人由于在第一个右边,所以当第一个是2的时候,他只能是3,4,5。
如果第一个人是2,第2个人是4,第三个人是几呢?他只能是5,6。
(2,4,5)(2,4,6)
所以左边那一堆和号的意思就是按照我描述的方式,从n个人中找k个不同的人。