组合数学1(排列组合 + 鸽巢原理 + 容斥原理)

排列组合

加法/乘法法则

加法法则

相互独立的事件 A、B 分别有 k 和 l 种方法产生,则产生 A 或 B 的方法数为 k+l 种。

集合论定义

若|A|=k,|B|=l ,且A∩B=Φ ,则|A∪B| = k+l 。

S = S1 ∪ S2 ∪ · · · ∪ Sm, Si ∩ Sj = ∅ (i ≠ j)

|S| = |S1| + |S2| + · · · + |Sm|。

例1

a食堂有3种汉堡,b食堂有4种小吃,c食堂有2种包子,你的早餐只想吃一种,共有多少种选择方法?

解:

设S是所有食物的集合,Si是第i类食物的集合(i=1,2,3),显然,Si∩Sj=Φ (i≠j) ,根据加法法则有:

|S| = |S1| + |S2| + |S3| = 3 + 4 + 2 = 9。

例2

大于0小于10的奇偶数有多少个?

解:

设S是符合条件数的集合,S1、S2分别是符合条件的奇数、偶数集合,显然,S1∩S2=Φ ,根据加法法则有:

|S| = |S1| + |S2| = 5 + 4 = 9。

乘法法则

相互独立的事件 A、B 分别有 k 和 l 种方法产生,则选取A以后再选取B 的方法数为 k×l 种。

集合论定义

若|A|=k,|B|=l ,A×B={(a,b)|a∈A,b∈B},则|A×B| = k×l 。

S = P × Q

|S| = |P | × |Q|。

从A 地到B地有二条不同的道路,从B地到C地有四条不同的道路,而从C地到D地有三条不同的道路。求从A地经B、C两地到达D地的道路数。

解:

设S是所求的道路数集合,S1、S2、S3分别是从A到B、从B到C、从C到D的道路集合,根据乘法法则有

|S| = |S1 | × |S2| × |S3| = 2 × 4 × 3 = 24。

计数问题的分类

有序安排或有序选择

​ ——允许重复/不允许重复

无序安排或无序选择

​ ——允许重复/不允许重复

重集的概念

标准集的特性:确定、无序、相异等。

重集:B={k1 b1, k2 b2, …, kn * bn},其中:bi为n个互不相同的元素,称 ki为bi的重数, i = 1, 2, …, n,n=1,2,…, ∞,ki = 1, 2, …, ∞。

排列

线排列

从n个不同元素中,取r个(0≤r≤n)按一定顺序排列起来,其排列数P(n,r)。

集合论定义

设A={an} ,从A中选择r个(0≤r≤n)元素排列起来,A的r−有序子集,A的r−排列。

定理

若n, r∈Z且n≥r≥0, P(n,r)=n!/(n-r)!。

若n=r,称全排列P(n,n)= n!;

若n<r, P(n,r)=0;

若r=0, P(n,r)=1。

证明

构造集合A的r−排列时,可以从A的n各元素中任选一个作为排列的第一项,有n种选法;第一项选定后从剩下的n-1个元素中选排列的第二项有n-1种选法;…由此类推,第r项有n-r+1种选法。根据乘法原理有:

P(n,r) = n(n-1)……(n-r+1) = n!/(n-r)! 。

推论1

若n, r∈N且n≥r≥2,则P(n,r)=n×P(n-1,r-1) 。

证明

在集合A的n个元素中,任一个元素都可以排在它的r−排列首位,故首位有n种取法;首位取定后,其他位置的元素正好是从A的另n-1个元素中取r-1个的排列,因此有P(n-1,r-1)种取法。由乘法法则有:

P(n,r)=n×P(n-1,r-1)

推论2

若n, r∈N且n≥r≥2,则P(n,r)= r×P(n-1,r-1)+P(n-1,r) 。

证明

当r≥2时,把集合A的r−排列分为两大类:一类包含A中的某个固定元素,不妨设为a1,另一类不包含a1 。第一类排列相当于先从A-{a1}中取r-1个元素进行排列,有P(n-1,r-1)种取法,再将a1放入每一个上述排列中,对任一排列,a1都有r种放法。由乘法法则,第一类排列共有r×P(n-1,r-1)个。第二类排列实质上是A-{a1}的r−排列,共有P(n-1,r)个。再由加法法则有:

P(n,r)= r×P(n-1,r-1)+P(n-1,r)

例1

由数字1,2,3,4,5可以构成多少个所有数字互不相同的四位数?

解:

由于所有的四位数字互不相同,故每一个四位数就是集合{1,2,3,4,5}的一个4−排列,因而所求的四位数个数为

P(5,4)=5!/(5-4)!=120。

例2

将具有9个字母的单词FRAGMENTS进行排列,要求字母A总是紧跟在字母R的右边,问有多少种这样的排法?如果再要求字母M和N必须相邻呢?

解:

由于A总是R的右边,故这样的排列相当于是8个元素的集合{F,RA,G,M,E,N,T,S}的一个全排列,个数为

P(8,8) = 8! = 40320。

如果再要求M和N必须相邻,可先把M和N看成一个整体={M,N},进行7个元素的集合{F,RA,G,E,T,S,}的全排列,在每一个排列中再进行 {M,N}的全排列,由乘法法则,排列个数为

P(7,7) P(2,2) = 7! 2! = 10080。

例3

有多少个5位数,每位数字都不相同,不能取0,且数字7和9不能相邻?

解:

由于所有的5位数字互不相同,且不能取0,故每一个5位数就是集合{1,2,…,9}的一个5-排列,其排列数为P(9,5),其中7和9相邻的排列数为[c(7,3)4!2]4×2×P(7,3),满足题目要求的5位数个数为

P(9,5) - 4 2 P(7,3) = 15120 -1680 = 13440

圆排列

设A={an} ,从A中取r个(0≤r≤n)元素按某种顺序(如逆时针)排成一个圆圈,称为圆排列(循环排列)。

定理

设A={an},A的r圆排列个数为P(n,r)/r。

证明

由于把一个圆排列旋转所得到另一个圆排列视为相同的圆排列,因此线排列a1a2…ar,a2a3…ara1,… ara1a2…ar-1在圆排列中是一个,即一个圆排列可产生r个不同的线排列;同理, r个不同的线排列对应一个圆排列。而总共有P(n,r)个线排列,故圆排列的个数为

​ P(n,r)/r= n!/(r×(n-r)!)

例1

有8人围圆桌就餐,问有多少种就座方式?如果有两人不愿坐在一起,又有多少种就座方式?

解:

由上述定理知8人围圆桌就餐,有8!/8=7!=5040种就座方式。

又有两人不愿坐在一起,不妨设此二人为A、B,当A、B坐在一起时,相当于7人围圆桌就餐,有7!/7=6!种就座方式。 而A、B坐在一起时,又有两种情况,或者A在B的左面,或者A在B的右面,因此A、B坐在一起时,共有2×6!种就座方式,因此如果有两人不愿坐在一起,就座方式为

7!-2×6!= 5×6!=3600

例2

4男4女围圆桌交替就座有多少种就座方式?

解:

显然,这是一个圆排列问题。首先让4个男的围圆桌就座,有4!/4=3!种就座方式。 因为要求男女围圆桌交替就座,在男的坐定后,两两之间均需留有一个空位,女的就座相当于一个4元素集合的全排列,就座方式数为4!。由乘法法则知,就座方式数为

3!×4!=144

重排列

从n个不同元素中,可重复选取r个按一定顺序排列起来,称为重排列。

集合论定义

从重集B={k1 b1, k2 b2, … , kn * bn}中选取r个按一定顺序排列起来。

定理1

重集B={∞ b1, ∞ b2, … , ∞ * bn} 的r−排列的个数为nr。

证明:

构造B的r−排列如下:选择第一项时可从n个元素中任选一个,有n种选法,选择第二项时由于可以重复选取,仍有n种选法,…,同理,选择第r项时仍有n种选法,根据乘法法则,可得出r−排列的个数为nr。

例1

由数字1,2,3,4,5,6这六个数字能组成多少个五位数?又可组成多少大于34500的五位数?

解:

一个五位数的各位数字可重复出现,是一个典型的重排列问题,相当于重集B={∞ 1,∞ 2,…,∞*6}的5−排列,所求的五位数个数为6^5=7776。

大于34500的五位数可由下面三种情况组成:

万位选4,5,6中的一个,其余4位相当于重集B的4−排列,由乘法法则知,共有3×6^4个五位数;

万位是3,千位5,6中的一个,其余3位相当于重集B的3−排列,由乘法法则知,共有2×6^3个五位数;

万位是3,千位4中的一个,百位选5,6中的一个,其余2位相当于重集B的2−排列,由乘法法则知,共有2×6^2个五位数;

由加法法则知,大于34500的五位数个数为3×6^4 + 2×6^3 + 2×6^2=4392

定理2

重集B={n1 b1,n2 b2,…,nk bk}的全排列个数为n! / ( n1! n2! …… nk! ),其中,n = n1 + n2 +…… +nk。

证明:

将B中的ni个bi看作不同的ni个元素,赋予上标1,2,…, ni,即b(1,i),b(2,i)……,b(ni,i), i=1, 2,…… k,如此,重集B就变成具有n1+n2+…+nk=n个不同的元素集合A = {b(1,1),b(2,1)……,b(n1,1),b(1,2),b(2,2)……,b(n2,2),……b(1,k),b(2,k)……,b(nk,k,}

显然,集合A的全排列个数为n!。又由于ni个bi赋予上标的方法有ni!种,于是对重集B的任一个全排列,都可以产生集合A的n1!×n2!×…×nk!个排列(由乘法法则),故重集B的全排列个数为n! / ( n1! n2! …… * nk! )。

注:利用组合数的计数方法同样可以得出证明。

例2

有四面红旗,三面蓝旗,二面黄旗,五面绿旗可以组成多少种由14面旗子组成的一排彩旗?

解:

这是一个重排列问题,是求重集{4红旗,3蓝旗,2黄旗,5绿旗}的全排列个数,根据定理,一排彩旗的种数为

14! / ( 4! 3! 2! * 5! ) = 2522520。

例3

用字母A、B、C组成五个字母的符号,要求在每个符号里,A至多出现2次,B至多出现1次,C至多出现3次,求此类符号的个数。

解:

这也是一个重排列问题。根据分析,符合题意的符号个数相当于求重集M={2A,1B,3*C}的5−排列个数,可分为三种情况:需要分别求M-{A}、M-{B}和M-{C}的全排列个数。根据加法法则,此类符号个数为

5! / (1! 1! 3!) + 5! / (2! 0! 3!) + 5! / (2! 1! 2!) = 60

项链排列

对圆排列,通过转动、平移、翻转、可重合的,即可看作项链排列。

若n个不同元素的r−项链排列个数为P(n,r)/(2×r),具体参照Pólya定理。


纸短情长啊文章结束了但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!