排列组合

前言

本文参考B站Up一数的排列组合系列视频。

1. 案例

---

案例1：从1,2,3,4,5,6,7,8,9中任选两个（不能重复），其中一个作为底数，另一个作为真数，可以得到不同对数值的个数为多少？

• 对数：
  
• 分析：
  • 底数排除1，有8种选择
  • 真数不能选择自身（9-1=8），并且真数为1的话，其对数值都为0，故而先排除1（8-1=7），故而真数有7种选择
  • 7*8=56 + 1 （真数为1的情况）= 57 种选择
  • 上述57种选择中又有4个相同的值：log24 = log39，log23 = log49，log32 = log94，log42 = log93
    
• 因此，总共有57 - 4 = 53 种排列方式。

---

案例2：从6张不同卡牌中选出4张作为底牌，有多少种排列方式？

• 分析：
  • 第一个牌位可以从6张中任选其一；
  • 第二个牌位：从余下的5张中任选其一；
  • 第三个牌位：从余下的4张中任选其一；
  • 第四个牌位：从余下的3张中任选其一；
  • 总共有：6×5×4×3 = 360 种排列方式。

---

案例3：从m张牌中选n张作为底牌，有多少种排列方式：

• 分析：
  • 参考案例2，排列方式数量 = m×(m-1)×(m-2)×(m-3)×(m-4)……×(m-n+1)

2. 概念

---

什么是排列？

• 设有 𝑛 个不同的元素，从中取出 𝑟 个元素，并按照一定的顺序排列，则称这样的一个序列为一个排列。
  其数量=𝑛×(𝑛-1)×(𝑛-2)×(𝑛-3)×(𝑛-4)×……×(𝑛- 𝑟 +1)，表达式过于冗长，可以记为以下形式：
  
• 排列数的计算公式：
  
• 排列数计算公式的推导过程：
  
• 一些特殊的阶乘的值：0!=1、1!=1，由此可以推导：
  

---

案例

1. 从集合{0,1,2,3,5,7,11} 中任取 3 个不同元素，分别作为直线方程𝐴𝑥+𝐵𝑦+𝐶=0中的𝐴,𝐵,𝐶求得的经过原点的直线有多少条？

   • P(6,2) = 6 × 5 = 30

2. 从7个人中挑选出3个人排成一排，有多少种排列？

   • P(7,3) = 7 × 6 × 5 = 210

3. 从7个人中挑选出3个人组成一个小组，有多少种组合？

   • P(7, 3) ÷ P(3, 3) = 210 ÷ 6 = 35
   • 分析：3人组成一个小组，选好了三个人之后，这三个人的顺序是无意义的，所以要除以P(3,3)。

---

什么是组合？

• 从𝑛个元素中选取𝑟个元素的方式，不考虑顺序。
  
• 从排列的公式推导出组合的计算公式：
  

---

案例：

1. 计算由 4 个数字 1 和 4 个数字 2 组成的不同 8 位数 的总数。
   • 从 8 个位置中选 4 个位置放数字 1（剩下的 4 个位置自动填充数字 2）。
   • 由于相同的 1 和相同的 2 之间的顺序不会影响排列，因此用组合数计算。
   • C(8,4) = 70
2. 安排6人去A、B、C 三个场馆做志愿，A要1名，B要2名，C要3名，有多少种安排方式？
   • C(6,1)×C(5,2)×C(3,3) = 60
3. 从7个人中选4人负责元且三天假期的值班工作，其中第一天安排2人，第二天和第三天均安排1人，且人员不重复，则不同安排方式的种数有多少？
   • 思路1：C(7,2)×C(5,1)×C(4,1) = 420
   • 思路2：C(7,4)×C(4,2)×P(2,2) = 420
4. 从4个男生、5个女生中选出3个排成一排，且男女生都要有，有几种选择方式？
   • C(4,2)×C(5,1)×P(3,3) + ×C(5,2)×C(4,1)×P(3,3) = 420

3. 经典问题

问题	解决方案
相邻问题⭐	捆绑法：将相邻元素看成一个整体
不相邻问题⭐	插空法：先排好其他元素，后插空排入不相邻的元素
相邻 + 不相邻⭐⭐	结合一下捆绑法和插空法
定序问题⭐⭐	整体法：先将顺序相对不变的选位置填入（组合），余下的再从余下位置选择排列
名额分配⭐⭐⭐	相同元素分给不同组 切面包法：先按照约束条件提前分配，让每个角色变成至少需要1个元素，然后从剩余元素中切分
分组问题⭐⭐⭐	不同元素分给（多个）相同组 总结：分组不考虑排序，当有N组分配的元素一样时，组合的结果需要除以P(N,N)
分组+分配⭐⭐⭐	先分组，后分配
分组+分配+特殊要求⭐⭐⭐⭐

相邻问题 ⭐

• 6个学生站一排，其中A和B必须相邻站一起，有多少种站法？
  • 捆绑法：
    1. 先将A和B视作一个整体，总共有P(5,5)种排列
    2. A和B两者排列，有P(2,2)中排列
    3. 总共有：P(5,5)×P(2,2)=240
• 3个小组要站一排拍合影，A组3人、B组4人、C组2人， 要求每个小组的人必须站在一起，有多少种站法？
  • P(3,3)×P(3,3)×P(4,4)×P(2,2)=1728
• A、B、C、D、E 5人站一排，A不站两端，B和C相邻，E不站中间，有多少种站法？
  • 捆绑法：
    1. 先把B和C捆绑，再忽视其他条件，有站法：P(4,4)×P(2,2)
    2. A站两端，有站法：2×P(3,3)×P(2,2)，E站中间，有站法：P(1,1)×P(3,3)×P(2,2)
    3. 结果：P(4,4)×P(2,2) - P(2,2)×P(3,3)×P(2,2) - P(1,1)×P(3,3)×P(2,2) = 12

不相邻问题 ⭐

• 6人站一排，其中A和B不能相邻，有多少种站法？

  • 参考相邻问题：P(6,6) - P(5,5)×P(2,2) = 480
  • 插空法：
    • 4人先选四个位置排好：P(4,4)
    • 余下两人再插空排入（第一个插的人可选5个空，最后一人可选4个空）：P(5,1)×P(4,1)，也可记为P(5,2)。
    • 总计：P(4,4)×P(5,1)×P(4,1) = 480

• 6个空位，3人去坐，且3人之间不能相邻，有多少种做法？

  • 插空法：
    1. 先让3个空位相邻排好（P(3,3) ，3个空位无须排序，放一起即可，即1种排法）
    2. 余下3人选择好位置去插空，C(4,3)
    3. 这3个人之间是有顺序的，所以总做法：C(4,3)×P(3,3)=P(4,3)=24

• 一条路10个灯，现在需要熄灭其中3盏灯，这3盏熄灭的灯不能相邻，有多少种熄灭的方法？

  • 插空法：
    • 余下7盏亮着的灯先排在一起
    • 余下3盏在7+1（总共的空隙）-2（左右两端不能选）= 6个空隙中去选择
    • 总计：C(6,3)=20（因为这三盏灯不需要再排序，无须×P(3,3)）

相邻 + 不相邻 ⭐⭐

• 用数组1,2,3,4,5,6组成没有重复数字的6位数，其中1,2相邻且3,4不相邻

  1. 先绑定：先把1,2绑定到一起，并排除3,4：P(3,3)×P(2,2)
  2. 再插空：3,4去4个空隙中插空：C(4,2)×P(2,2)
  3. 总计：P(3,3)×P(2,2)×P(4,2)=144

• 5个人要坐一排，其中A和B不能相邻，且A和B不能同时坐在两边，有多少种坐法？

  • 先插空，后排除坐两边的情况：P(3,3)×A(4,2) - 2×P(3,3) = 60

定序问题 ⭐⭐

• 4人排成一排，后塞入A和B，之前的4人相对顺序不变，有多少种站法？
  • 整体法：
    1. 一共6人，即6个座位；
    2. 先前的4个先选位置，且这4人相对顺序不变，故：C(6,4)
    3. 后面两人再在余下的位置中选择：P(2,2)
    4. 总计：C(6,4)×P(2,2) = 30
• 10人合影，前排4人后排6人，现在需要从后排调2人去前排，其他人相对顺序不变，有多少种调整方法？
  • 整体法：
    1. 后排选两人：C(6,2)
    2. 前排4人先从6个位置中选好位置：C(6,4)
    3. 新加入的人再选位置P(2,2)
    4. 总计：C(6,2)×C(6,4)×P(2,2) = 450

名额分配 ⭐⭐⭐

• 有8个名额、4个班，每个班至少有一个名额，总共有几种分配方法？

  • 切面包法：C(7,3)
    

• 有10个名额，机构A至少3个，机构B至少2个，机构C至少1个，有几种分配方法？

  • 切面包法：
    1. 先把每个机构所必须得名额变为1，即预先分配A、B两家机构2个、1个名额
    2. 从余下的7个名额中继续划分，有C(6,2)=15种方案
       

• x1+x2+x3+x4=8，这四个未知数都是正整数，求有多少组数据满足表达式？
  -切面包法：
  1. 将8看做8份，需要向其中切3刀划分为4份
  2. 总计：C(7,3)

• x1+x2+x3+x4=8，这四个未知数都是非负整数，求有多少组数据满足表达式？

  • 四个未知数都+1，让取值区间变为正整数: x1+1+x2+1+x3+1+x4+1=8+4
  • 总计：C(11, 3)

分组问题 ⭐⭐⭐

• 现在有A、B、C、D四人，要分成两个小组
  • 一组1人，一组3人有多少种分法？
    • C(4,1)
  • 一组2人，一组2人有多少种分法？
    • C(4,2)
    • 注意：分成两个小组，小组之间不需要排序，如下：
      
    • 总计：C(4,2)÷P(2,2)
• 6本书进行分组：
  • 一组4本，一组2本
    • 总计：C(6,4)
  • 一组3本，一组3本
    • 总计：C(6,3)÷P(2,2)
  • 一组3本，一组2本，一组1本
    • 总计：C(6,3)×P(3,2)
  • 一组2本，一组2本，一组2本
    • 总计：C(6,2)×C(4,2)÷P(3,3)
  • 一组2本，一组2本，一组1本，一组1本
    • 总计：C(6,2)×C(4,2)÷P(2,2)×C(2,1)×C(1,1)÷P(2,2)
  • 一组3本，一组1本，一组1本，一组1本
    • 总计：C(6,3)×C(3,1)×C(2,1)×C(1,1)÷P(3,3)

分组+分配 ⭐⭐⭐

• 4人到3个小区做志愿，每人只去1个小区，每个小区至少有1人，有多少种安排？

  • 先分组后分配：
    1. 转换为4人分3组：2,1,1
    2. 总计：C(4,2)×C(2,1)×C(1,1)÷P(2,2)×P(3,3)
       

• 6本书分四组：2、2、1、1，分好组之后要把这四组书分别分给4人，有多少种分法？

  • 总计：C(6,2)×C(4,2)÷P(2,2)×C(2,1)×C(1,1)÷P(2,2)×P(4,4)

• 5人分3组，每人只分配到1组，每组最少分配1人，有多少种分配方案？

  • 先分组后分配：
    1. 分组：3,1,1、2,2,1
    2. 总计：(C(5,3)×C(2,1)×C(1,1)÷P(2,2) + C(5,2)×C(3,2)×C(1,1)÷P(2,2)) ×P(3,3)

分组+分配+特殊要求 ⭐⭐⭐⭐

• 5人分3组，其中A和B必须在一起，每人只能去1组，每组至少1人，有多少种分配方法？

  • 绑定+分组+分配：
    1. 把相邻视作一个元素，分法：2,1,1 => C(4,2)×C(2,1)×C(1,1)÷P(2,2)×P(3,3)
    2. 因为相邻元素在一组中无须排序，所以无须×P(2,2)
    3. 总计：C(4,2)×C(2,1)×C(1,1)÷P(2,2)×P(3,3) = 36
  • 分组+分配：
    1. 分组：3,1,1、2,2,1
    2. 计算的时候要考虑相邻情况：C(3,1)×C(2,1)×C(1,1)÷P(2,2)×P(3,3) + C(3,2)×C(1,1)×P(3,3) = 36
       3人组中插入AB + AB单独作为1个2人组

• 将5人分配到3个小组，每人只能分配到1个小组，每个小组最少1人，且A、B两人不能在一起，有多少种分配方案？

  1. 先不管限定条件，直接分组：3,1,1、2,2,1 => (C(5,3)×C(2,1)×C(1,1)÷P(2,2) + C(5,2)×C(3,2)×C(1,1)÷P(2,2)) ×P(3,3)
  2. 排除A、B在一起的情况：(C(5,3)×C(2,1)×C(1,1)÷P(2,2) + C(5,2)×C(3,2)×C(1,1)÷P(2,2)) ×P(3,3) - C(3,1)×C(2,1)×C(1,1)÷P(2,2)×P(3,3) - C(3,2)×C(1,1)×P(3,3)

• 将7人分配到3个小组，每个小组至少2人，且A和B去同一个小组，C不能去小组1，有多少种分配方案？

  1. 分组且AB同组（先不×P(2,2)）：3,2,2 => C(5,1)×C(4,2)×C(2,2)÷P(2,2) + C(5,3)×C(2,2)
  2. C不能去小组1，由此可以去余下两组，则包含丙这组只有两种情况=>×2，余下两组自由选择P(2,2)
  3. 总计：(C(5,1)×C(4,2)×C(2,2)÷P(2,2) + C(5,3)×C(2,2))×2×P(2,2)

4. 拓展

此章节不定时更新

1. 给小朋友分糖果Ⅱ
   • 题述：给你两个正整数 n 和 limit 。
     请你将 n 颗糖果分给 3 位小朋友，确保没有任何小朋友得到超过 limit 颗糖果，请你返回满足此条件下的 总方案数 。
   • 示例：

     示例 1：输入：n = 5, limit = 2
     输出：3
     解释：总共有 3 种方法分配 5 颗糖果，且每位小朋友的糖果数不超过 2 ：(1, 2, 2) ，(2, 1, 2) 和 (2, 2, 1) 。示例 2：输入：n = 3, limit = 3
     输出：10
     解释：总共有 10 种方法分配 3 颗糖果，且每位小朋友的糖果数不超过 3 ：(0, 0, 3) ，(0, 1, 2) ，(0, 2, 1) ，(0, 3, 0) ，(1, 0, 2) ，(1, 1, 1) ，(1, 2, 0) ，(2, 0, 1) ，(2, 1, 0) 和 (3, 0, 0) 。
     

   • 分析：这题的本质是在有界范围内求非负整数解的个数，属于隔板法/切面包法的变形问题
     1. 假设三个小朋友分别获得a、b、c颗糖果，有表达式：a + b + c = n （a、b、c 取值区间 [0,limit])
        为了使用切面包法，需要让取值 ≥ 1，即：a + b + c = n + 3 （a、b、c 取值区间 [1,limit + 1])
     2. 忽略limit，有分配总数：C(n+2, 2)
     3. 现在考虑超过limit的情况，有3种：1人超过限制，2人超过限制，3人超过限制:
        a. 1人超过限制：先给1人提前分配 limit + 1 颗糖果 （因为等式已经 +1 【因为每人可被分配0颗】，所以这里也要 + 1），有：C(3,1)*C(n-(limit + 1) + 2, 2)
        b. 2人超过限制，有：C(3,2)C(n-2(limit + 1) + 2, 2)
        c. 3人超过限制，有：C(3,3)C(n-3(limit + 1) + 2, 2)
     4. 总计：C(n+2, 2) - 3*(n-(limit + 1) + 2, 2) + 3*(n-2*(limit + 1) + 2, 2) - (n-3*(limit + 1) + 2, 2)
        这里用+是因为当我们把所有「单个违规」的情况相加时，这个既有 A 违规又有 B 违规的方案就被算了两次

        假设有一个具体的分配方案，其中 小朋友 A 和 B 都违规（也就是说，A 得到了 limit+1 颗或更多，B 同样如此）。当我们统计集合 A 时，这个分配方案满足「小朋友 A 违规」，所以它被计入 A 中。
        同样地，在统计集合B 时，这个方案也满足「小朋友 B 违规」，它又被计入B 中。
        这样，当我们把所有「单个违规」的情况相加时，这个既有 A 违规又有 B 违规的方案就被算了两次。
        

     5. java代码如下：

        class Solution {public long distributeCandies(int n, int limit) {return combination(n + 2, 2) - 3*combination(n - (limit + 1)+2, 2) + 3*combination(n - 2*(limit + 1)+2, 2) - combination(n - 3*(limit + 1)+2, 2);}public static long combination(int a, int b) {if (a < b) {return 0;}return ((long) a * (a - 1)) / 2;}
        }