排列组合

闲言

昨天晚上在宿舍睡觉的时候，问 (hxk) ,你不会不组合数学，他说会，我说：速教我。他 (TM) 说，你也配， (MD) , 这个 (ZZ) ,

入门

我相信，学排列组合的话，高中选择性必修二很显然是不错的。

加法 & 乘法原理

加法原理
在完成一件事情有 (n) 种方法，(a_i) 表示第 (i) 中方法的数目，那么总方法就有：(S = sum_{i = 1}^{n} a_i)
乘法原理
在完成一件事情有 (n) 个步骤， (a_i) 表示第 (i) 个步骤的不同方法的数目，则总方法有：
(S = prod_{i=1}^{n}a_i)

排列数

从 (n) 个不同的元素中依次取出 (m) 个元素排成一列，产生的不同排列的数目为：
(A_{n}^{m} = frac{n!}{(n-m)!} = n imes (n - 1) imes … imes (n - m + 1))

证明：我依稀记得吧，当选择第 (1) 个元素的时候，我们有 (n) 的数目， (2) 个元素的时候，有 (n - 1) 的数目，一直到 (m) 个元素的时候，我们用 (n - m + 1) 的数目选择。根据乘法原理，就可以知道了。

组合数

从 (n) 个不同元素中取出 (m) 个数组成一个集合(不考虑顺序) ，产生的不同集合数目为：
(C_{n}^{m} = frac{n!}{m!(n - m)!} = frac{n imes (n - 1) imes … imes (n - m + 1)}{m imes (m - 1) imes … imes 2 imes 1})

如何理解上述式子：选出 (m) 个人来，不排队，不在乎顺序。如果在乎顺序的话，就是 (A_{n}^{m}) ，那么重复了 (m)了，同样让 (m) 个人排列，保证最后是不重复的。

现在数学中常用： (displaystyle inom{n}{m}) 代替 (C_{n} ^{m})

性质：

(1. C_{n}^{m} = C_{n}^{n - m})

由组合数的定义，对于从 (n) 个不同元素中取出 (m) 个组成的每个集合，剩余未取出的元素也构成一节集合，两个集合一一对应，所以性质1成立。

$2. C_{n}^{m} = C_{n - 1}^{m} + C_{n - 1}^{m - 1} $

从 (n) 个不同元素中取出 (m) 个组成的一个集合有两种方法：取 (n)浩元素，不取 (n) 号元素，若取 (n) 号元素，则应在剩余的 (n - 1) 个中选择 (m - 1) , 则方案数为 (C_{n - 1}^{m - 1}) ，若不取 (n) 号元素，则应在剩余的 (n - 1) 个数中选择 (m) 个数，即为 (C_{n - 1}^{m}) ，综上，性质二成立。

(3. sum_{i = 0}^{n}C_{n}^{i} = 2^n)

从 (n) 个元素中取出若干个元素组成一个集合，有 (n + 1) 中方法，分别是取出 (0 , 1 , 2 … n) 个。根绝加法原理，共有 (C_{n}^{0} + C_{n}^{1} + C_{n}^{2} … + C_{n}^{n}) 。同样的，每一个元素都对应着选或者不选，那么根据乘法原理，就得知 (2^n) ，都是代表的同样的，所以综上，性质三成立

求解组合数的方法：

(1.) 根据性质二，我们很显然的可以得出一种思路，那就递推求解，递推式是杨辉三角的递推式 (f_{i,j} = f_{i-1,j} + f_{i-1 , j-1}) , 但是这种的复杂度是 (O(n^2)) 的，很显然不是那么优秀。
一般由于组合数都比较大，从而要求 (mod) ，这种时候，我们就可以 $n! mod $ , 然后又因为 (1 ext{~} p) 满足存在逆元，其对 (/(n - m) !) 就直接用逆元解决掉。，进行一下预处理就好。

大概是： (C_{n}^{m} ext{%} p= f_n imes finv_{m} imes finv_{n-m})

关于求解逆元的方法的方法，这里就不再赘述了。

二次项定理

[(a + b) ^ n = sum_{i = 0}^{n} inom{n}{i}a^{n - i} b^i ]

证明：咕了。

例题：计算系数 Code

进阶

略微难一些。

Lucas 定理

若 (p) 为质数，则对于任意整数 (1 leq m leq n) 有：

[displaystyle C_{n}^{m} = C_{n ext{%} p}^{m ext{%} p} imes C_{n / p}^{m / p} (mod p) ]

如何理解这个式子

就是把 (n,m) 全部转化成 (p) 进制数，对 (p) 进制下的每一位分别记录组合数，最后再乘起来。

证明的话，一般用到生成函数知识，不涉及。

inline void init() 
{
	f[0] = 1 ; 
	for(qwq int i = 1 ; i <= p ; i++) f[i] = (f[i - 1] * i) % p ;
}
inline int powe(int k , int b , int mod) 
{
	int ret = 1 ; 
	while(b) 
	{
		if(b & 1) ret = ret * k % mod ; 
		k = k * k % mod; 
		b >>= 1 ; 
	}
	return ret % mod; 
}
inline int calc(int n , int m) 
{
	if(m > n) return 0 ; 
	return (( f[n] * powe(f[m] , p - 2 , p) ) % p * powe(f[n - m] , p - 2 , p) ) % p ;  
}
inline int Lucas(int n , int m)
{
	if(!m) return 1 ; 
	return calc(n % p , m % p) * Lucas(n / p , m / p ) % p ;
}
signed main()
{
	int T = read() ; 
	while(T--) 
	{
		n = read() , m = read() , p = read() ; 
		init() ; 
		printf("%lld
" , Lucas(n + m , m)) ; 
	}
	return 0 ;
}

多重集的排列数 | 组合数

多重集：指包含重复元素的集合，即为 (S = {n_1 imes a_1 , n_2 imes a_2 … n_k imes a_k})
其中表示为含有 (n_1) 个 (a_1) ， (n_2) 个 (a_2) …… (n_k) 个 (a_k) 的集合。

(S) 的全排列个数为 $displaystyle frac{(sum_{i=1}^{{k}n)!}{prod_{k}}{i = 1} n_i} $ .

说明：
主要想法就是去掉重复的元素，(sum = sum_{i = 1}^{k} n_i) 中有 (k) 种不一样的球。这 (sum) 个球的全排列就是多重集的排列数。

在这 (sum) 个元素中取出 (m) 个元素形成一个多重集(无序)，产生的不同的多重集的组合数量为

[displaystyle C_{k + m - 1}^{k - 1} ]

证明：
咕了，是我菜了，没证明出来

不相邻的排列

(1 ext{~}n) 的自然数内，取出 (m) 个数，这 (m) 个数都不相邻的组合有 (C_{n - m + 1}^{m}) 种

错位排列

根据 (OI-WIKI) 提供的思路，我们将其转化为实质化的题目：现在有 (n) 个邮箱和 (n) 个信件，求解信件的编号不能和邮箱一样的组合数。

现在考虑放第 (n) 个信件

前 (n - 1) 个信件全部都被装错了
前 (n - 1) 个信件有一个没装错，其余全部装错了。

对于前面已经全部装错的，我们将当前的 (n) 这个信件随便插入到 (n - 1) 的一个范围就行，因为前面 (n - 1) 的信件不可能属于第 (n) 个邮箱，所以就有 (n - 1) 种情况。

对于第二种情况：这就像是走楼梯的递推式一样，可以一次性走一步，其他的步数都是可以拼凑出来的，就像是 (n - 1) 的前面一样可能也是有一个信件的，综上，就是爬楼梯的递推式， (f_{i} = f_{i -1} + f_{i - 2})

所以, 综上， (f_i = (i - 1) imes (f_{i - 1} + f_{i - 2}))

圆排列

暂且咕了