贡献者： 零穹
1组合学的一个重要方面在与计数问题。实际上，在很长一段时间里，大多数数学工作者把组合学与 “计数” 当作一回事。“计数” 往往是指找出进行某个确定的运算方法的个数，与之紧密联系的内容便是排列组合。
“排列” 和 “组合” 这两个术语在高中部分已经熟悉。本节将给予这些概念于一个更完整、更直观的描述，这意味着要建立一些术语，而这些术语给出了这种直观的意义。排列组合在很多方面都有应用，本节的术语将使得这种应用更加直观。
1. 布置 Arrangement
排列组合的很多应用在于将一定数量的 “物体” 放置在一定数量的 “房间”（盒子）中，下面的定义使得这种应用更加明显。
定义 1 物体、房间、布置
设 $X,Y$ 是有限集，把 $X$ 的元素叫做物体，把 $Y$ 的元素叫房间。映射 $f:X\rightarrow Y$ 称为物体集合 $X$ 到房间集合 $Y$ 的一种布置（arrangement）。
物体集合 $X$ 到房间集合 $Y$ 的映射 $f:X\rightarrow Y$ 使得 $y_i$ 与 $X$ 的一些元素构成的集合
\begin{equation}
\{x|x\in X,f(x)=y_i\}~.
\end{equation}
相对应。称 $f$ 为布置暗示着 $f$ 将 $X$ 中的物体放置或分配到 $Y$ 中的房间内。
和很多命名一样，关于集合的元素是为了方便人们的记忆和应用。比如研究矢量的集合称为矢量空间，集合中的元素称为矢量；研究点集拓扑学的集合称为拓扑空间，其上的元素称为点。对应的，与组合数学对应的集合分别称为物体（定义域）和房间（值域），而物体到房间的映射称为布置。
当 $ \left\lvert X \right\rvert =n, \left\lvert Y \right\rvert =m$ 时，每个函数 $f$ 和一个字符串 “$f(x_1)\cdots f(x_n)$” 相对应。往往字符串代表着一个字，比如字 word 是由字母 “w”，“o”，“r”，“d” 构成的，下面的定义给出了这种直观上的意义。
定义 2 字母，字
设 $X,Y$ 分别是基数为 $ \left\lvert X \right\rvert =n, \left\lvert Y \right\rvert =m$ 的有限集，$f:X\rightarrow Y$ 是 $X$ 到 $Y$ 上的映射，则称 $Y$ 的元素为字母, $f$ 是由 $Y$ 中的字母形成的长度为 $n$ 的一个字 $f(x_1)\cdots f(x_n)$。
上面定义中，$X$ 可看成给出了字的一个顺序。
通过这些概念，得到以下一些定理。
定理 1
设 $X,Y$ 分别是基数为 $ \left\lvert X \right\rvert =n, \left\lvert Y \right\rvert =m$ 的有限集，则映射 $f:X\rightarrow Y$ 的个数等于 $m^n$。
证明：由定义 2 ，$f$ 的个数等于由 $Y$ 中的字母拼成的长度为 $n$ 的字的个数。因为字的第一个字母有 $m$ 种选法，第二个，$\cdots$，第 $n$ 字母也有 $m$ 种选法。由乘法原则（子节 2 ），结果字的个数等于 $\underbrace{m\cdots m}_{n\text{个}}=m^n$。
证毕！
将上述定理换成定义 1 的语言，得到：
定理 2
$n$ 个物体的集合在 $m$ 个房间的集合里的布置个数为 $m^n$。
定理 1 就是不管集合 $X,Y$ 是否有限，所有的映射 $f:X\rightarrow Y$ 的集合常记作 $Y^X$ 的原因。
定义 3 有序布置
设物体集合 $X$ 被布置在房间集合 $Y$ 里，且每个房间可容纳 $X$ 中任意个物体，若改变房间中物体的顺序得到的布置不同，则称这样的布置叫作房间里的有序布置（ordered arrangement）。$n$ 个物体在 $m$ 个房间里有序布置的个数记作 $[m]^n$。
定理 3
$n$ 个物体在 $m$ 个房间里有序布置的个数 $[m]^n$ 为
\begin{equation}
[m]^n=m(m+1)\cdots(m+n-1)~.
\end{equation}
证明：
记 $T_n$ 为 $n$ 个物体在 $m$ 个房间里的所有有序布置的集合。设 $T_{n-1}$ 是前 $n-1$ 个物体在 $m$ 个房间里的所有有序布置的集合，则 $T_n$ 可以这样构造：将第 $n$ 个物体 $x_n$ 插入到 $T_{n-1}$ 的每一有序布置中得到。
由于 $T_{n-1}$ 的每一有序布置都可用 $n-1$ 个物体和 $m-1$ 个分隔符表示，其中 $m-1$ 个分隔符将 $n-1$ 个物体分为 $m$ 段，第 $i$ 段对应第 $i$ 个房间内物体的一个有序布置。因此可以用 $(n-1)+(m-1)=n+m-2$ 个记号的序列来表示 $T_{n-1}$ 的一个布置，这些记号标记了这 $n-1$ 个物体和 $m-1$ 个分隔符。
将 $x_n$ 加入到 $T_{n-1}$ 的每个有序布置中，其可以放在每个记号标记的物体或房间前后，每一种方法都对应 $T_{n}$ 中的不同有序布置。所以 $T_{n-1}$ 的每个有序布置都可产生 $n+m-2+1=n+m-1$ 个 $T_n$ 的有序布置。于是
\begin{equation}
\left\lvert T_n \right\rvert =(m+n-1) \left\lvert T_{n-1} \right\rvert ~.
\end{equation}
重复这种关系，可得到
\begin{equation}
\left\lvert T_n \right\rvert =(m+n-1)(m+n-2)\cdots (m+1) \left\lvert T_1 \right\rvert ~.
\end{equation}
由于单个物体在 $m$ 个房间的有序布置个数 $ \left\lvert T_1 \right\rvert =m$，所以
\begin{equation}
[m]^n= \left\lvert T_n \right\rvert =m(m+1)\cdots(m+n-1)~.
\end{equation}
2. 排列
定理 4
设 $X,Y$ 分别是基数为 $ \left\lvert X \right\rvert =n, \left\lvert Y \right\rvert =m$ 的有限集，则单射 $f:X\rightarrow Y$ 的个数为 $m(m-1)\cdots(m-n+1)$。
证明：函数 $f$ 的单一性由字的字母是两两不同的这个事实表示。因为字的第一个字母有 $m$ 种选法，第二个字母有 $m-1$ 种选法，$\cdots$，第 $n$ 个字母有从剩下的 $m-n+1$ 个字母中有 $m-n+1$ 中不同选法。由乘法原则，由 $m$ 元集 $Y$ 的 $n$ 个不同字母构成的字的个数为 $m(m-1)\cdots(m-n+1)$。
证毕！
同样的，上述定理相当于：
定理 5
将 $n$ 个物体的集合在 $m$ 个房间的集合里进行布置，要求每个房间至多包含一个物体的布置个数为 $m(m-1)\cdots(m-n+1)$。
定义 4 排列，全排列
从 $m$ 元集 $Y$ 的 $n$ 个不同字母构成的字叫作从集合 $Y$ 的 $m$ 个物体每次取 $n$ 个的排列（permutation）(或 $m$ 元集 $Y$ 的 $n$ 排列)，其个数记为 $[m]_n$ (或 $P(m,n)$)，其中 $m\geq n$。若 $m=n$，则 $[n]_n$ 也记作 $P_n$ 或 $n!=1\cdot2\cdots n$，此时的排列称 $n$ 元集 $Y$ 的全排列.
由定理 5
\begin{equation}
[m]_n=P(m,n)=m(m-1)\cdots(m-n+1)~.
\end{equation}
3. 组合
定义 5 增字
若集合 $Y=\{y_1,y_2,\cdots,y_m\}$ 是个偏序集（子节 5 ），那么称由 $Y$ 的 $n$ 个字母构成的字 $y_{i1}y_{i2}\cdots y_{in}$ 为增字，如果 $y_{i1}\leq y_{i2}\leq\cdots\leq y_{in}$。若 $y_{i1}< y_{i2}<\cdots< y_{in}$，则称字 $y_{i1}y_{i2}\cdots y_{in}$ 为严格增字。
定理 6
从 $m$ 个字母中选出 $n$ 个构成的增字个数等于 $\frac{[m]^n}{n!}$。
证明：下面将增字和 $n$ 个物体在 $m$ 个房间里的有序布置联系起来：若房间 $y_i$ 里有选自集合 $\{x_1,x_2,\cdots,x_n\}$ 的 $p_i$ 个物体，在构造增字里这个房间 $y_i$ 就写 $p_i$ 次：$\underbrace{y_i\cdots y_i}_{p_i\text{个}}$；
若房间 $y_i$ 不包含物体，$y_i$ 就不出现在增字中。例如（不失一般性设 $y_1\leq y_2\leq\cdots$）：
\begin{equation}
\begin{aligned}
&x_2| x_1 x_3 x_6|x_4 x_5|\quad|x_7\cdots\\
&y_1\quad y_2\qquad y_3\quad y_4\quad y_5~.
\end{aligned}
\end{equation}
对应增字
\begin{equation}
y_1y_2y_2y_2y_3y_3y_5\cdots~.
\end{equation}
这一构造说明每一有序布置都有一增字对应，且哪些物体放在房间里对增字没有影响，而只有房间里的物体个数有意义。即不改变房间物体数的所有布置都对应于每一增字，而不改变房间物体数的有序布置共 $n!$ 个（比如房间 $y_i$ 的物体数有 $p_i$ 个，对于 $n$ 个物体所有可能的排列个数为 $n!$，将每一排列分成 $m$ 段，第 $i$ 段对于房间 $y_i$，且第 $i$ 段的物体数为 $p_i$，这便是保持房间 $y_i$ 的物体数 $p_i$ 不变的所有有序布置），因此每一增字都对应 $n!$ 个有序布置。
显然对应不同增字的有序布置是不同的，即对应不同增字的有序布置的构成集合是不相交的，而每一有序布置都在这样的某个集合里，即每一增字对应的 $n!$ 个有序布置的集合构成了所有有序布置构成集合的不相交的并集（也称不交并）。因此，若设增字的个数为 $x$，则 $x\cdot n!=[m]^n$。
证毕！
定义 6 重复组合
从 $m$ 个字母的集合 $Y$ 中选出 $n$ 个构成的增字也叫从 $m$ 个物体的集合 $Y$ 中一次取 $n$ 个的重复组合。
定理 7
从 $m$ 个字母中取 $n$ 个构成的严格增字的个数为 $\frac{[m]_n}{n!}$。
证明：由定义 4 知道，从 $m$ 个字母的集 $Y$ 中的 $n$ 个不同字母构成的字的集合有 $[m]_n$ 个元素，而这 $[m]_n$ 个字都能由 $Y$ 中的 $n$ 个字母构成的严格增字的集合里，用 $n!$ 种不同的方法排列每个字的字母无重复的得到。因此，若设从 $m$ 个字母中取 $n$ 个构成的严格增字的个数为 $x$，则
\begin{equation}
x\cdot n!=[m]_n~.
\end{equation}
证毕！
注意 $m$ 元集的 $n$ 元子集的每一个都和一个由该子集中的元素构成的增字一一对应，所以由下面推论。
推论 1
$m$ 元集 $Y$ 的 $n$ 元子集个数为 $\frac{[m]_n}{n!}$。
定义 7 组合
由 $Y$ 中 $n$ 个字母构成的严格增字也叫从 $m$ 个物体的集合 $Y$ 中一次取 $n$ 个的组合（combination），其个数记作 $C_m^n$ 或 $\left(\begin{aligned}&m\\&n\end{aligned}\right)$
由定理 6
\begin{equation}
C_m^n=\left(\begin{aligned}
m\\n
\end{aligned}\right)=\frac{[m]_n}{n!}=\frac{m!}{(m-n)!n!}~.
\end{equation}
4. 多项式数
定理 8
若物体集合 $X=\{x_1,x_2,\cdots x_n\}$ 在房间集合 $Y=\{y_1,y_2,\cdots,y_p\}$ 的布置，使得房间 $y_i$（$i=1,\cdots,p$）分别含有 $n_i$ 个物体（$\sum_{i}^p n_i=n$）。则这样的布置个数为
\begin{equation}
\frac{n!}{n_1!n_2!\cdots n_p!}~.
\end{equation}
证明：首先，和定理 6 证明中提到的一样，不改变房间内物体数的有序布置个数为 $n!$，那么在房间中物体顺序无关的布置情形，这 $n!$ 个有序布置中，房间 $y_i$ 内 $n_i$ 个物体的 $n_i !$ 个全排列对应的布置都是同一个，故知该定理对应的布置（与房间中物体顺序无关）个数为
\begin{equation}
\frac{n!}{n_1!n_2!\cdots n_p!}~.
\end{equation}
证毕！
定义 8 多项式数
称数 $\frac{n!}{n_1!n_2!\cdots n_p!}$ 为多项式数，并记作 $\left(\begin{aligned}
&n\\n_1,n_2,&\cdots,n_p
\end{aligned}\right)$。
多项式数推广了组合数（$p=2$ 的情形），并且将二项式公式（式 1 ）扩充到一般的多项式中：
\begin{equation}
(a_1+\cdots+a_p)^n=\sum_{\begin{aligned}
&n_1,\cdots n_p\\
n_1+&\cdots+n_p=n
\end{aligned}}\left(\begin{aligned}
&n\\n_1,n_2,&\cdots,n_p
\end{aligned}\right)a_1^{n_1}\cdots a_p^{n_p}~.
\end{equation}
上式的成立可通过将 $a_1^{n_1}\cdots a_p^{n_p}$ 理解成在第 $i$ 个房间放 $n_i$ 个物体 $a_i$ 得到（相当于在 $n$ 个括号中的 $n_i$ 个里取 $a_i$ 作乘法）。
1. ^ I.Tomeson.组合学引论，栾汝书等译。高等教育出版社。1987.