计数前先确认两件事：顺序是否重要，是否允许重复。这决定了该用 permutation、combination，还是 stars and bars 等其他模型。

Permutations：顺序重要

一个 $n$ 元集合的 $k$-permutation，是从中选出 $k$ 个不同元素并按顺序排列。这里 $n$、$k$ 都是非负整数，且 $k$ 不超过 $n$。这样的排列共有

种。Factorial 记号的含义是

例：分配三个职务

从一个有 $20$ 名学生的班级中选出 president、vice-president 和 secretary。三个职务不同，而且由不同学生担任，所以顺序重要：

也可以写作

当 $k=n$ 时，所有元素都被使用。这是完整的 permutation，并且

例如，集合 $\{1,2,3,4,5\}$ 共有

种 permutation。

Combinations：顺序不重要

一个 $n$ 元集合的 $k$-combination 是一个恰有 $k$ 个元素的 subset，元素顺序不影响结果。记号

读作“$n$ choose $k$”，称为 binomial coefficient。

每一组已选出的 $k$ 个元素都有 $k!$ 种排列方式。把 permutation 的数量除以 $k!$，就能消去由不同顺序带来的重复计数：

例：选一个委员会

从 $20$ 名学生中选出一个三人委员会，不分配职务。有序计数把同一组三名学生算了 $3!=6$ 次，因此

例：扑克牌手牌与 flushes

一手五张牌是从 $52$ 张牌中选出的五元素集合，所以手牌总数是

如果要求五张牌全是同一种花色，可以分两步：

1. 从四种花色中选择一种；
2. 从该花色的十三张牌中选择五张。

由 product principle，数量为

例：恰有四个零的 bit strings

一个长度为 $10$、恰好包含四个零的 bit string，由这四个零所占的位置唯一确定。因此数量为

剩下六个位置自动填一。

Stars and bars

把相同的对象分配到不同类别、且同一类别可以得到多个对象时，可以使用 stars and bars。

假设商店有七种巧克力口味，我们要买四块。购买顺序不重要，也可以重复选同一种口味。用一个 star 表示一块巧克力，再用六个 divider 把 stars 分到七种口味中。

例如，

**|*||*|||

表示第一种口味两块、第二种一块、第三种零块、第四种一块，最后三种都不买。

每一种购买方案都唯一对应一个含四个 stars、六个 dividers 的字符串。字符串共有十个位置，选定四个 star 的位置就确定了整个方案，因此共有

一般地，把 $r$ 个相同对象分给 $n$ 个不同类别，其中 $r$ 是非负整数、$n$ 是正整数。若允许某个类别分到零个对象，方案数为

这里每种方案只记录各类别分到多少个，不区分对象本身的身份。

两个 binomial identities

Combinatorial proof 通过用两种方法数同一批对象，说明两个表达式相等。

Symmetry

第一个 identity 是

长度为 $n$、含有 $k$ 个零的 bit string，一定含有 $n-k$ 个一。数同一批字符串，可以选择：

• 零所占的 $k$ 个位置，共有 $\binom nk$ 种；或
• 一所占的 $n-k$ 个位置，共有 $\binom n{n-k}$ 种。

两个表达式数的是完全相同的字符串，所以它们相等。

Pascal's identity

Pascal's identity 是

先考虑 $k$ 至少为一、至多为 $n$ 的情形。一个班有 $n+1$ 名学生，其中有一名指定的学生，称为 student $0$。把所有 $k$ 人委员会分成两个 disjoint 的情况：

1. Student $0$ 在委员会中。从其余 $n$ 人里选另外 $k-1$ 人，共有 $\binom n{k-1}$ 种。
2. Student $0$ 不在委员会中。全部 $k$ 人都从其余 $n$ 人里选，共有 $\binom nk$ 种。

这两种情况互不重叠，又包含了所有委员会，因此 sum principle 给出 Pascal's identity。边界处可直接使用下面的边界值；若要在边界也套用这个 identity，则约定超出可选人数范围的 binomial coefficient 为零。

Pascal's triangle

根据 Pascal's identity，每个内部的 binomial coefficient 都等于它上方相邻两项之和。边界值为

前五行是

例如，

这样就能递归地用加法计算 binomial coefficients，而不必直接计算 factorials。