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

2023-03-27 16:21:37 浏览数 (1)

文章目录

  • 一、集合排列 和 多重集排列问题 1
  • 二、 集合排列 和 多重集排列问题 2
  • 三、 找一一对应计算集合排列问题 ( 反向计算 )
  • 四、 圆排列问题 1
  • 五、 集合交替排列问题
  • 六、 圆排列问题 2
  • 七、 推广的牛顿二项式公式
  • 八、 二项式展开问题

一、集合排列 和 多重集排列问题 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

次 (

n > 1

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

1

位 有

6

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

1

次 , 因此第

2

位 有

5

种方案 , 第

3

位 有

4

种方案 , 第

4

位 有

3

种方案 ; 相乘后 结果

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)

进行计算 ;

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{6times5times4times3times2times1}{2times 1} = 6 times 5 times 4 times 3 =360

问题 2 解答 :

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

k

种元素 ) 中 选取

r

个元素 , 可以使用公式

k^r

进行计算 ;

② 结果是

6^4=1296

;

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

题目 :

  • 1.条件 : 从
{1,2,3,4,5,6,7,8,9}

中选取不同的数字 ;

  • 2.问题 :
4,5,6

不相邻的

7

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

4,5,6

任意一个排列 如

654 , 546

等 ) ;

解答 :

分析 :

  • 1.正面计算 :
4,5,6

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

  • 2.寻找一一对应 : 这里 先计算
4,5,6

相邻的 方案数

A

,

P(9,7) -A

与

456

不相邻的

7

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

计算

4,5,6

相邻的

7

位数 方案数 :

①

7

位数 中 必定 含有

4,5,6

三个数字 , 还需要选

4

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

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

② 一共有

9

位数 , 其中

3

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

6

位可选数字 , 从剩下的

6

位数中选

4

位数字 ;

P(6,4) = cfrac{6!}{(6-4)!}=cfrac{6times5times4times3times2times1}{2times1} = 360

③

4

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

4,5,6

相邻排列所在位置 ;

4

个数字 , 其 两端 和 中间

3

个空隙 , 有

5

个可选位置 ;

④

4,5,6

相邻的

7

位数 个数计算 :

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

⑤

4,5,6

不相邻的

7

位数 等价于 任意

7

位数个数 减去

4,5,6

相邻的

7

位数个数 ;

P(9,7)-10800 = cfrac{9times8times7times6times5times4times3times2times1}{2times1} - 10800 = 181440 - 10800 = 17064

四、 圆排列问题 1

题目 :

  • 1.条件 :
5

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

  • 2.问题
1

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

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

n

元集

S

的环形

r-

排列数 :

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

解答 : ① 先让

5

男坐下 , 使用公式计算

5

元集

S

的环境

5-

排列;

cfrac{P(5,5)}{5} = cfrac{5!}{5times1} =4!= 4times3times2times1=24

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

2^5=32

种选择 ;

③ 根据乘法原则 : 共有

24times32=768

种方案 ;

五、 集合交替排列问题

题目 :

  • 1.条件 :
5

个文科生 ,

5

个理科生坐一排 ;

  • 2.问题
1

: 有多少不同排法 ;

  • 3.问题
2

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

解答 :

问题

1

:

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

P(10, 10)

; 计算过程如下 :

P(10,10) = cfrac{10!}{(10 - 10)!}=cfrac{10times9times8times7times6times5times4times3times2times1}{1}=3628800

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

问题

2

:

① 计算

5

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

P(5,5) = cfrac{5!}{(5-5)!}=5times4times3times2times1 = 120

② 计算

5

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

P(5,5) = cfrac{5!}{(5-5)!}=5times4times3times2times1 = 120

③

5

个文科生 和

5

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

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

④ 最终结果是有

28800

种方案数 ;

六、 圆排列问题 2

题目 :

  • 1.条件 :
4

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

  • 2.问题
1

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

  • 2.问题
1

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

  • 2.问题
1

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

解答 :

问题

1

:

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

n

元集的 环形

r-

排列个数 :

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

;

②计算过程如下 :

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

问题

2

:

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

P(4,4)

, 再排列 4女 全排列

P(4,4)

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

② 最终结果是 :

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

问题

3

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

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

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

2^4=16

种选择 ;

② 最终结果是

96

种 ;

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

二项式定理 :

(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
  • ③ 换元法 : 使用
ax

将推论中的

x

替换 :

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
集合 排序 数学 统计

0 人点赞