【离散数学中的数据结构与算法】六排列与组合二

红太狼 2022-04-23 14:46 196阅读 0赞

> 接着上一篇学习：[【离散数学中的数据结构与算法】五 排列与组合一][Link 1]

上一篇文章主要学习了可重复选取的可重排列和不可重复选取的排列。他们都是在**n个不同的对象中选取**。

今天我们俩学习的是，当这个n个对象中有相同的元素的时候，排列的相关定理。

> ### 文章目录 ###
> 
>  *   *  1 问题的引入
>      *   *  1.1 定理

## 1 问题的引入 ##

1.  由a, b, b, e, e, h, i, s, s, t, t, t可以组成多少个长度为12的字符串？

例如： tseabibttseh

1.  先考虑一个同类型的简单问题：由a, a, b, c可以组成多少个长度为4的字符串？

对a加下标得到 a1, a2，于是一共可以得到4!=24个长度为4的字符串：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9seXktMDIxNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70_pic_center]

去掉重复的字符串：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9seXktMDIxNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70_pic_center 1]  
所以一共12种（4！/ 2 = 12）。

1.  再看另一个同类型的问题：由a, a, a, b可以组成多少个长度为4的字符串？对a加下标得到 a1, a2, a3，于是一共可以得到4!=24个长度为4的字符串。如下图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9seXktMDIxNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70_pic_center 2]

所以一共有4种字符串。（4！ / 3! = 4）

1.  再看一个同类型的问题：由a, a, b, b可以组成多少个长度为4的字符串？

对a, b加下标得到 a1, a2, b1 , b2，于是一共可以得到4!=24个长度为4的字符串。如下图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9seXktMDIxNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70_pic_center 3]

所以一共有：6种字符串（4！ / 2! \* 2! = 6）

### 1.1 定理 ###

由 k1 个1， k2 个2 ， …， kt个t组成的长度为 n 的排列总数为：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9seXktMDIxNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70_pic_center 4]  
其中：n = k1 \+ k2 \+ k3 \+ … + kt

回到问题1：  
由a, b, b, e, e, h, i, s, s, t, t, t可以组成多少个长度为12的字符串？

12!/(2! 2! 2! 3!) = 9979200

[Link 1]: https://lyy-0217.blog.csdn.net/article/details/88620784
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9seXktMDIxNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70_pic_center]: /images/20220307/cd10cc52d1bb4124940e6a579fd79571.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9seXktMDIxNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20220307/ac2d57484233491795c4570641a09816.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9seXktMDIxNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20220307/a2da0a7fb9b44ff081abfa102669cb6e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9seXktMDIxNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20220307/5ddb3daeef1146e9816215e7c4b1da56.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9seXktMDIxNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20220307/85f341474a9740bdbcd3cfac8bca6404.png