加法原理

今天您想给orz做一道题。

您有10道数学题，5道物理题，5道oi题，这些题orz都不会做。

可惜您只能用其中一道题来考orz. 请问您有多少种方法让orz爆零？

10+5+5 = 20

假设您有很多种手段，使用每种手段都可以达成目标。

那么：每种手段的方法数之和，就是达成目标的方法数。

乘法原理

今天您想给orz做三道题：数学、物理、oi各一题。

您有10道数学题，5道物理题，5道oi题，这些题orz都不会做。

您只能在每个科目选一道题来考orz.需要让orz三道题都不会。

请问您有多少种方法让orz爆零？

10*5*5=250

如果您为了达成目标，需要几个步骤，所有的步骤都需要完成，目标才能达成。

那么完成目标的方法数是：各步骤方法数的乘积。

 排列与组合

我们再考虑另一个问题：

有甲乙丙丁戊共5个神仙，你要从中选出三个神仙排成一排。

有多少种方法？

第一位：5种

第二位：4种

第三位：3种

记为=n!/(n-m)!

排列数

从5个女生和7个男生中，选出3个女生和3个男生排成一排。 女生站在一起，男生站在一起，且女生排在男生前面。

有多少种方法？

现在我们考虑另一个问题。

放鸽子：一共有3只鸽子，你要从中选出2只放飞。不关心选择的顺序，只关心选了哪些鸽子。

没有发现这个柿子，表示的就是杨辉三角？

        0 1 2 3 4

C0: 1

C1: 1 1

C2: 1 2 1

C3: 1 3 3 1

C4: 1 4 6 4 1

递推求组合数

其他排列组合

//☝证明来自：不尽相异元素的全排列问题

生成算法

现在已经存在很多种全排列算法，例如字典序算法、递增进位制算法、递减进位制算法、邻位对换法。这里介绍一下圆排列生成的算法。我们不妨用1、2、…、n来表示n个元素

对于，圆排列仅有一种。

对于，假设我们已经得到了n-1时的圆排列，我们由此序列来生成n的圆排列。

假设为n-1时的其中一个圆排列，那么我们可以将n分别插入到后，由此生成新的n-1种排列

……

对个圆排列均进行此操作，即可生成一组新的一组排列，此排列即为n时的圆排列。

算法证明

首先我们由上述算法能够得到，对于n，我们生成的排列有种排列。与圆排列的个数相等，下面我们只需要证明这个排列无重复即可。首先我们由上述构造方法可知，一定为每个圆排列的头。

下用数学归纳法证明：

1. 对于n=1，2，3时，无重复成立。

2. 假设对于n-1时，无重复成立。

3. 对于n时：

由构造方式可知，n是采取插入的方式，故由生成的n-1个序列中，n左右的两个元素均不相同。故生成的n-1个序列两两不同。

下证由不同圆排列生成的序列无重复。因为一定为每个圆排列的头，所以若两个序列重复，它们一定是完全相同的序列。(例如123 231 312为同一组圆排列，但是由于1一定为头，所以不可能出现后两种情况)

假设序列与序列重复，由上述可知：

我们去除n后得到n-1的圆排列序列，但是对于n-1，无重复序列，故矛盾。即对于n时生成的算法无重复。

即证。

举例

把n个有标号的珠子排成一个圆圈，共有多少种不同的排法？

解：这是典型的圆排列问题。对于围成圆圈的n个元素，同时按同一方向旋转，即每个元素都向左(或向右)转动一个位置，虽然元素的绝对位置发生了变化，但相对位置未变，即元素间的相邻关系未变，这样的圆排列认为是同一种，否则便是不同的圆排列。下面从三种角度推导圆排列数的计算公式。

方法一：

先令n个相异元素任意排成一行(称为线排列)，共有n!种排法，再将其首尾相接围成一圈，当圆转动一个角度时，对应另一个线排列，当每个元素又转回到原先的位置时，相当于n个不同的线排列，故圆排列数为

方法二：

先取出某一个元素k，放于圆上某确定位置，再令余下的n-1个元素作成一个线排列，首尾置于k的两侧构成一个圆排列同样可得到

方法三：

⊙x₁x₂…xk，⊙x₂x₃…x_kx₁,…，⊙x_kx₁…x_k-1都表示同一环状字，所以⊙x₁x₂…x_k=⊙x₂x₃…x_kx₁=…=⊙x_kx₁…x_k-1，有n个这样的等式，其排列数为

//以上来自：百度百科“圆排列”

证明一：（来自：360问答）

证明二：（来自：360百科）

排列组合常用技巧

捆绑法

有8个讲师，需要排成一排。zro和orz需要站在一起。（只需要站在一起，谁站在前面都行）,有多少种方案？

隔板法

8个讲师要站成一排，但是当局禁止zro和orz站在一起,问方案数。

我们考虑将剩下的6个讲师先排成一排。于是出现了7个空位。

我们把zro和orz放在这7个空位里的2个就行了！

 二项式定理

将这里的视作当x=y=1时，(x+y)^10中x^10的系数，那么其余的也同理，所以上式=(1+1)^10=2^10=1024

【例 1】「NOIP2011」计算系数（信息学奥赛一本通 1648）

【题目描述】

给定一个多项式 (ax+by)k ，请求出多项式展开后 xnym （n+m=k）项的系数。

【输入】

输入共一行，包含 5个整数，分别为 a,b,k,n,m ，每两个整数之间用一个空格隔开。

【输出】

输出共 1行，包含一个整数，表示所求的系数，这个系数可能很大，输出对 10,007 取模后的结果。

【输入样例】

1 1 3 1 2

【输出样例】

3

 求组合数的常规方法

//上图来自：冯志刚《初等数论》P37

组合（信息学奥赛一本通 1650）

【题目描述】

给出组合数 C(n,m) 表示从 n 个元素中选出 m 个元素的方案数。例如 C(5,2)=10,C(4,2)=6。可是当 n,m 比较大的时候，C(n,m)  很大。于是 xiaobo 希望你输出 C(n,m) mod p 的值。 【输入】

输入数据第一行是一个正整数 T，表示数据组数； 接下来是 T 组数据，每组数据有 3个正整数 n,m,p。

【输出】

对于每组数据，输出一个正整数，表示 C(n,m) mod p 的结果。

【输入样例】

2

5 2 3

5 2 61

【输出样例】

1 10

中国剩余定理

其中m1,m2,m3…mk 为两两互质的整数求x的最小非负整数解.

现在已知一个数为C(n,m)=(M*t+x)%M 求x。M=m1*m2*…*mk, mi为质数

用中国剩余定理求得的最小非负整数解即为所求x。

例题：古代猪文

 卡特兰数