【编程数论】排列与组合

1.组合数的定义与背景

2. 计算公式

3. 对比排列数

利用排列组合公式，解决隔板模型问题。

• 隔板模型的概念：把一些相同的元素分给不同的对象，且每个对象都必须有，这种相同元素的分堆问题，就是隔板模型。
• 题型特征：
• 所要分的元素必须完全相同。
• 元素要全部分完，不允许有剩余。
• 每个对象至少分到 1 个元素。
• 解题原理与公式：假设将$n$个相同元素分给$m$个不同对象，每个对象至少分得 1 个。可以将$n$个相同元素排成一排，$n$个元素中间会形成$n-1$个空隙。在这些空隙当中选择$m-1$个位置插入木板，就可以将这些元素分为$m$堆，每堆至少 1 个。所以总的分法就是在$n-1$个空隙中选择$m-1$个空隙插上木板的组合数，记为$C_{n-1}^{m-1}$。
• 典型例题：有 12 个相同的篮球，分给 5 个班级，每个班级至少一个，有多少种分配方案？
• 分析：此问题符合隔板模型的 3 个条件，可将其视作求 12 个相同的元素分成 5 堆，每堆至少一个的情况数。
• 解答：将 12 个相同元素一字排开，要分成 5 堆需要 4 个隔板，而 12 个元素之间有 11 个空隙，所以只需在 11 个位置中任选 4 个放置隔板即可，情况数为$C_{12-1}^{5-1}=C_{11}^4=\frac{11!}{4!(11-4)!}=\frac{11\times 10\times 9\times 8}{4\times 3\times 2\times 1}=330$种。
• 隔板模型的变形：
• 每个对象至少分多个元素：若题目中要求每个对象至少分$a$个元素（$a>1$），可以先从总数中给每个对象先分去$a-1$个元素，再将剩下的相同元素用隔板法公式进行分配。例如，将 15 份公文分给三个人，每人至少 3 份。可以先给每人 2 份，剩下$15-2\times 3=9$份，此时题目就转换成了 9 份公文分给三个人，每人至少 1 份，可根据公式计算为$C_{9-1}^{3-1}=C_8^2=28$种。
• 允许某些对象为空：将$n$件相同物品分给$m$个人，允许若干个人为空，可以看成将这$n$件物品和$m-1$块隔板排成一排，占$n+m-1$位置，从这$n+m-1$个位置中选$m-1$个位置放隔板，共有$C_{n+m-1}^{m-1}$种不同的方法。

  ---

• 排列组合是数学中处理 “计数问题” 的重要工具，但其抽象性和灵活性常让人困惑。掌握以下技巧可以帮助更清晰地理解和运用排列组合：

• 一、明确核心区别：“有序” vs “无序”

• 排列与组合的本质区别在于是否考虑顺序，这是判断用 “A” 还是 “C” 的关键：
• 
  
• 排列（A）【Arrangement】：元素选取后需要考虑顺序（如 “选 3 人站成一排”“密码锁的密码”）。
  例：从 5 人中选 2 人分别担任班长和副班长，顺序不同结果不同，用$A_5^2$。
• 组合（C）【Combination】：元素选取后不考虑顺序（如 “选 2 人参加活动”“从一堆球中取 3 个”）。
  例：从 5 人中选 2 人参加会议，选法与顺序无关，用$C_5^2$。
• 
  
• 技巧：用 “交换法” 验证 —— 若交换两个元素的位置后结果不同，则是排列；若相同，则是组合。

• 二、掌握 “分类” 与 “分步” 的逻辑（加法原理 vs 乘法原理）

• 排列组合的计数过程本质是 “分类” 或 “分步” 的过程：
• 
  
• 加法原理（分类）：
  完成一件事有多种 “独立方案”，方案之间互斥（选一种即可完成），总方法数为各方案方法数之和。
  例：从 A 地到 B 地，坐火车有 3 种方式，坐汽车有 2 种方式，总方法数为$3+2=5$。
• 乘法原理（分步）：
  完成一件事需要分多个 “步骤”，步骤之间依赖（缺一不可），总方法数为各步骤方法数之积。
  例：从 A 到 B 再到 C，A 到 B 有 3 种方式，B 到 C 有 2 种方式，总方法数为$3\times 2=6$。
• 
  
• 技巧：遇到复杂问题时，先判断是 “分类完成” 还是 “分步完成”，再逐层拆解。

• 三、牢记经典模型，套用 “模板” 解题

• 排列组合的很多问题可以归纳为经典模型，掌握这些模型能快速破题：
• 
  
• 相邻问题：捆绑法
  要求某些元素必须相邻时，将它们 “捆绑” 成一个整体，与其他元素一起排列，再考虑捆绑内部的顺序。
  例：3 个男生和 2 个女生排成一排，女生必须相邻。
  解：将 2 个女生捆绑为 1 个 “整体”，与 3 个男生共 4 个元素排列（$A_4^4$），再考虑女生内部顺序（$A_2^2$），总方法数为$A_4^4\times A_2^2=48$。
• 不相邻问题：插空法
  要求某些元素不相邻时，先排无要求的元素，再将不相邻元素插入它们的空隙中。
  例：3 个男生和 2 个女生排成一排，女生不相邻。
  解：先排 3 个男生（$A_3^3$），形成 4 个空隙（包括两端），从中选 2 个插入女生（$A_4^2$），总方法数为$A_3^3\times A_4^2=72$。
• 相同元素分堆：隔板法（见前文教程）
  适用于 “相同元素分给不同对象” 的问题，核心是用 “隔板” 分隔元素。
• 全排列中的 “重复元素” 问题
  若 n 个元素中有重复（如 k 个相同元素），则全排列数为$\frac{n!}{k!}$（重复元素越多，结果越小）。
  例：“AAB” 的全排列数为$\frac{3!}{2!}=3$（即 AAB、ABA、BAA）。
• 错位排列：元素不回到原位
  如 “n 封信装入 n 个信封，全部装错”，记为$D(n)$，公式：$D(n)=(n-1)\times [D(n-1)+D(n-2)]$（$D(1)=0$，$D(2)=1$）。
  例：3 个元素的错位排列数$D(3)=2$。

• 四、逆向思维：“正难则反”

• 当直接计算符合条件的情况数较复杂时，可先算总情况数，再减去不符合条件的情况数。
  例：从 5 人中选 3 人，排除某 1 人不入选的情况。
  解：总情况数$C_5^3$，减去 “某 1 人不入选” 的情况$C_4^3$，结果为$C_5^3-C_4^3=10-4=6$。

• 五、通过 “具象化” 理解抽象问题

• 排列组合的抽象性强，可通过 “举例”“画图” 等方式将问题具象化：
• 
  
• 用 “树状图” 列举简单情况（如 2 个元素的排列组合），观察规律。
• 用 “位置法” 分析：将问题拆解为 “第 1 位选什么，第 2 位选什么……”，逐步计数。
  例：“用 1、2、3 组成无重复数字的两位数”，可按 “十位”“个位” 分步：十位 3 种选择，个位 2 种选择，共$3\times 2=6$种。

• 六、多练 “易混淆题型”，总结细节

• 排列组合的陷阱常在于细节，需特别注意：
• 
  
• 元素是否可重复：如 “密码锁” 可重复（每位数字独立），“排队选不同人” 不可重复。
• 是否包含特殊元素 / 位置：如 “排列中某元素必须在首位”，需优先处理特殊要求。
• “至少”“至多” 问题：优先用逆向思维或分类讨论（如 “至少选 1 个女生”= 总情况 - 全选男生）。

• 总结

• 排列组合的核心是 “逻辑拆解”：先明确 “有序 / 无序”，再用 “分类 / 分步” 拆解，最后套用经典模型或逆向思维。通过大量练习不同题型，熟悉细节陷阱，就能逐步掌握其规律。
  

  ---

  
  

• Day09-计数原理与排列组合-（上)-作业.pdf