一、排列与组合

口诀：有序排列，无序组合，分类相加，分步相乘。

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。

三、容斥原理