高中数学基础：排列与组合

基本计数原理

（1）分类加法计数原理（分类相加）

做一件事情，完成它有$n$类办法，在第1类办法中有$m_1$中不同的方法，在第2类办法中有$m_2$中不同的方法······在第n类办法中有$m_n$中不同的方法。那么完成这件事情共有$N=m_1+m_2+···+m_n$种不同的方法。

（2）分类乘法计数原理（分步相乘）

做一件事情，完成它需要$n$个步骤，做第1个步骤中有$m_1$不同的方法，做第2个步骤中有$m_2$不同的方法······做第n个步骤有$m_n$中不同的方法。那么完成这件事情共有$N=m_1×m_2×···×m_n$种不同的方法。

排列与组合

排列

① 从$n$个不同元素中，任取$m(m≤n)$个元素，按照一定的顺序排成一列，叫做从$n$个不同元素中取出$m$个元素的一个排列。
② 从$n$个不同元素中，取出$m(m≤n$个元素的所有排列的个数，叫做从$n$个不同元素中取出$m$个元素的排列数，记作$A_n^m$。

组合

① 从$n$个不同元素中，任取$m(m≤n)$个元素并成一组，叫做从$n$个不同元素中取出$m$个元素的一个组合。
② 从$n$个不同元素中，取出$m(m≤n)$个元素的所有组合的个数，叫做从$n$个不同元素中取出$m$个元素的组合数，记作$C_n^m$。

排列数公式

$
A_n^m=n(n-1)(n-2)···(n-m+1)\
\,\,\,\,\,\,\,\,=\frac{n!}{(n-m)!}
$

$A_n^n=n!$，规定$0!=1$

组合数公式

$
C_n^m=\frac{n(n-1)(n-2)···(n-m+1)}{m!}\
\,\,\,\,\,\,\,\,=\frac{n!}{m!(n-m)!}
$

$C_n^n=Cn^{n-m}$，规定$C_n^0=1$

组合诱导公式

$Cn^m + C{n-1}^m = C_n^{m+1}$

$C_n^m + Cn^{m-1} = C{n+1}^m$

Python实现

# -*- coding: utf-8 -*-
import itertools

x = [1, 2, 3, 4, 5]
# 组合
c1 = itertools.combinations(x, 3)
print(list(c1))
# 排列
a1 = itertools.permutations(x, 3)
print(list(a1))

排列与组合的区别

排列有顺序，组合无顺序

排列与组合的联系

$A_n^m=C_n^m·A_m^m$

即排列就是先组合在全排列

排列与组合的两个性质

排列：$A_{n+1}^m=A_n^m+mAn^{m-1}$
组合：$C{n+1}^m=C_n^m+C_n^{m-1}$