本文介绍的内容是关于组合数学和概率方面的一些内容，提到组合数学，大家可能多多少少都有一些印象或者基础，高中的时候也应该练习过不少组合数学相关的题目，当然，如果往深了追究，组合数学包含的内容远不是这一篇文章可以说清楚的，本文意在帮助大家复习或者学习在ACM竞赛中，我们经常会遇到的组合数学问题和对应的解法。

加法原理是分类计数原理，常用于排列组合中，具体是指：做一件事情，完成它有n类方式，第一类方式有M1种方法，第二类方式有M2种方法，……，第n类方式有Mn种方法，那么完成这件事情共有M1+M2+……+Mn种方法。

举个简单的例子：从武汉到上海有乘火车、飞机、轮船3种交通方式可供选择，而火车、飞机、轮船分别有k1，k2，k3个班次，那么从武汉到上海共有 k1+k2+k3种方式可以到达。

做一件事，完成它需要分成n个步骤，做第一 步有m1种不同的方法，做第二步有m2种不同的方法，……，做第n步有mn种不同的方法。那么完成这件事共有 N=m1×m2×m3×…×mn 种不同的方法。 和加法原理是数学概率方面的基本原理。

同样我们也用一个例子来说明这个问题，从武汉到上海我们要先坐火车到北京，再从北京坐飞机到深圳，最后从深圳坐轮船到上海，而火车、飞机、轮船分别有k1，k2，k3个班次，那么从武汉到上海共有 k1* k2*k3种方式可以到达。

他们之间最大的区别就是，加法原理解决的是分类问题，乘法原理解决的是分步问题。

排列（permutation）从n个不同元素中每次取出m（1≤m≤n）个不同元素，排成一列，称为从n个元素中取出m个元素的无重复排列或直线排列，简称排列。从n个不同元素中取出m个不同元素的所有不同排列的个数称为排列种数或称排列数，用符号记为A。运算公式如下 A n m = n ! ( n − m ) ! = n ∗ ( n − 1 ) ∗ . . . ∗ ( n − m + 1 ) A_n^m=\frac{n!}{(n-m)!}=n*(n-1)*...*(n-m+1) Anm​=(n−m)!n!​=n∗(n−1)∗...∗(n−m+1) 组合（combination），数学的重要概念之一。从n个不同元素中每次取出m个不同元素（0≤m≤n），不管其顺序合成一组，称为从n个元素中不重复地选取m个元素的一个组合。所有这样的组合的总数称为组合数，这个组合数用符号记为C，运算公式如下 C n m = n ! m ! ( n − m ) ! = n ∗ ( n − 1 ) ∗ . . . ∗ ( n − m + 1 ) m ∗ ( m − 1 ) ∗ . . . ∗ 2 ∗ 1 C_n^m=\frac{n!}{m!(n-m)!}=\frac{n*(n-1)*...*(n-m+1)}{m*(m-1)*...*2*1} Cnm​=m!(n−m)!n!​=m∗(m−1)∗...∗2∗1n∗(n−1)∗...∗(n−m+1)​

A n m = n A n − 1 m − 1 A_n^m=nA_{n-1}^{m-1} Anm​=nAn−1m−1​

这个性质就可以理解为我们先把某个特定位置安排好数，在对其他位置进行排列 C n m = C n n − m C n m = C n − 1 m + C n − 1 m − 1 C n 0 + C n 1 + C n 2 + . . . + C n n = 2 n C_n^m=C_{n}^{n-m}\\ C_n^m=C_{n-1}^{m}+C_{n-1}^{m-1}\\ C_n^0+C_n^1+C_n^2+...+C_n^n=2^n Cnm​=Cnn−m​Cnm​=Cn−1m​+Cn−1m−1​Cn0​+Cn1​+Cn2​+...+Cnn​=2n 分别来简单理解或者证明一下这几个性质，首先对于性质1，我们直接从定义出发，每次我们从n中选m个元素组成一个集合的同时，剩余元素也自动组成了一个组合，这二个集合一一对应。所以性质1成立。对第二个性质，我们可以把问题看作从n个不同元素中取出m个元素分为2类，一个是选择n号元素，一个是不选择n号元素。如果选择n号元素。剩下的部分只需要在n-1个元素中选择m-1个元素即可。如果不选择n号元素，就需要从n-1个元素中选择m个元素。因为这是分类问题，根据加法原理，性质二也成立。性质三就是从n个元素中选择若干个元素组成1个集合，一共有n+1种方法。也就是从n中取出0，1…n个元素。换个角度来想，对于n个元素，我们看作每个元素可以选也可以不选2种状态，也就是二进制组成它的所有选择情况，两种方法得到的值应该相等，所以性质三正确。

提到排列我们就顺便介绍一下排列的特殊情况，全排列。从n个元素中取出n个元素排列。排列方法一共有n!种。在algorithm库中我们可以调用函数

next_permutation() 函数，自动产生当前某数组的下一种全排列的方式。