贡献者： 零穹
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.
致读者： 小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此，我们请求广大读者
热心打赏 ，使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损， 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款， 他们的付出帮助了 99% 的读者免费获取知识， 我们在此表示感谢。