【数论系列】计数原理与排列组合（鸽巢与容斥）

（1）C(n,0) = C(n,n) = 1

（2）C(n,k) = C(n,n-k)

（3）递推公式1：C(n,k) = C(n-1,k) + C(n-1,k-1)

（4）递推公式2：C(n,k) = (n-k+1)/k*C(n,k-1)

（5）计算公式：C(n,k) = n!/k!*(n-k)!

（6）求和公式1：C(n,0) + C(n,1) + C(n,2) + …… + C(n,n) = 2^n

（7）求和公式2：0C(n,0) + 1C(n,1) + 2C(n,2) + ….. + nC(n,n) = n*2^(n-1)

（8）求和公式3： $0^{2}C(n,0) + 1^{2}C(n,1) + 2^{2}C(n,2) + ...... + n^{2}C(n,n) = n(n+1)2^{n-2}$

（9）求和公式4： $C(n,0)^{2} + C(n,1)^{2} + C(n,2)^{2} + ..... + C(n,n)^{2} = C(2n,n)$

4. 容斥原理

（1）基本概念

在计数时，必须注意没有重复，没有遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法。这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复。这种计数的方法称为容斥原理。

注意：组合数学问题中，正面解决会困难，常用方法是正难则反，使用容斥原理求反向在用全集减去，将对立面的限制条件分析清楚。

（2）三个集合的容斥原理

设A, B, C是三个有限集合，则 |A + B + C| = |A| + |B| + |C| – |AB| – |AC| – |BC| + |ABC|，其示意图如下所示：

（3）容斥原理使用特征

问题可以分解为集合性质，或者与集合有关

问题有明显的约束条件，或从反面考虑约束较为简单

每一个约束条件或者反面条件考虑为一个集合的特性，然后从全集里面减去这些集合的交并关系得到答案

5. 鸽巢原理（抽屉原理）

基本性质：

把n+1个东西放到n个抽屉里，则必有一个抽屉里面有两个

把多于m*n+1个物品放到n个抽屉里面，则必有一个抽屉里面有不少于（m+1）个物品

把无穷多个物品放入到n个抽屉里面，则至少有一个抽屉里面有无穷个物品

把m*n-1个物品放入n个抽屉里面，则必有一个抽屉里至多有（m-1）个物品

该原理的作用是常用来证明存在性问题。

二. 常见的计数问题

1. 无重复的排列问题

Problem Description

在n个不同的数字里面选择m个排成一列，每个数字仅有一个，有多少种方案？

答案是 C(n,m)*m! = n!/(n-m)!；特别的，当n==m时，答案为n!

2. 无重复的组合问题

Problem Description

在n个不同数字里面选择m个（与顺序无关），每个数字仅有一个，有多少种方案？

答案是 C(n,m) = n!/m!*(n-m)!

3. 有重复的全排列问题

Problem Description

有k个元素，第i个元素有ni个（n1+n2+n3+….+nk = n），求全排列个数。

设全排列个数为x，由于 n1!*n2!*n3!*….*nk!*x = n!，则 x = n!/(n1!*n2!*n3!*….*nk!)

4. 有重复的组合问题

Problem Description

有n个不同的元素，每个元素可以选择多次，一共要选k个，问有多少种方法。

假设第i个元素取xi次，则有方程：x1 + x2 + x3 + …. + xn = k；

即：(x1 + 1) + (x2 + 1) + …. + (xn + 1) = k + n；

即：y1 + y2 + y3 + ….. + yn = k+n；

等价于：求该方程有多少个y1~yn的解

等价于：把k+n个1分成n份，也就是在k+n个1里面插入n-1个隔板（不能包括首尾，因为yn = xn+1>=1）

因此：答案为 C(k+n-1,n-1) = C(k+n-1,k)

5. 有重复元素的排列问题

Problem Description

从n个不同元素中取m个元素(同一元素允许重复取出)，按照一定的顺序排成一列，叫做从n个不同元素中取m个元素的可重复排列，问排列个数

答案是这种排列的个数为n^m

6. 多组合问题

Problem Description

把n个元素，按照一定顺序分为k组，要求第i组有ni个元素（n1 + n2 + … + nk=n），问有多少种分法

因为有顺序分组：

答案 = C(n,n1) *C(n-n1,n2)*C(n-n1-n2,n3)*…..*C(n-n1-n2-…-nk-1,nk)

= $\frac{n!}{n1!*(n-n1)!} * \frac{(n-n1)!}{n2!*(n-n1-n2)!} * .......*\frac{(n-n1-n2-...-n(k-1)!}{nk!*(n-n1-n2-....-nk)!}$

= $\frac{n!}{n1!*n2!*n3*....*nk!}$

注意：当k组无先后顺序时，答案 = $\frac{n!}{n1!*n2!*n3!*.....*nk!*k!}$

7. 一元不定方程的非负整数解的个数

x1 + x2 + x3 + …… + xn = m的解的个数为：C(m+n-1,m)

8. 单色三角形模型

Problem Description

给定空间n个点，其中没有三点共线，每两点之间都有一条线段连接，线段为黑色或者红色，给定每个点所连接的黑色线段条数ai,求能组成的三条边同色的三角形的个数。

每个点连接着n-1条线段，若有ai条黑色线段，则有n-1-ai条红色线段。若直接考虑同色，则枚举三个点，时间复杂度O(n^3)；若从反面来考虑，n个点一共能组成C(n,3)个三角形。如果我们求出了异色三角形的个数，那么就相当于间接求出了同色三角形的个数。

在一个异色三角形中，无非是两红一黑或者是两黑一红，但是不论哪一种情况，总有两个点一端连接黑色，一端连接红色。所以要想构成一个异色三角形，只要有一个点同时连接两个不同颜色边即可。所以对于一个点i，有ai*(n-1-ai)个异色三角形，但是总的来看时，每个三角形被考虑了两次，因此最终结果因应该除以2。

最终答案即： $_{n}^{3}\textrm{C} - \frac{1}{2}*\sum ai*(n-1-ai)$

9. 错排问题

Problem Description

某人写了n封信，这里有n个信封，要求第i封信不能装在第i个信封里面，求全错排的情况数目有多少。

假设错排x封信有D(X)种情况。这里先放第一封信，这封信不能放在第一个信封，只有(n-1)个位置可以放，假如它放在第k个位置；那么接下来要排第k封信放在哪，这里有两种情况：

（1）若第k封信放在第一封信的位置，相当于两封信互换了位置，取余n-2个元素未该变，所以接下来相当于错排n-2个元素，有D(n-2)种情况

（2）若第k封信没有放在第一封信的位置，可以先把第k封信的位置剔除掉（第一封已经错排了），然后把第一封信的位置看作第k封信本应在的地方，那么就是剩下的n-1个元素错排，有D(n-1)种情况

综上所述：根据加法原理与乘法原理有错排公式：D(n) = (n-1)*(D(n-1) + D(n-2))，特别有 D(1) = 0，D(2) = 1；

三. 例题分析

1. UVA11538 Chess Queen

Problem Description

在n行m列的棋盘上，防止两个能够相互攻击的皇后，皇后能互相攻击的条件是，位于同一行同一列或者对角线上，问有多少种放置方法？

（1）先分析一行上的：C(n,1)*C(m,2) = m*n*(m-1)/2*2！

（2）再分析一列上的：C(m,1)*C(n,2) = m*n*(n-1)/2*2！

（3）再分析对角线上的：假设n<=m，我们知道一个长为n的对角线，要占据n行n列，所以在n<=m的条件下，我们能达到的最大的对角线就是占据n个格子。m每比n多1，就可以将该对角线右移一位，得到一个新的占据n格子的对角线；所以长为n的对角线有：m – n + 1；故n*m的棋盘对角线变化为：1，2，3……n，n，n…(m-n+1个)，(n-1)，…….3，2，1；故一条对角线上的情况为：2* $\sum$ C(i,2)*2！(1<=i<=n-1) + (m-n+1)*C(n,2)*2！；存在两条对角线，故上述结果应该再*2；

故最终答案 = m*n*(m + n – 2) +2*2* $\sum i*(i-1)$ + 2*(m – n + 1)*n*(n-1) = m*n*(m + n – 2) + 4*sum(i*i) – 4*sum(i) + 2*(m-n+1)*n*(n-1)；已知平方和公式如下：

所以最终答案 = m*n*(m + n – 2) +2* n(n-1)*(2*n – 1)/3 – 2*n*(n-1) + 2*n*(n-1)*(m-n+1) = m*n*(m + n – 2) + 2*n*(n-1)*(3*m -n – 1)/3；若n > m，则相当于把m和n换一下考虑即可。

#include <iostream> #include<bits/stdc++.h> using namespace std; typedef unsigned long long int LLU; int main() { LLU n,m; while(scanf("%llu%llu",&n,&m)!=EOF&&(n||m)){ if(n > m)swap(n,m); //cout<<n<<" "<<m<<endl; printf("%llu\n",m*n*(m + n - 2) + 2*n*(n-1)*(3*m - n - 1)/3); } return 0; }

2. UVA11401 数三角形

Problem Description

给你n，问你从1~n可以选出多少组三个不同的整数构成三角形？

假设最大边长为x的三角形个数为C(x)，假设其他两边为y、z；则由构成三角形条件可知： y + z > x，则z 的范围为 x – y< z < ｘ。

当y为1时：0个解；

当y为2时：z = x – 1，一个解；

………

当y为x-1时：z 有x – 2个解；

所以：总的 = 0 + 1 + 2 + 3 + ….. + (x-2) = (x-1)*(x-2)/2；

但是这样计算中包括了y = z的情况而且每个三角形算了两次比如3、4、5就一定有4、3、5；y==z时y从x/2 + 1开始到x-1共（x-1）/2个解。所以最终答案C(x) = ((x-1)*(x-2)/2 – (x-1)/2)/2；故f(x) = f(x-1) + C(x)

#include <iostream> #include<bits/stdc++.h> using namespace std; typedef long long int LL; const int maxn =  + 7; LL Triangle[maxn]; void init(){ Triangle[3] = 0; for(LL i = 4;i<maxn;i++){ Triangle[i] = Triangle[i-1] + ((i-1)*(i-2)/2 - (i-1)/2)/2; } } int main() { int n; init(); while(scanf("%d",&n)!=EOF){ if(n<3)break; printf("%lld\n",Triangle[n]); } return 0; }

3. UVA11806 拉拉队

Problem Description

有m*n的棋盘，放k个相同的石子，要求第一行第一列最后一行最后一列都得有石子，有多少种方法？

若直接考虑，第一行第一列放一个石子就能同时满足两个条件，考虑起来很麻烦。可以正难则反：若求第一行第一列最后一行最后一列都没有石子，那么答案 = C((m-2)*(n-2),k)；若求第一行或第一列或最后一行或最后一列没有石子，答案也很好求，去掉这一行/列组合数即可，可见反面很好求，既然用到正难则反，就不得不考虑容斥了，看约束条件。

假设：集合A = 第一行没有石子，集合B = 最后一行没有石子，集合C = 第一列没有石子，集合D = 最后一列没有石子，集合E = 答案集合；

则：

$E = S - A - B - C - D + A\bigcap B + A\bigcap C + A\bigcap D + B\bigcap C + B\bigcap D + C\bigcap D - A\bigcap B\bigcap C - A\bigcap B\bigcap D - A\bigcap C\bigcap D - B\bigcap C\bigcap D + A\bigcap B\bigcap C\bigcap D$

则：

$E = _{m*n}^{k}\textrm{C} - 2*_{(m-1)*n}^{k}\textrm{C} - 2*_{m*(n-1)}^{k}\textrm{C} + _{(m-2)*n}^{k}\textrm{C} + 4*_{(m-1)*(n-1)}^{k}\textrm{C} + _{m*(n-2)}^{k}\textrm{C} - 2*_{(m-2)*(n-1)}^{k}\textrm{C} - 2*_{(m-1)*(n-2)}^{k}\textrm{C} + _{(m-2)*(n-2)}^{k}\textrm{C}$

#include <iostream> #include<bits/stdc++.h> using namespace std; const int maxn = 400 + 7; #define mod  int fac[maxn][maxn]; void init(){ memset(fac,0,sizeof(fac)); fac[0][0] = 1; for(int i = 0;i<maxn;i++){ fac[i][0] = fac[i][i] = 1; for(int j = 1;j<i;j++){ fac[i][j] = (fac[i-1][j-1] + fac[i-1][j])%mod; } } } int main() { init(); int T; int t = 0; scanf("%d",&T); while(T--){ t++; int n,m,k; scanf("%d%d%d",&n,&m,&k); if(k>m*n){ printf("Case %d: 0\n",t); continue; } else if(k==m*n){ printf("Case %d: 1\n",t); continue; } int sum = fac[m*n][k]; sum = ((sum - 2*fac[(m-1)*n][k])%mod + mod)%mod; sum = ((sum - 2*fac[m*(n-1)][k])%mod + mod)%mod; sum = (sum + fac[(m-2)*n][k])%mod; sum = (sum + 4*fac[(m-1)*(n-1)][k])%mod; sum = (sum + fac[m*(n-2)][k])%mod; sum = ((sum - 2*fac[(m-2)*(n-1)][k])%mod + mod)%mod; sum = ((sum - 2*fac[(m-1)*(n-2)][k])%mod + mod)%mod; sum = (sum + fac[(m-2)*(n-2)][k])%mod; printf("Case %d: %d\n",t,sum); } return 0; }

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/136241.html

【数论系列】 计数原理与排列组合（鸽巢与容斥）

一. 基本原理与性质

1. 基本计数原理

2. 二项式定理和杨辉三角

3. 组合数基本性质