组合排序题目汇总(排列组合、卡特兰数和递归思想)

心已赠人 2022-01-29 12:57 274阅读 0赞

### 组合排序题目汇总 ###

*  排列组合
 *   *  矩阵走法
     *  A必须在B左边站队
     *  互不相邻站队
     *  分糖果
     *  球放入桶
     *  吃糖
 *  卡特兰数
 *   *  括号匹配
     *  进出栈顺序/售票顺序
     *  二叉树不同的结构数
     *  高矮排列
 *  递归思想
 *   *  信封装信

# 排列组合 #

## 矩阵走法 ##

在6×9的方格中，以左上角为起点，右下角为终点，每次只能向下走或者向右走，请问一共有多少种不同的走法。

**解题思路：**

> 一共走13步，必然向下要走五步，向右要走8步。所以在13步中选择5步或者8步进行组合即可，公式如下：![图][20190521223748921.png]

## A必须在B左边站队 ##

ABCDEFG七人站队，要求A必须在B的左边，但不要求一定相邻，请问共有多少种排法？第二问如果要求A必须在B的左边，并且一定要相邻，请问一共有多少种排法？

**解题思路：**

> 1.  **第一问：**  
>     七个人一共有 **7!** 种排列方法，其中一半情况为A在B的左边，还有一半情况为A在B的右边，所以A必须在B的左边且不一定相邻的排法为： **7!/2 = 2520** 种。
> 2.  第二问  
>     题目要求A必须在B的左边并且一定要相邻，所以AB可以看成是一个人，即只需要求6个人的全排列即可：**6! = 720** 种。

## 互不相邻站队 ##

六个人排成一排，要求甲与乙不相邻，并且甲与丙不相邻的排法数是多少？

**解题思路：**

> 1.  **方法一：**  
>     六个人一共有 **6! = 720** 种排列方法，甲与乙相邻共有 **5! + 5! = 240** 种排列方法(甲乙看成一个人，乙甲看成一个人)，同理，甲与丙相邻也有**5! + 5! = 240** 种排列方法。  
>     甲与乙相邻和甲与丙相邻中还有**交集**，即 **乙甲丙** 和 **丙甲乙**：在甲乙和丙甲排列方法中，丙甲乙出现了两次；在乙甲和甲丙排列方法中，乙甲丙出现了两次，所以要加上重复减去的这一部分，即 **4! + 4! = 48**。  
>     所以，甲与乙不相邻，并且甲与丙不相邻的排法数为：**720 - 240 - 240 + 48 = 288** 种。
> 2.  **方法二：**  
>     （1）**甲在左侧开头位置**，他的邻居不能是乙或是丙，所以还剩3种选择，剩下四个人再任意排列 4! 种即可。所以甲在左侧，有 **3 × 4! = 72** 种。  
>     （2）同理，**甲在最右侧末尾位置**，有 **3 × 4! = 72** 种。  
>     （3）**当甲不在开头或末尾时**，有中间4个位置选择，但邻居不是能乙或丙，所以只能在剩下3个人之中选择，所以邻居有 **C32 = 6** 种方法。剩下的3个人全排列即可。所以甲在任意位置上合理的总数为 **6 × 3! = 36** 种。因为一共有**4个中间位置**，所以总数为 **36 × 4 = 144** 种。  
>     所以最后将三种情况相加： **72 + 72 + 144 = 288** 种。

## 分糖果 ##

10颗相同的糖果，分给3个人，每人至少一颗，问有多少种分法。

**解题思路：**

> 10个糖果中有9个空隙，所以最后目标可以转换为9个空隙中选择两个地方插入隔板，隔出的部分就看作每个人分得的数量。所以一共有 **C92 = 36** 种。

## 球放入桶 ##

10个不同的球放入3个不同的桶里有多少种方法。

**解题思路：**

> 每个球都有3种选择放入某个桶，一共有10个球，所以有 **310 = 59049** 种方法。

## 吃糖 ##

有10颗糖，如果每天至少吃一颗，吃完为止，问有多少种不同的吃法？

**解题思路：**

> 1.  如果想一天吃完所有的糖，方法为 1 种。
> 2.  如果想两天吃完所有的糖，方法为 C91 种。（相当于9个空隙放1个隔板）
> 3.  如果想三天吃完所有的糖，方法为 C92 种。
> 4.  如果想四天吃完所有的糖，方法为 C93 种。
> 
> 所以一共有：  
> **C(9,0) + C(9,1) + C(9,2) + … + C(9,9) = 29 = 512** 种

# 卡特兰数 #

## 括号匹配 ##

假设有n对左右括号，请求出合法的排列有多少个？合法是指每一个括号都可以找到与之配对的括号，比如 n = 1 时，()是合法的，但是)(为不合法。

**解题思路：**

> **左括号数量为n，右括号数量为n，总排列数为C(2n,n)。** 其中有不合理的排列，在左括号前多了右括号。 所以现在**把左括号记为 1，把右括号记为 -1**，如下图：  
> ![图][20190522135127186.png]  
> 其中，前三个括号中，出现了右括号比左括号多的情况，这是不合法的，把这一部分的1变成-1，-1变成1，（**当-1的数量比1的数量第一次多时将该位置以前的1，-1互换，后面的不变换**），如下图：  
> ![图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb3l1ZWFjZQ_size_16_color_FFFFFF_t_70]  
> 所以现在括号的排列变为：**n+1个1 和 n-1个-1的组合**。（因为第一次出现-1 比 1多时，-1肯定比1 多一个，所以翻转后，1 比 -1 多一个）。  
> **每一个不合格的括号排列通过这种变换方式，都可以得到 n+1个1 和 n-1个-1 所组成的队列。** 同时， n+1个1 和 n-1个-1 所组成的队列也可以倒推回一个不合格的括号排列。  
> 所以，**所有不合法的排列数 = n+1个1 和 n-1个-1 组成的排列数 = C(2n, n+1) 或者 C(2n, n-1)**  
> 即，**最终合法的排列数**为：  
> ![公式][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb3l1ZWFjZQ_size_16_color_FFFFFF_t_70 1]

## 进出栈顺序/售票顺序 ##

n个数进出栈的顺序有多少种？假设栈的容量无限大。还有一个问题与之类似，2n个人排队买票，n个人拿5块钱，n个人拿10块钱，票价是5块钱1张，每个人买一张票，售票员手里没有零钱，问有多少种排队方法让售票员可以顺利卖票。

**解题思路：**

> 1.  进出栈顺序  
>     这题是括号匹配的变种题，实际上核心思想是一样的，**进栈的元素可以作为左括号，出栈的元素可以作为右括号**，出栈与进栈必须匹配才合格。  
>     所以n个数进栈，n个数出栈，共有 **C(2n, n)/(n+1)** 种顺序。
> 2.  售票顺序  
>     依旧可以将**5块钱看作左括号，10块钱看作右括号**，所以同理，共有 **C(2n, n)/(n+1)** 种顺序。

## 二叉树不同的结构数 ##

求n个无差别的节点构成的二叉树有多少种不同的结构？

解题思路：

> 有 1 个节点时，f(1) = 1;  
> 有 2 个节点时，固定根节点，另外一个节点 = 1 + 0 = 0 + 1，有两种，即 f(2) = f(1) + f(1) = 2;  
> 有 3 个节点时，固定根节点，剩余两个节点 = 2 + 0 = 1 + 1 = 0 + 2，有三种，即 f(3) = f(2) + f(1)×f(1) + f(2);  
> 有 n 个节点时，固定根节点，剩余节点 = n-1 + 0 = n-2 + 1 = n-3 + 2 = … = 1 + n-2 = 0 + n-1，即 f(n) = f(n-1) + f(n-2)f(1) + f(n-3)f(2) + … + f(1)f(n-2) + f(n-1)。  
> **设f(0) = 1，f(1) = 1，f(n) = f(n-1)f(0) + f(n-2)f(1) + f(n-3)f(2) + … + f(1)f(n-2) + f(0)f(n-1)** 为卡特兰(Catalan)数，最后的解为 **C(2n, n)/(n+1) = (2n)! / n!(n+1)!**。  
> 其前几项为 : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796…  
> 卡特兰数的推导需要构造母函数。

## 高矮排列 ##

12个高矮不同的人，排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，问排列方式有多少种？

**解题思路：这题的核心依旧是卡特兰数问题！！！！**

> 将站在第一排的人设为0，站在第二排的人设为1 ，一个0后面可以匹配上一个1，但是如果有单独的1没能匹配，就说明高矮不合格。  
> 所以，这又可以看成是括号匹配问题，站在第一排的看为左括号，第二排的看作右括号，共有 **C(n, n/2)/(n/2+1)** 种顺序。

# 递归思想 #

## 信封装信 ##

有n个信封，包含n封信，现在把信拿出来，再装回去，要求每封信不能装回它原来的信封，问有多少种装法？

**解题思路—递归思想：**

> 第 n 封信按照题目要求的装法设为f(n)（只考虑n>2）。  
> 假设第 n 封信装入第 i 个信封，有两种情况需要讨论：
> 
> 1.  情况一：  
>     第 i 封信也放入了第 n 个信封中，则后续装法为 f(n-2)。
> 2.  情况二：  
>     第 i 封信没放入第 n 个信封中，则后续装法为 f(n-1)。
> 
> 而第 n 封信装入第 i 个信封，信封 i 的选择有 n-1 种，所以总数为：  
> **f(n) = (n-1) × ( f(n-1) + f(n-2) )**

[20190521223748921.png]: /images/20220129/26c8d7cd40db4213a5ed2e6ee26735a2.png
[20190522135127186.png]: /images/20220129/3fa81818ef964105b53bde9c49c20af6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb3l1ZWFjZQ_size_16_color_FFFFFF_t_70]: /images/20220129/276b483914d845e4b8aa3ab1f47b5a4d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb3l1ZWFjZQ_size_16_color_FFFFFF_t_70 1]: /images/20220129/46debdd52a404c8d97442acd0ec33973.png