排列组合 排列组合是组合数学中的基础。排列就是指从给定个数的元素中取出指定个数的元素进行排序；组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。排列组合与古典概率论关系密切。
在高中初等数学中，排列组合多是利用列表、枚举等方法解题。
加法 & 乘法原理 加法原理 完成一个工程可以有 n a_i(1 \le i \le n) i S=a_1+a_2+\cdots +a_n
乘法原理 完成一个工程需要分 n a_i(1 \le i \le n) i S = a_1 \times a_2 \times \cdots \times a_n
排列与组合基础 排列数 从 n m m\leq n m n n m n m m\leq n n m \mathrm A_n^m \mathrm P_n^m
排列的计算公式如下：
\mathrm A_n^m = n(n-1)(n-2) \cdots (n-m+1) = \frac{n!}{(n - m)!} n! n 6! = 1 \times 2 \times 3 \times 4 \times 5 \times 6
公式可以这样理解： n m m \le n n n-1 m n-m+1
\mathrm A_n^m = n(n-1)(n-2) \cdots (n-m+1) = \frac{n!}{(n - m)!} 全排列： n n n n-1
\mathrm A_n^n = n(n-1)(n-2) \cdots 3 × 2 × 1 = n! 全排列是排列数的一个特殊情况。
组合数 从 n m m\leq n n m n m m\leq n n m \mathrm C_n^m
组合数计算公式
\mathrm C_n^m = \frac{\mathrm A_n^m}{m!} = \frac{n!}{m!(n - m)!} 如何理解上述公式？我们考虑 n m m \le n C_n^m A_n^m m A_n^m
\mathrm C_n^m \times m! = \mathrm A_n^m\\ \mathrm C_n^m = \frac{\mathrm A_n^m}{m!} = \frac{n!}{m!(n-m)!} 组合数也常用 \displaystyle \binom{n}{m} n m \displaystyle \mathrm C_n^m=\binom{n}{m} \displaystyle \binom{n}{m} \mathrm C_n^m
组合数也被称为「二项式系数」，下文二项式定理将会阐述其中的联系。
特别地，规定当 m>n \mathrm A_n^m=\mathrm C_n^m=0
二项式定理 在进入排列组合进阶篇之前，我们先介绍一个与组合数密切相关的定理——二项式定理。
二项式定理阐明了一个展开式的系数：
(a+b)^n=\sum_{i=0}^n\binom{n}{i}a^{n-i}b^i 证明可以采用数学归纳法，利用 \displaystyle \binom{n}{k}+\binom{n}{k-1}=\binom{n+1}{k}
二项式定理也可以很容易扩展为多项式的形式：
设 n 为正整数， x_i
(x_1 + x_2 + \cdots + x_t)^n = \sum_{满足 n_1 + \cdots + n_t=n 的非负整数解} \binom{n}{n_1n_2\cdots n_t} x_1^{n_1}x_2^{n_2}\cdots x_t^{n_t} 满 足 的 非 负 整 数 解 其中的 \binom{n}{n_1,n_2,\cdots ,n_t}
\sum{\binom{n}{n_1n_2\cdots n_t}} = t^n 排列与组合进阶篇 接下来我们介绍一些排列组合的变种。
多重集的排列数 | 多重组合数 请大家一定要区分 多重组合数 与 多重集的组合数 ！两者是完全不同的概念！
多重集是指包含重复元素的广义集合。设 S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k,\} n_1 a_1 n_2 a_2 n_k a_k S
\frac{n!}{\prod_{i=1}^kn_i!}=\frac{n!}{n_1!n_2!\cdots n_k!} 相当于把相同元素的排列数除掉了。具体地，你可以认为你有 k n_1,n_2,\cdots,n_k n=n_1+n_2+\ldots+n_k n 多重集的排列数 。多重集的排列数常被称作 多重组合数 。我们可以用多重组合数的符号表示上式：
\binom{n}{n_1,n_2,\cdots,n_k}=\frac{n!}{\prod_{i=1}^kn_i!} 可以看出， \displaystyle \binom{n}{m} \displaystyle \binom{n}{m,n-m}
多重集的组合数 1 设 S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k,\} n_1 a_1 n_2 a_2 n_k a_k r(r<n_i,\forall i\in[1,k]) S r 多重集的组合数 。这个问题等价于 x_1+x_2+\cdots+x_k=r
多重集的组合数 2 考虑这个问题：设 S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k,\} n_1 a_1 n_2 a_2 n_k a_k r S r
这样就限制了每种元素的取的个数。同样的，我们可以把这个问题转化为带限制的线性方程求解：
\forall i\in [1,k],\ x_i\le n_i,\ \sum_{i=1}^kx_i=r 于是很自然地想到了容斥原理。容斥的模型如下：
全集： \displaystyle \sum_{i=1}^kx_i=r 属性： x_i\le n_i 于是设满足属性 i S_i \overline{S_i} i x_i\ge n_i+1
\left|\bigcap_{i=1}^kS_i\right|=|U|-\left|\bigcup_{i=1}^k\overline{S_i}\right| 根据容斥原理，有：
\begin{aligned} \left|\bigcup_{i=1}^k\overline{S_i}\right| =&\sum_i\left|\overline{S_i}\right| -\sum_{i,j}\left|\overline{S_i}\cap\overline{S_j}\right| +\sum_{i,j,k}\left|\overline{S_i}\cap\overline{S_j}\cap\overline{S_k}\right| -\cdots\\ &+(-1)^{k-1}\left|\bigcap_{i=1}^k\overline{S_i}\right|\\ =&\sum_i\binom{k+r-n_i-2}{k-1} -\sum_{i,j}\binom{k+r-n_i-n_j-3}{k-1}+\sum_{i,j,k}\binom{k+r-n_i-n_j-n_k-4}{k-1} -\cdots\\ &+(-1)^{k-1}\binom{k+r-\sum_{i=1}^kn_i-k-1}{k-1} \end{aligned} 拿全集 \displaystyle |U|=\binom{k+r-1}{k-1}
Ans=\sum_{p=0}^k(-1)^p\sum_{A}\binom{k+r-1-\sum_{A} n_{A_i}-p}{k-1} 其中 A 是充当枚举子集的作用，满足 |A|=p,\ A_i<A_{i+1}
不相邻的排列 1 \sim n n k k \displaystyle \binom {n-k+1}{k}
错位排列 我们把错位排列问题具体化，考虑这样一个问题：
n 1,2,3,4,5 1,2,3,4,5
假设我们考虑到第 n n n
前面 n-1 前面 n-1 对于第一种情况，前面 n-1 n-1 n f(n-1)\times (n-1)
对于第二种情况，前面 n-1 n-1 n
其他情况，我们不可能通过一次操作来把它变成一个长度为 n
于是可得错位排列的递推式为 f(n)=(n-1)(f(n-1)+f(n-2))
错位排列数列的前几项为 0,1,2,9,44,265
圆排列 n \mathrm Q_n^n
\mathrm Q_n^n \times n = \mathrm A_n^n \Longrightarrow \mathrm Q_n = \frac{\mathrm A_n^n}{n} = (n-1)! 由此可知部分圆排列的公式：
\mathrm Q_n^r = \frac{\mathrm A_n^r}{r} = \frac{n!}{r \times (n-r)!} 组合数性质 | 二项式推论 由于组合数在 OI 中十分重要，因此在此介绍一些组合数的性质。
\binom{n}{m}=\binom{n}{n-m}\tag{1} 相当于将选出的集合对全集取补集，故数值不变。（对称性）
\binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}\tag{2} 由定义导出的递推式。
\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}\tag{3} 组合数的递推式（杨辉三角的公式表达）。我们可以利用这个式子，在 O(n^2)
\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=\sum_{i=0}^n\binom{n}{i}=2^n\tag{4} 这是二项式定理的特殊情况。取 a=b=1
\sum_{i=0}^n(-1)^i\binom{n}{i}=[n=0]\tag{5} 二项式定理的另一种特殊情况，可取 a=1, b=-1 n=0 1
\sum_{i=0}^m \binom{n}{i}\binom{m}{m-i} = \binom{m+n}{m}\ \ \ (n \geq m)\tag{6} 拆组合数的式子，在处理某些数据结构题时会用到。
\sum_{i=0}^n\binom{n}{i}^2=\binom{2n}{n}\tag{7} 这是 (6) n=m
\sum_{i=0}^ni\binom{n}{i}=n2^{n-1}\tag{8} 带权和的一个式子，通过对 (3)
\sum_{i=0}^ni^2\binom{n}{i}=n(n+1)2^{n-2}\tag{9} 与上式类似，可以通过对多项式函数求导证明。
\sum_{l=0}^n\binom{l}{k} = \binom{n+1}{k+1}\tag{10} 可以通过组合意义证明，在恒等式证明中较常用。
\binom{n}{r}\binom{r}{k} = \binom{n}{k}\binom{n-k}{r-k}\tag{11} 通过定义可以证明。
\sum_{i=0}^n\binom{n-i}{i}=F_{n+1}\tag{12} 其中 F
\sum_{l=0}^n \binom{l}{k} = \binom{n+1}{k+1}\tag{13} 通过组合分析——考虑 S={a_1, a_2, \cdots, a_{n+1}} k+1
build Last update and/or translate time of this articleCheck the history edit Found smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github people Contributor of this article OI-wiki translate Translator of this article Visit the original article! copyright The article is available under CC BY-SA 4.0 & SATA