可重排列
Abstract
可重排列与可重组合是计数理论中处理”允许重复选取”问题的两大核心工具。可重排列关注有序选取（排列数 ），可重组合关注无序选取（通过隔板法得到 ）。两者在密码学、分配问题、组合优化等领域有广泛应用。
定义
可重排列（r-Permutation with Repetition）
从 个不同类型的物体中，允许重复地选取 个物体进行有序排列，其排列数为：
其中每个位置都有 种选择，由乘法原理直接得出。
可重组合（r-Combination with Repetition / 隔板法）
从 个不同类型的物体中，允许重复地选取 个物体（不计顺序），其组合数为：
该公式也称为隔板法（Stars and Bars）公式。
隔板法（Stars and Bars Theorem）
将 个不可区分的星号（代表被选物体）排成一排，用 个隔板分成 组（每组对应一类物体），则不同的分组方式数为：
直观理解： 个星号和 个隔板共占 个位置，从中选 个位置放隔板（或等价地选 个位置放星号），即得公式。
核心性质
| 编号 | 性质 | 公式 / 说明 |
|---|---|---|
| 1 | 可重排列的乘法原理 | 每个位置独立选择，共 个位置，每个位置 种选择，故总数为 |
| 2 | 可重组合 = 隔板法 | ，本质是将 个不可区分物品分配到 个可区分盒子 |
| 3 | 对称形式 | ，由二项式系数对称性直接得出 |
| 4 | 退化情况 | 当不允许重复时（每类最多选1个）， 退化为 （需 ） |
| 5 | 隔板法图示 | 选3类水果共5个： 表示”2个第1类、1个第2类、2个第3类” |
| 6 | 与分配问题的等价性 | 可重组合数等于”将 个不可区分物体放入 个可区分盒子”的方案数 |
| 7 | 生成函数联系 | 可重组合的生成函数为 ， 的系数恰为 |
关系网络
graph TD A["可重排列<br/>$n^r$"] --> B["排列<br/>$P(n,r)$"] A --> C["可重组合<br/>$\\binom{n+r-1}{r}$"] C --> D["隔板法<br/>Stars and Bars"] C --> E["组合<br/>$\\binom{n}{r}$"] C --> F["分配问题<br/>不可区分物体→可区分盒子"] D --> F B --> G["多重集排列<br/>$\\frac{n!}{n_1! n_2! \\cdots n_k!}$"] F --> H["斯特林数<br/>$S(n,k)$"]
章节扩展
- 第6.5节：本概念是Rosen教材第6.5节的核心内容，与多重集排列、分配问题共同构成”高级计数技术”模块。
- 隔板法的推广：当要求某些盒子至少装1个物体时，可先每盒预放1个，转化为 （要求 ）。
- 应用场景：密码学中密钥空间计算、投票问题中票数分配、整数方程 的非负整数解个数。
补充
隔板法的严格证明
设 表示第 类物体被选取的个数，则可重组合问题等价于求方程 的非负整数解的个数。将 个星号排成一行，插入 个隔板将其分为 段，第 段的星号数即为 。 个星号与 个隔板共 个位置，选其中 个放隔板，得 种方案。
经典例题
从5种水果中任选10个（可重复），有多少种选法？