计数原理

分类加法计数原理与分布乘法计数原理

分类加法计数原理

完成一件事有两类不同方案，在第1类方案中有 $m$ 种不同的方法，在第2类方案中有 $n$ 中不同的方法，那么完成这件事总共有 $N=m+n$ 种不同的方法。

要求：每一类中的任一种方法都可以完成要做的事

$N=m_1+m_2+\dots+m_n$

分布乘法计数原理

完成一件事需要两个步骤，第1步有 $m$ 种不同的方法，第2步有 $n$ 种不同的方法，那么完成这件事总共有 $N=m\times n$ 种不同的方法。

要求：依次完成各个步骤才能完成要做的事情

$N=m_1\times m_2 \times \dots \times m_n$

关键能力拓展

元素、位置选择法

在计数问题中常涉及元素与位置，解题时要分清楚要完成的事是元素选择位置还是位置选择元素

涂色问题

涂色问题是计数原理应用的典型问题，一般是指求用几种不同的颜色给已知图形的不同区域（或点）涂色，共有几种涂法的问题。

需要关注的图形特征：区域的个数、区域相邻情况

解决方案

选择正确的涂色顺序，一般从相邻区域最多的区域开始
根据涂色所用色数多少进行分类处理

树状图法

懂的都懂

正难则反

懂的都懂

建模法

根据具体问题，构造对应图形，直观地分析、解决较复杂问题的方法

排列与组合

排列

一般地，从 $n$ 个不同元素中取出 $m(m\leq n,n,m\in \mathbb{N}^*)$ 个元素，并按照一定的顺序排成一列，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个排列。

排列具有顺序性，当排列中的元素变换位置时，就算作不同的排列。

排列数

从 $n$ 个不同元素中取出 $m(m\leq n,n,m\in \mathbb{N}^*)$ 个元素的所有不同排列的个数，叫做从 $n$ 个不同的元素中取出 $m$ 个元素的排列数，用符号 $A_n^m$ 表示。

$A_n^m=n(n-1)(n-2)\dots(n-m+1),n,m\in\mathbb{N}^*,m\leq n$

全排列

特别地，我们把 $n$ 个不同元素全部取出的一个排列，叫做 $n$ 个元素的一个全排列，这时公式中 $m=n$ ，即

$A_n^n=n\times(n-1)\times(n-2)\times\dots\times2\times1=n!$

其中， $0!=1$

$A_n^m=\frac{n!}{(n-m)!}=\frac{A_n^n}{A_{n-m}^{n-m}}$

组合

一般地，从 $n$ 个不同的元素中取出 $m(m\leq n,n,m\in\mathbb{N}^*)$ 个元素作为一组，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个组合。

排列与组合的区别：有序排列，无序组合

组合数

从 $n$ 个不同的元素中取出 $m(m\leq n,n,m\in\mathbb{N}^*)$ 个元素的所有不同组合的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的组合数，用符号 $C_n^m$ 表示。

$C_n^m=\frac{A_n^m}{A_m^m}=\frac{n\cdot(n-1)\cdot(n-2)\cdot\dots\cdot(n-m+1)}{m\cdot(m-1)\cdot(m-2)\cdot\dots\cdot1}=\frac{n!}{m!(n-m)!}$

其中， $C_n^0=1$