CCF 总是喜欢考排列组合。自然不可能像计算机一样枚举，有组合的技巧。

阶乘、求和、求积

表示

在说排列组合之前，必须说一些符号。

阶乘：
$n!$ 为 $n$ 的阶乘。代表着从 1 到 n 的乘积。例如 $5!=1\times 2\times 3\times 4\times 5=120$。特殊 $0!=1$。

求和：
$\sum$ 叫 sigma，即为求和。下面写开始的数字，上面写结束的数字。$\sum _1^n$ 即从 $1$ 加到 $n$。后面也可以加上表达式。例如：

同样地，数组也可以使用。

求积：
$\prod$ 和求和符号差不多，下面写开始的数字，上面写结束的数字。如：

加/乘法原理

加法原理：完成一件事有 $n$ 种方法，$a_i$ 表示方法 $i$ 的数目，那么完成这件事共有 $\sum _{i=1}^n{a}_i$ 种不同的方法。

乘法原理：完成一件事需要 $n$ 个步骤，$a_i$ 表示步骤 $i$ 的方法数目，那么完成这件事共有 $\prod _{i=1}^n{a}_i$ 种不同的方法。

更多基本定义

以下所有，$x\ge y$

排列数

从 $x$ 个不同的元素中任意选取 $y$ 个元素，组成不同的排列的所有个数。记为 ${\mathrm{A}}_x^y$。计算如下：

特殊地对于全排列问题，即上述 $x=y$：

理解为 $x$ 个不同的数任意排列，排列中第一个（步骤）有 $x$ 个选择，第二个有 $x-1$ 个选择，一直到最后即 $x-y+1$（全排列是 $1$）。

组合数

从 $x$ 个不同的元素中选 $y$ 个元素组成所有集合的个数，记作 $\left(\genfrac{}{}{0ex}{}{x}{y}\right)$（也有记作 ${\mathrm{C}}_x^y$）。
组合数相对排列数来说，不在乎顺序。那么就相当于上面的例子再去掉选出 $y$ 个元素的全排列。那么可知：

解决方法

捆绑法

此类问题要求几个元素排列时必须相邻。
解决则将这几个元素看作整体考虑。

如三个人中 1, 2 两人（一组）必须相邻，将两人看作一人，乘上 1, 2 两人可能的排列。则共有 ${\mathrm{A}}_{3-1}^{3-1}\times {\mathrm{A}}_2^2=4$。

若 $n$ 人中有 $x$ 组人必须相邻，$x$ 中第 $y$ 组要求相邻的人数记作 $m_y$，那么排列数计算为：

插空法

适用于问题要求几个元素排列时必须不相邻。
将普通元素全排列 与 从普通元素排列“空隙”（普通元素个数加一）选取不相邻元素的全排列相乘即可。“从普通元素排列‘空隙’（普通元素个数加一）和不相邻元素的全排列相乘”就相当于再把不相邻的元素排列到普通元素中的方案。

共有 $9$ 个方块，其中有 $4$ 个红色方块， $5$ 个绿色方块，所有红方块不能相邻。那么共有 ${\mathrm{A}}_{9-4}^{9-4}\times {\mathrm{A}}_{9-4+1}^4={\mathrm{A}}_5^5\times {\mathrm{A}}_6^4=43200$ 种方案。

若 $n$ 个元素中特定的 $m$ 个元素不能相邻，那么总共排列计算为：

$n-m$ 即为普通元素个数，$n-m+1$ 就是空隙个数。

隔板法

至少在我看来更容易理解的问题。将 $n$ 个元素任意放到 $m$ 个空位中，每个空位至少有一个元素（$n\ge m$）。
可以看作再 $n$ 个元素空隙中隔板，每个空隙只能放一个板。插入 $m-1$ 个隔板（即可分成 $m$ 组）到 $n-1$ 个位置（每两个元素之间为一空隙）中。就是：

如将 $10$ 个球放进 $7$ 个盒子，每个盒子至少有一个球。那么共有 $\left(\genfrac{}{}{0ex}{}{9}{6}\right)=84$ 种方案。