【题解】组合数学
一、排列与组合
口诀：有序排列，无序组合，分类相加，分步相乘。
1.排列数公式：
表示的含义是从n个数中选出m个进行排队，有多少种不同的排法。
从n个不同的元素中任取m(m≤n)个元素的所有排列的个数，叫做从n个不同的元素中取出m(m≤n)个元素的排列数。
排列与元素的顺序有关，组合与顺序无关。
排列数公式：A(n,m) = n*(n-1)*...*(n-m+1)=n!/(n-m)!
排列数公式中总共有m项乘积。
常见的题目类别：
捆绑法
插空法
代码模板（递归法）：
// 计算阶乘
int factorial(int n){
int fc=1;
for(int i=1;i<=n;++i)
fc *= i;
return fc;
}
//计算排列数
int permutation(int n,int m){
int perm=factorial(n)/factorial(n-m);
return perm;
}2.组合数公式：
计算组合数公式的方法比较多。
定义法
先计算n!，然后令其分别除以m! 和（n-m)! 。这种方法的计算量庞大，至少n!数量级时间复杂度。
参考代码：
long long C(long long n,long long m){
long long ans = 1;
for(long long i = 1;i<= n;i++){
ans *= i;
}
for(long long i = 1;i <= m;i++){
ans/=i;
}
for(long long i = 1;i<= n-m;i++) {
ans /= i;
}
return ans;
}递推公式
利用公式：
进行求解
long long C(long long n,long long m){
if(m==0 || m == n) return 1;
return C(n-1,m)+C(n-1,m-1);
}我们把上面的方法改变一下，去除重复计算，将计算过的结果赋值给数组，用数组存储在之前重复计算的数字，然后就不用重复计算。
long long res[67][67]={0};
long long C(long long n,long long m){
if(m==0 || m==n) return 1;
if(res[n][m] != 0)return res[n][m];
return res[n][m] = C(n-1,m)+ C(n-1,m-1);//赋值给res[n][m]并返回
}边乘边除
long long C(long long n,long long m){
long long ans = 1;
for(long long i =1;i<=m;i++){
ans = ans * (n-m+i)/i; // 注意一定要先乘再除
}
return ans;
}【例题1】
6个男生，4个女生站一排，任何两名女生都不相邻的站法有多少种？
【例题2】
10名运动员，分给7个班，每班至少一个，共有多少种不同的分法？
【例题3】
求X+Y+Z=10正整数解的个数?
【例题4】
2位男生和3位女生站成一排，规定男生不占两端，3位女生有且只有2位相邻，问不同 排法有多少种？
二、鸽巢原理（抽屉原理）
1. 简单形式：如果 n＋1 个物体被放进 n 个盒子，那么至少有一个盒子包含两个或更多的物体。
2. 加强形式：令 q1，q2，…，qn为正整数。如果将 q1＋q2＋…＋qn－n＋1 个物体放入 n 个盒子内，那么或者
第一个盒子至少含有 q1个物体，或者第二个盒子至少含有 q2个物体，…，或者第 n 个盒子含有 qn 个物体
简言之：一个萝卜一个坑！
推论 1：m 只鸽子进 n 个巢，至少有一个巢里有只鸽子。
推论 2：n(m－1)＋1 只鸽子进 n 个巢，至少有一个巢内至少有 m/n 只鸽子。、
推论 3：若 m1，m2，……，mn 是正整数，且（（m1+m2+m3+...+mn）/n）>r-1 ，则至少有一个不小于 r。
常见问题：
１.属相有12个，那么任意37个人中，至少有几个人属相相同？
２.有300人到招聘会求职，其中软件设计有100人，市场营销有80人，财务管理有70人，人力资源管理有50人。那么至少有多少人找到工作才能保证一定有70人找的工作专业相同？
３.一个抽屉里有20件衬衫，其中4件是蓝的，7件是灰的，9件是红的，则应从中随意取出多少件才能保证有5件是同颜色的？
答案：
１.上取整(37 / 12) = 4
２.考虑最差情况，即软件设计，市场营销，财务管理均招了69人，人力资源管理招了50人，此时再多招1人，就有70人找的工作专业相同了。
故答案为 69*3 + 50 + 1 = 258
３.考虑最差情况，即已经取出了4件蓝色，4件灰色，4件红色，再多取出1件就满足条件。
故答案为 4 + 4 + 4 + 1 = 13。
三、容斥原理
扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
