排列组合基本概念与公式caequa
🖨️

排列组合基本概念与公式caequa

Created
Oct 15, 2020 12:59 PM
Tags
数学
排列组合
Author
注:此文章不适合初学者(网上适合初学者的排列组合入门文章很多),适合有一定基础的回顾知识点,有一定的拓深,并为后面内容作出铺垫。

基本原理:

乘法原理,加法原理,容斥原理,这个你肯定会。

排列:

排列与不全相异元素的排列

这里用表示从不同的数中选个数的排列数。
这就是排列公式了。
特别地,当时,叫做这n个数的全排列;时,叫做选排列。
如果在个元素中,有个元素彼此相同,个元素彼此相同……个元素彼此相同。此时,这个元素的全排列叫做不全相异元素的全排列,计算公式为;这个元素选个的排列数叫做不全相异元素的选排列,计算公式为
 

错位排列

的一个全排列,若是任意的意思),都有,则称的一个错位排列。这里用表示的错位排列个数。有
注意的阶乘是
可以算得 ……
其实同样的,还有以下四个递推计算方法:
 
我们可以来推导一下第一个递推式。先从错位排列的实际意义出发。假设有个人,个物品,第一次每人各取一件物品,要求第二次每人仍各取一件物品,但是所取物品应与前一次所取到的物品不同,此时第二次可行的方案总数就是
我们不妨假设号同学第二次拿到的物品是原来第号同学第一次拿到的物品,这时,我们可以分两种情况讨论:
  1. 号同学第二次拿到的物品是号同学第一次拿到的物品,那么此时其他个人就自给自足,号同学和号同学的方案唯一,已经确定,此时的总方案数就是其他个人的总方案数,即
  1. 号同学第二次拿到的物品不是号同学第一次拿到的物品,那么我们就可以将号同学第一次拿到的物品看作是号同学第一次拿到的物品。为什么可以这么看呢?此时已经确定,只需要看其他个人的方案数。假设第个同学第二次取到了号同学第一次所取的物品,那么除了号同学以外,可以说其他同学都与号同学无关,这样,如果我们强制将号同学排除,转化出的子问题就只需将i号同学第二次所取物品的下标改一下就行了。这时候我们发现,分离出来的子问题少了号同学第一次取的物品,多了号同学第一次取的物品,因此我们将号同学第一次取的物品下标改为号同学第一次取的物品的下标,答案不会改变。用图举个例子吧
这是分离1号同学之前的情况。
这是分离1号同学之前的情况。
这是分离后的情况。
这是分离后的情况。
 
观察可发现,分离后的方案就是一个独立的子问题,方案数正好是
返回原问题,共有种选择,因此当时,时就是特例,因此递推式一得证。
 
第二个递推式很容易证明,可以考虑用总方案数减去不满足的方案数。总方案很明显是。既然方案不满足,那么说明一定有人取了第一次拿的物品。我们假设有个人取了第一次拿的物品,个人的总组合数(组合马上就讲)为,根据乘法原理,每一个对应的不符合的方案数即为个人的组合数乘剩下的人符合条件的方案数,即可以从取到,因此,递推式二得证。
 
第三个式子的证明方法与第二个类似,只是细节上会用到容斥原理。
 
第四个不会证,路过的大佬可以指教一下。
 
 
咕咕咕……待填坑。

Loading Comments...