一只蒟蒻的组合数学的入门笔记

发表于 更新于 分类于

加法及乘法原理

加法原理

完成一件事有 $n$ 类方法，每类方法有 $m$ 个不同的方法，那么完成这件事总共就有 $N=m_{1}+m_{2}+…+m_{n}$ 种方法。

乘法原理

完成一件事有 $n$ 个步骤，每个步骤有 $m$ 个不同的方法，那么完成这件事总共就有 $N=m_{1} \times m_{2} \times … \times m_{n}$ 种方法。

排列与组合入门

排列与排列数

在 $n$ 个元素中任取 $m$ （$m<=n$，$m,n \in N$）个元素，按照一定顺序排列，所有的情况的个数叫做 从 $n$ 个不同元素中取出 $m$ 个的排列数。

公式如下：

$ A^{m}_{n}=\left ( n-m+1 \right )…\left ( n-2 \right )\left ( n-1 \right )n=\frac{n!}{\left (n-m\right )!} $

如何理解这个公式：

有 $m$ 个位置，第一个有 $n$ 种选法，第二个有 $n-1$ 种，以此类推，第 $m$ 种有 1 种选法，所以由乘法原理可得总方案数为 $\left ( n-m+1 \right )…\left ( n-2 \right )\left ( n-1 \right )n$。

组合与组合数

在 $n$ 个元素中任取 $m$ （$m<=n$，$m,n \in N$）个元素，组成一个组合（集合），所有的情况的个数叫做 从 $n$ 个不同元素中取出 $m$ 个的组合数。

公式如下：

$C^{m}_{n}=\frac{A^{m}_{n}}{m!}=\frac{n!}{m!\left (n-m\right)!}$

如何理解这个公式：

一个 $m$ 个元素的序列的全排列的序列数为 $m!$，所以将排列数除去全排列的序列数就为组合数。

$C^{m}_{n}$ 还写成 $\begin{pmatrix}n \\m\end{pmatrix}$，组合数也叫二项式系数。

特别地，当 $m>n$ 时，$A^{m}_{n}=C^{m}_{n}=0$。

C++ 求组合数代码

递归：

1
2
3
4
5
6
7
8
9
10
11
const int N = 100005, MOD = 19260817;
int a[N], ans;
int C(int n, int m) 
{
	for (int i = n; i >= m; i--) 
	{
		if (m > 1) C(n - 1, m - 1);
		else ans = (ans + 1) % MOD;
	}
	return ans;
}

递推：

组合数满足以下递推式：

$\left\{\begin{matrix} C^{m}_{n}=C^{m-1}_{n}+C^{m-1}_{n-1},n>m>0\\C^{m}_{n}=1,m=0 或 n=m\end{matrix}\right.$

所以代码很容易打出来了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int N = 1005, MOD = 19260817;
int f[N][N];
int C(int n, int m) 
{
	if (n == 0 || m == n) return 1;
	for (int i = 0; i <= m; i++) 
	{
		for (int j = i + 1; j <= n; i++) 
		{
			if (i == 0)f[i][j] = 1;
			else f[i][j] = f[i - 1][j - 1] + f[i - 1][j];
		}
	}
	return f[m][n];
}

求排列数则只要
将组合数乘上 $m!$ 就好了。

二项式定理

公式如下：

$\left ( a+b \right )^{n}= {\textstyle \sum_{n}^{i=0}\begin{pmatrix}n \\i\end{pmatrix}a^{n-i}b^{i}}$

其实很好理解，自己手推一下就出来了。

Catalan（卡特兰）数列

没什么好说的，记个公式（要推导它的通项公式需要生成函数，反正本蒟蒻不会）。

$Cat_{0}=Cat_{1}=1$

$Cat_{n}=\frac{\begin{pmatrix}2n\\n\end{pmatrix}}{n+1}\left ( n\ge 2,n \in N^{+}\right )$

其他 Catalan 数列常用公式：

$Cat_{n}=\frac{Cat_{n-1}\left ( 4n-2 \right )}{n+1}$

$Cat_{n}=\begin{pmatrix} 2n\\n\end{pmatrix}-\begin{pmatrix} 2n\\n-1\end{pmatrix}$

$Cat_{n}=\left\{\begin{matrix}{\textstyle \sum_{i=1}^{n}Cat_{i-1}Cat_{n-i}},n\ge 2,n\in N^{+} \\1, n=0,1\end{matrix}\right.$

代码可以由 $Cat_{n}=\frac{Cat_{n-1}\left ( 4n-2 \right )}{n+1}$ 很简单的写出来，这里就不放了。

应用

  1. 对角线不相交，将一个凸多边形分成多个三角形的方案数。
  2. 一个序列的进栈顺序为 $1,2,3…,n-1,n$，求有几种不同的出栈序列。
  3. $n$ 个节点可以构成多少个不同的二叉树。
  4. 等等等等

ok，有错误请 D 我。