组合数学入门笔记

发表于 更新于 分类于

来学组合数学！

加法及乘法原理

加法原理

完成一件事有 nn 类方法，每类方法有 mm 个不同的方法，那么完成这件事总共就有 N=m_1+m_2+...+m_nN=m\_{1}+m\_{2}+...+m\_{n} 种方法。

乘法原理

完成一件事有 nn 个步骤，每个步骤有 mm 个不同的方法，那么完成这件事总共就有 N=m_1×m_2×...×m_nN=m\_{1} \times m\_{2} \times ... \times m\_{n} 种方法。

排列与组合入门

排列与排列数

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

公式如下：

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

如何理解这个公式：

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

组合与组合数

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

公式如下：

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

如何理解这个公式：

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

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

特别地，当 m>nm>n 时，Am_n=Cm_n=0A^{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!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=1Cat\_{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=Cat_n−1(4n−2)n+1Cat\_{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=Cat_n−1(4n−2)n+1Cat\_{n}=\frac{Cat\_{n-1}\left ( 4n-2 \right )}{n+1} 很简单的写出来，这里就不放了。

应用

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

ok，有错误请 D 我。