n的k排列证明

作者: admin
标签: 组合数学
更新: 6/27/2019, 2:27:20 PM
P(n,r)P(n,r)代表元素总数为n的集合中取出r个元素进行排列 个数

定理1

P(n,r)=n×(n1)×...×(nr+1)P(n,r)=n\times(n-1)\times...\times(n-r+1)也可写作 P(n,r)=nr+1nP(n,r) = \prod_{n-r+1}^{n}

证明:

SS是具有 nn个元素的集合,我们取第一个元素时有nn种可能,取第二个元素时有n1n-1种可能,依次类推, 第 rr次有n(r+1)n-(r+1)种可能 ( r<nr<n)。我们要获取P(n,r)P(n,r)可用全排列即 n!n!除去多余部分排列(即 0nr\prod_0^{n-r} )。
并约定0!=10!=1,

所以证得:

P(n,r)=n!(nr)!=nr+1nP(n,r)=\frac{n!}{(n-r)!} =\prod_{n-r+1}^{n}

此证明过于简洁,仅作参考。前缀知识包括计数乘法定理

删除
修改
点击登陆评论