排列与组合

考什么 · What it tests

需要先会 · Prerequisites

• 乘法原理与阶乘 / The multiplication principle and factorials
• 基本计数原理 / Basic counting principles
• 分数约分 / Simplifying fractions

常见套路 · Common moves

1. 先判顺序，再选公式：在意先后就用排列 $A_n^m$，只在意选出哪几个就用组合 $\displaystyle C_n^m = \frac{A_n^m}{m!}$——一切排列组合题的分叉口。

   Judge order, then pick the formula: if sequence matters use the permutation $A_n^m$, if only the chosen set matters use the combination $\displaystyle C_n^m = \frac{A_n^m}{m!}$ — the fork every such problem starts at.
2. 相邻用捆绑、不相邻用插空：要求几个人挨着就先捆成一个整体再排，要求互不相邻就先排别人再往空隙里插。

   Bundle for together, gap for apart: if some must sit adjacent, tie them into one block first; if they must not be adjacent, seat the others first and slot these into the gaps.
3. 相同物品分组用隔板：把 $n$ 个相同的东西分给几个人（每人至少一个），相当于在 n-1 个缝里插隔板。

   Use dividers for identical items: handing out $n$ identical things so each person gets at least one is the same as placing dividers in the n-1 gaps.

易错点 · Common pitfalls

• 该用组合却用了排列，把同一组多数了几遍：选 3 个人组队顺序无关，用 $C$ 不用 $A$。

  Using a permutation where a combination is needed, counting one group several times: choosing 3 people for a team ignores order, so use $C$, not $A$.
• 捆绑法忘了内部还能排：几个人捆成一团，团内部自己还有排列数要乘上。

  Forgetting the internal arrangements when bundling: once several people are tied into a block, the arrangements inside the block still multiply in.