附
录
一.两个基本计数原理分类加法计数原理：做一件事情，完成它有n 类办法，在第一类办法中有m 1种不同的方法，在第二类办法中有m 2种不同的办法……在第n 类办法中有m n 种不同的方法，那么完成这
件事情共有N＝m 1＋m 2＋…＋m n 种不同的方法。
分步乘法计数原理：做一件事情，完成它需要分成n 个步骤，做第一个步骤有m 1种不同的方法，做第二个步骤有m 2种不同的办法……做第n 个步骤有m n 种不同的方法，那么完成这件
事情共有N＝m 1×m 2×…×m n 种不同的方法。
两个基本计数原理是解决计数问题最基本的理论根据，它们分别给出了用两种不同方式（分类和分步）完成一件事情的方法总数的计算方法。考虑用哪个计数原理，关键是看完成一件事情是否能独立完成，决定是分类还是分步。如果完成一件事情有n 类办法，每类办法都能独立完成，则用分类加法计数原理；如果完成一件事情，需要分成n 个步骤，各个步骤都是不可缺少的，需要依次完成所有步骤，才能完成这件事情，则用分步乘法计数原理。
二.排列
以下陈述中如无特别说明，n、m 都表示正整数。一般的，从n 个不同的元素中任取m （m ≤n）个元素，按照一定的顺序排成一列，叫做从n 个不同元素中取出m 个元素的一个排列。如果要求排列中诸元素互不相同，则称为选排列；反之，若排列中的元素可以有相同时，则称为可重复排列。可重复排列在生活中比较常见，如电话号码、证件号码、汽车牌照，等等。从n 个不同的元素中任取m（m ≤n）个元素的所有排列的个数，叫做从n 个不同元素中任取m 个元素的排列数。用符号m n A 。为导出m n A 的计算公式，注意到对任一选排列，其第一位（从左到右计）可以放置编号1到n 的n 个元素的任意一个，共有n 种可能的结果；对于第一位的每一种放置结果，第二位可以放置剩下的n-1个元素中的任意一个，共有n-1种可能的结果；...,对于第m-1位的每一种放置结果，第m 位可以放置最后剩下的n-m+1个元素中的任何一个，共有n-m+1种可能结果。因此，根据乘法计数原理，有排列数公式：
)
1()2)(1(+---=m n n n n A m n （1.3）从n 个不同的元素全部取出的一个排列，叫做n 个不同元素的一个全排列，记作n n A ，也记之
为!n 。根据排列数的公式有
.12)1(!⋅⋅⋅⋅-⋅=n n n （1.4）
同时我们约定当n=0时，0！＝1。
m n A 也可用全排列数表示，容易从（1.3）式直接得到
!)!(!
m m n n A m n -=（1.5）
下面计算所有不同的可重复排列数，仿照（1.3）式的推理，排列的第一位的放置有n 种可能结果。由于可重复性，当11-≤≤m i ，对于第i 位的每一种放置结果，第i+1位仍然可放置全部n 个元素中的任何一个，因而仍然有n 种可能结果。依乘法计数原理可得可重复排列种数为
m
n n n = （1.6）
三、组合一般地，从n 个不同的元素中任取m（m ≤n）个元素，不考虑次序将它们并成一组，叫做从n 个不同元素中取出m 个元素的一个组合。从n 个不同的元素中任取m（m ≤n）个元素的所有组合的个数，叫做从n 个不同元素中任取m 个元素的组合数。用符号m n C
或)(m n 。为导出组合数m n C 的计算公式，可以考虑选排列数m n A 的另一种算法。为实现一个排列，
可以分两步走：先从n 个元素中任取m 个不同元素归并成一个组合；然后，将该组合中的m 个元素进行全排列。第一步有m
n C 个可能结果，对第一步产生的每一个组合，第二步有!m 个可能结果。于是，依乘法计数原理有
m n A =!m C m n ⋅由此即可得到组合数的计算公式：
),,(!)1()2)(1(n m N n m n m n n n n C m n ≤∈-=+---=+且 （1.7）依前面的约定0！＝1，因而当r=0时，10=n C 。又从组合的定义可知：每一个从n 个元
素取r 个的组合，其余下的n-r 个元素也构成一个组合；反之亦然。因而从n 个元素取r 个的组合与从n 个元素取n-r 个组合构成一一对应。所以有
m n n m n C C -=（1.8）
