【组合数学】集合的排列组合问题示例 ( 排列 | 组合 | 圆排列 | 二项式定理 )

韩曙亮

发布于 2023-03-27 16:21:37

1.5K0

发布于 2023-03-27 16:21:37

文章被收录于专栏：韩曙亮的移动开发专栏

文章目录

一、集合排列和多重集排列问题 1

题目 :

1.条件 : 由字母

a, b,c,d,e,f

组成 4 个字母的单词 ;

2.问题 1 : 每个字母在单词中最多出现一次 , 这样的单词个数有多少 ;
3.问题 2 : 如果字母允许重复 , 可以组成多少单词 ;

问题 1 解答 :

① 每个字母最多出现一次 , 那么该问题就是集合的排列问题 , 即

P(6,4)

; ② 计算步骤 :

P(6,4) = \frac{6!}{(6-4)!} = 6 \times 5 \times 4 \times 3 = 360

解析 : 问题限定 : 1>集合排列 : 每个字母最多出现 1 次 , 这是将问题限定在了集合的排列问题上 ; 2>多重集排列 : 如果每个字母最多出现

次 (

n > 1

) , 那么就是多重集的排列 ; 利用乘法计数原则 , 从左到右依次计算 , 第

位有

种方案 , 每个单词只能出现

次 , 因此第

位有

种方案 , 第

位有

种方案 , 第

位有

种方案 ; 相乘后结果

6 \times 5 \times 4 \times 3 = 360

;

问题 2 解答 :

① 如果允许重复 , 这就变成了多重集的排列问题 ; ② 单词每一位都有 6 种方案 , 结果为

6^4 = 1296

种方案数 ;

二、集合排列和多重集排列问题 2

题目 :

1.条件 : 由字母

a, b,c,d,e,f

组成 4 个字母的单词 ;

2.问题 1 : 每个字母在单词中最多出现一次 , 这样的单词个数有多少 ;
3.问题 2 : 如果字母允许重复 , 可以组成多少单词 ;

问题 1 解答 :

① 每个单词出现一次 , 该问题本质上是 6元集 ( 集合 ) 的排列问题 , 使用集合排序公式

P(n,r)

进行计算 ;

元集的

排列 , 计算公式如下 :

P(n,r)= n(n-1)(n-2)\cdots(n-r+1) =\frac{n!}{(n-r)!}

② 计算过程 :

P(6,4) = \cfrac{6!}{(6-4)!} = \cfrac{6\times5\times4\times3\times2\times1}{2\times 1} = 6 \times 5 \times 4 \times 3 =360

问题 2 解答 :

① 如果字母允许重复 , 该文本本质上就是多重集的排列问题 ; 如果不限制其出现次数 , 多重集 ( 有

种元素 ) 中选取

个元素 , 可以使用公式

k^r

进行计算 ;

② 结果是

6^4=1296

;

三、找一一对应计算集合排列问题 ( 反向计算 )

题目 :

1.条件 : 从

\{1,2,3,4,5,6,7,8,9\}

中选取不同的数字 ;

2.问题 :

4,5,6

不相邻的

位数有多少 ; ( 这里不能出现

4,5,6

任意一个排列如

654 , 546

等 ) ;

解答 :

分析 :

1.正面计算 :

4,5,6

不相邻的情况有很多 , 正面计算很困难 , 要考虑个不相邻 , 2个与 1个不相邻, 每个不相邻的数字之间的排列分布等情况 , 计算量很大 ;

2.寻找一一对应 : 这里先计算

4,5,6

相邻的方案数

P(9,7) -A

与

456

不相邻的

位数字 方案数是一一对应的 ;

计算

4,5,6

相邻的

位数方案数 :

①

位数中必定含有

4,5,6

三个数字 , 还需要选

位数 ; 此处先统计下这三个数的全排列数 :

P(3,3) = \cfrac{3!}{(3-3)!} = \cfrac{3 \times 2 \times 1}{1} = 6

② 一共有

位数 , 其中

位是必须要选择 , 那么还剩下

位可选数字 , 从剩下的

位数中选

位数字 ;

P(6,4) = \cfrac{6!}{(6-4)!}=\cfrac{6\times5\times4\times3\times2\times1}{2\times1} = 360

③

位数字选好之后, 开始安排

4,5,6

相邻排列所在位置 ;

个数字 , 其两端和中间

个空隙 , 有

个可选位置 ;

④

4,5,6

相邻的

位数个数计算 :

P(3,3) \times P(6,4) \times 5 = 6 \times 360 \times 5 =10800

⑤

4,5,6

不相邻的

位数等价于任意

位数个数减去

4,5,6

相邻的

位数个数 ;

P(9,7)-10800 = \cfrac{9\times8\times7\times6\times5\times4\times3\times2\times1}{2\times1} - 10800 = 181440 - 10800 = 17064

四、圆排列问题 1

题目 :

1.条件 :

对夫妻参加宴会 , 围成一桌坐下 ;

2.问题

: 每对夫妻相邻 , 有多少种方案 ;

解析 : 灵活使用圆排列公式 :

元集

的环形

排列数 :

\cfrac{P(n,r)}{r} = \cfrac{n!}{r(n-r)!}

解答 : ① 先让

男坐下 , 使用公式计算

元集

的环境

排列;

\cfrac{P(5,5)}{5} = \cfrac{5!}{5\times1} =4!= 4\times3\times2\times1=24

② 每个妻子都有两种选择 , 坐在丈夫左边或者右边 , 有

2^5=32

种选择 ;

③ 根据乘法原则 : 共有

24\times32=768

种方案 ;

五、集合交替排列问题

题目 :

1.条件 :

个文科生 ,

个理科生坐一排 ;

2.问题

: 有多少不同排法 ;

3.问题

: 交替坐成一排有多少种排法 ;

解答 :

问题

① 没有要求坐一排的话就是 10 个人的全排列

P(10, 10)

; 计算过程如下 :

P(10,10) = \cfrac{10!}{(10 - 10)!}=\cfrac{10\times9\times8\times7\times6\times5\times4\times3\times2\times1}{1}=3628800

② 结果是 3628800 种不同的排法 ;

问题

① 计算

个文科生作成一拍的全排列 :

P(5,5) = \cfrac{5!}{(5-5)!}=5\times4\times3\times2\times1 = 120

② 计算

个理科生坐成一排的全排列 :

P(5,5) = \cfrac{5!}{(5-5)!}=5\times4\times3\times2\times1 = 120

③

个文科生和

个理科生交替排成一排 , 那么有两种插空方式 : 计算最终结果 :

P(5,5) \times P(5,5) \times 2 = 120 \times 120 \times 2 =14400 \times 2=28800

④ 最终结果是有

28800

种方案数 ;

六、圆排列问题 2

题目 :

1.条件 :

对夫妻参加宴会 , 围成一桌坐下 ;

2.问题

: 没有任何限制条件就座 , 有多少种方案 ;

2.问题

: 4男 4女排成一排 , 有多少种方案 ;

2.问题

: 夫妻相邻 , 有多少种方案 ;

解答 :

问题

① 没有任何限制条件的圆排列 , 使用公式

元集的环形

排列个数 :

\cfrac{P(n,r)}{r}

;

②计算过程如下 :

\cfrac{P(8,8)}{8}=\cfrac{8!}{8\times(8-8)!}=7!=5040

问题

① 男女交替排法 : 先排列 4男全排列

P(4,4)

, 再排列 4女全排列

P(4,4)

, 在进行交替插空 , 有两种方案 ;

② 最终结果是 :

P(4,4)\times P(4,4)\times 2 = 1152

问题

: ① 夫妻相邻就座 : 首先让丈夫圆排列

\cfrac{P(4,4)}{4} = 3! =6

, 然后让妻子坐在丈夫左边或右边 , 每人两种选择

2^4=16

种选择 ;

② 最终结果是

种 ;

七、推广的牛顿二项式公式

二项式定理 :

(x+y)^n=\sum_{k=0}^{n}\dbinom{n}{k}x^ky^{n-k}

牛顿二项式公式 :

(1+x)^n=\sum_{k=0}^{n}\dbinom{n}{k}x^k

牛顿二项式公式变体 :

(1+ax)^n=\sum_{k=0}^{n}\dbinom{n}{k}a^kx^k

推广的牛顿二项式公式 :

(1+x)^{-n}=\sum_{k=0}^{n}\dbinom{-n}{k}x^k

八、二项式展开问题

题目 :

条件 :

(1+2x)^n

展开 ,

( 1 \leq k \leq n)

问题 : 其中

x^k

的系数是多少 ;

问题分析 :

① 二项式定理 :

(x + y)^n = \sum^{n}_{k=0} \dbinom{n}{k} x^k y^{n-k}

② 推论 :

(1 + x)^n = \sum^{n}_{k=0} \dbinom{n}{k} x^k

③ 换元法 : 使用

将推论中的

替换 :

\begin{array}{lcl} (1 + ax)^n & = & \sum^{n}_{k=0} \dbinom{n}{k} (ax)^k \\ & = & \sum^{n}_{k=0} \dbinom{n}{k} a^k x^k \end{array}

解答 :

① 根据牛顿二项式的推广公式 :

(1+ax)^n = \sum_{k=0}^{n}\dbinom{n}{k}a^kx^k

②

(1+2x)^n

的

x^k

项为 :

\dbinom{n}{k} 2^kx^k

x^k

前面的系数是

\dbinom{n}{k} 2^k

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019-07-17，如有侵权请联系 cloudcommunity@tencent.com 删除

集合

排序

数学

统计

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度