2.3　排列组合和二项式定理

排列组合问题是组合数学中的重要问题，是研究数字之间关系的重要方法，对数论、函数、图论、集合论、数理逻辑等内容起着重要的支撑作用。

2.3.1　排列

1.排列的定义

定义2-19　从个不同元素中，任意取个元素，将取得的元素按照一定的顺序排成一列，该过程称为从个不同元素中取出个元素的一个排列。从个不同元素中选取个元素的所有排列的个数，称为排列数，用符号来表示。

说明：（1）排列的过程是从不同的元素中选取具有规定顺序的元素的过程；

（2）要从个不同元素中取个元素进行排列，可能不只有一种方式，其抽取的方法数的总和称为排列数。

2.排列的计算公式

排列的计算公式如下：

3.排列实例

例2-7　一个创新小组有10名学生，他们要参加学校举办的计算机创新创业大赛，每个团队由3名学生组成，并且规定1号选手、2号选手、3号选手每个人只能参加一个团队，则该创新小组共有多少种参赛方式？

解：从10名不同学生组成的团队中抽选学生参加比赛，且每名学生只能参加一个团队，该问题属于排列问题；首先从10名学生中选取一名学生作为1号选手，共有10中选法，然后选取另一名学生作为2号选手，由于已经有一名学生被选为1号选手了，2号选手只能从剩余的9名学生中选取，而3号选手只能从剩余的8名学生中选取。

计算方法一：。

计算方法二：。

2.3.2　组合

1.组合的定义

定义2-20　从n个不同元素中，任意取个元素，将取得的元素构成一组，该过程称为从n个不同元素中取出m个元素的一个组合。从n个不同元素中选取个元素的所有组合的个数，称为组合数，用符号来表示。

说明：组合和排列最主要的区别是，构成排列的元素有位置差别，而构成组合的元素没有位置差别。

2.组合的计算公式

组合的计算公式如下：

3.组合举例

例2-8　一个创新小组有10名学生，他们要参加学校举办的计算机创新创业大赛，每个团队由3名学生组成，每名学生在比赛团队中的作用是一样的，且每名学生只能参加一个团队，则这个创新小组共有多少种参赛方式？

解：由于团队成员没有位置选择，也就是说，三名选手在团队中的身份是一样的，因此该问题属于组合问题，可以从10名学生中任选3名选手。

计算方法：。

2.3.3　二项式定理

1.基本计数原理

（1）加法原理：若做一项工作有多类方法（这里设为n），而在每类方法中，又有多种方法可以完成该工作，用来表示每类的方法数，则完成该工作的全部方法数可以表示为；这和集合的并集操作是一致的。

（2）乘法原理：若一项工作可分解为多个步骤（这里设为n），而在每个步骤中，又有多种方法可以完成该步骤，用来表示每个步骤的方法数，则完成该工作的全部方法数可以表示为。

2.二项式定理

二项式定理又称为牛顿二项式定理，它可将两个数之和的整数次幂展开为相应项之和。

根据该定理，可以将的任意整数次幂展开成一系列项之和的形式：

其中，称为二项式系数。该公式称为二项式公式。

根据二项式公式和组合计算公式，二项式公式还可以写成如下形式：

2.3.4　综合案例及应用

例2-9　通过Python实现如图2-2所示的杨辉三角的输出。

对该问题的分析如下：

（1）数字分析：通过杨辉三角图形可以看出，每行起点与结尾的数都为1；每个数等于它上方两数之和；每行数字左右对称，从两头由1开始逐渐变大。

（2）图形分析：在杨辉三角图形中，第行的数字有项；第行数字和为；第行的个数可表示为，是从个不同元素中取个元素的组合数；每个数字等于上一行的左右两个数字之和，即第行的第个数等于第行的第个数和第个数之和，其公式形成为。

利用Python实现杨辉三角输出的程序如下[6]：

输出结果如下：