预备知识

1. 加法原理

设完成一件事有m种方式，其中第一种方式有n1种方法，第二种方式有n2种方法，……，第m种方式有nm种方法，无论通过哪种方法都可以完成这件事，则完成这件事的方法总数为n1+n2+…+nm.

2. 乘法原理

设完成一件事有m个步骤，其中第一个步骤有n1种方法，第二个步骤有n2种方法，……，第m个步骤有nm种方法；完成该件事必须通过每一步骤才算完成，则完成这件事的方法总数为n1×n2×…×nm.

3. 排列、组合

（1）选排列

从n个不同的元素中，任意选取r个（0<r≤n，不许重复），然后按顺序排成一列，称为从n个元素中取r个元素的一种选排列，其排列总数记为，则

特别地，当n=r时，这种选排列称为全排列，排列数为！.

（2）有重复排列

从n个不同的元素中，任意选出m个（每个元素可重复选取），然后按顺序排成一列，称为有重复排列，其排列数为nm.

（3）不同元素的组合

从n个不同元素中，每次不重复地取出r个（r≤n）元素组成一组，不计较组内各元素的次序，叫作从n个不同元素中取出r个元素的一个组合，其组合数为

性质

1.（剩余公式）

2.

（4）有重复的组合

从n个不同元素中，每次取r个为一组，各组的对象可以任意重复，则此种组合称为取的重复组合，其重复组合数以符合表示，且

4. 二项式公式

对任意正整数n及非负整数r，

于是有