ACM数论----计数原理与排列组合（鸽巢+容斥）

84 阅读 0 评论 56 点赞

我是靠谱客的博主俊秀红酒，最近开发中收集的这篇文章主要介绍ACM数论----计数原理与排列组合（鸽巢+容斥），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一.排列组合

1.计数原理的两大基本原理

（1）加法原理：做一件事情有n个办法，第i种办法有mi个方案，则做这件事情一共有m1 + m2 + m3 +...... + mn种方案

（2）乘法原理：做一件事情有n个步骤，第i个步骤有mi个方案，则做这件事情一共有m1*m2*m3*.....*mn种方案

注：

加法原理是分类，不同类之间互不干扰，哪一类都可以独立完成这个任务

乘法原理是分步，不同步之间有次序先后关系，必须完成所有步骤才能完成这个任务

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

（1）杨辉三角

性质1：第i行的数字与 (a+b)^(i-1)的系数一一对应

性质2：每一个数字等于肩上两数字之和

（2）二项式定理

每一项系数 = C(n,0) + C(n,1) + C(n,2) + ...... + C(n,n)

恰好与杨辉三角第n+1行对应

3.组合数基本性质

（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）求和：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）求和3： $c(n,0)^{2} + c(n,1)^{2} + c(n,2)^{2} + ..... + c(n,n)^{2} = c(2n,n)$

4.常见的计数问题

（1）无重复的排列问题

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

C(n,m)*m! = n!/(n-m)!

特别的：当n==m时，答案为n!

（2）无重复的组合问题

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

C(n,m) = n!/m!*(n-m)!

（3）有重复的全排列问题

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

n1!*n2!*n3!*....*nk!*x = n!

则：x = n!/(n1!*n2!*n3!*....*nk!)

（4）有重复的组合问题

有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）有重复元素的排列问题

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

（6）多组合问题

把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）单色三角形模型

给定空间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）错排问题

某人写了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.概念：

在计数时，必须注意没有重复，没有遗漏。

为了使重叠部分不被重复计算，人们研究出一种新的计数方法。

这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复。

这种计数的方法称为容斥原理。

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

2.三个集合的容斥原理: 设A, B, C是三个有限集合

|A + B + C| = |A| + |B| + |C| - |AB| - |AC| - |BC| + |ABC|

3.容斥原理使用特征

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

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

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

三.例题&解题模型

1.UVA11538 Chess Queen

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

分析：

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

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

再分析对角线上的：假设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("%llun",m*n*(m + n - 2) + 2*n*(n-1)*(3*m - n - 1)/3);
}
return 0;
}

2.uva11401 数三角形

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

分析：假设最大边长为x的三角形个数为C(x),假设其他两边为y,z

则由构成三角形条件可知： y + z > x，则z 的范围为 x - y<　z <　ｘ

当ｙ为１时：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 = 1000000 + 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("%lldn",Triangle[n]);
}
return 0;
}

3.uva11806 拉拉队

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

分析：若直接考虑，第一行第一列放一个石子就能同时满足两个条件，考虑起来很麻烦

正难则反：若求第一行第一列最后一行最后一列都没有石子，那么答案 = C((m-2)*(n-2),k)

若求第一行或第一列或最后一行或最后一列没有石子，答案也很好求，去掉这一行/列组合数即可，可见反面很好求，既然用到正难则反，就不得不考虑容斥了，看约束条件

假设集合A = 第一行没有石子

集合B = 最后一行没有石子

集合C = 第一列没有石子

集合D = 最后一列没有石子

集合E = 答案集合

则

$e = s - a - b - c - d + abigcap b + abigcap c + abigcap d + bbigcap c + bbigcap d + cbigcap d - abigcap bbigcap c - abigcap bbigcap d - abigcap cbigcap d - bbigcap cbigcap d + abigcap bbigcap cbigcap 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 1000007
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: 0n",t);
continue;
}
else if(k==m*n){
printf("Case %d: 1n",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: %dn",t,sum);
}
return 0;
}

四.鸽巢原理/抽屉原理

1.描述

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

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

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

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

2.作用：用来证明存在性问题