计数问题_牛客博客

一项工作需要分为t步完成，工作的每一步都有ni种选择，那么完成这项工作的所有可能选择就是将每一步的可能选择相乘。n1* n2* n3.......nt

例如：新高考下广东选课政策为“3+1+2”，那么要选出自己的科目需要分三步，第一步必选语数英，所以就只有一种选择；第二步从物理或者历史里面挑一门科目，所以有两种选择；第三步从政治、化学、生物、地理四门科目里挑两门，有C(4,2)种选择。后将三部分所有可能性相乘即可。

假定有n个集合，各个集合间互不相交，那么从所有集合中能够选出来的总元素个数等于所有集合的元素个数之和。

如一项工作可以有n个解决方案，每个解决方案相互独立，并且每个解决方案都有t种具体对应的方法。所以这项工作的解决方法共需将每个方案的具体方法相加即可。

从n个物体中选出m个物体，不讲究顺序，则共有C(n,m)种选择，组合强调无序性。

例如：从10个学生中抽出5个学生参加活动，共有C(10,5)种选择

从一个含n个元素的集合中挑选出m个元素出来，并将它们按顺序有排好的问题，是排列问题。排列的表达为A(n,m)/P(n,m)

排列问题的经典问题有：

1.环形排列：如果将n个人按圆桌边排列成一个环，则共有A(n,n)/n种选择。因为在排列队列中有重复。例如顺序：abc bac cab 在直线排列中不同，但当他们首尾相接，则对应的是相同的环形排列。

2.插空问题：将5个男孩和2个女孩排成行，但女孩不能相邻。则就需要插空。先将男孩分割开来并排序A(5,5)再将女孩排入5个男孩中的6个空位中并且排序则为A(6,2)。最后因为这是分两步，所以按乘法原理A(5,5)* A(6,2)

容斥原理是人类在计算某些数目时，先将多余的部分包容进来，最后剔除出去的原理

|A∪B|=|A|+|B|-|A∩B|

上面为求AB和混合，先求出各自独立部分相加，再将重复两遍地混合部分删除一部分。

由上面公式可以推出|!A∩!B|=|U|-(|A|+|B|-|A∩B|)

鸽笼原理的内容是：如果有n-1只鸽子，n个笼子，那么必定有一个笼子里面存在两只鸽子。它是用来证明存在性的。

例如：证明：如果从1-10所有数字里面挑6个数，那么必定存在其中两个数的和为11。

先将1-10所有能组合成11的数组列出来{1,10}{5,6}{4,7}{3,8}{2.9}。那么将这五组数组看成是五个鸽笼，六个数字看成6只鸽子，那么按题意必定会上面五个数组中组成任意一个数组。