首页 > 代码库 > 专题——计数原理
专题——计数原理
由于最近在研究数论,所以这期为大家带来一个数论中的专题——计数原理,下面我们来看四个概念:
一、配对原理:
对于集合A、B,如果存在一个一一映射,f:A→B,则|A|=|B|,假如我们很难计算A的值,不如转变方法,先计算B的值,再根据一一映射反推A,这时就需要找到这样一个易于计算的B,这需要很高的技巧。
二、容斥原理:
<1>容斥原理
把集合A分成子集A1,A2,A3,…,Am,即:A=A1∪A2∪A3…∪Am
,简单的来说,要求的集合是等于全集减去所有子集相交的重复的部分。
<2>逐步淘汰原理
设S为集合,Ai为S的子集,记=S-Ai
|∩∩…∩|=|S|-|A1∪A2∪A3…∪Am|
三、算两次:
算两次这个很好理解,就是通过两种方法来计算某个值,则这两种方法等价,建立方程,就可以把你想要的求出来。
典例:皮克定理:
一个计算点阵中顶点在格点上的多边形面积公式:S=a+b÷2-1,其中a表示多边形内部的点数,b表示多边形边界上的点数,S表示多边形的面积
四、polya数:
polya计数是计算对称情况下(旋转和镜面反射)不等价的状态。下面给出几种简单情况下的公式,都是考虑对称的图形,而且可以旋转和翻转(镜面反射)。
①用p种颜色对一个正五边形顶点着色,共有[p(p2+4)(p2+1)/10]种不同情况。
②用p种颜色对一个正四边形顶点着色,共有[(p4+2p3+3p2+2p)/8]种不同情况。
③用p种颜色对一个正三角形顶点着色,共有[(p3+3p2+2p)/6]种不同情况。
应用举例:
例1:有序拆分的种数——配对原理
题目描述 Description
把正整数n表示为若干个正整数之和,和式中的项的不同次序,也是不同的表达式,例如:4=4=3+1=1+3=2+2=2+1+1=1+2+1=1+1+2=1+1+1+1,共有8种表示方法。上面这种表示称为n的有序拆分,把n的有序拆分的种数记为R(n),请计算R(n)。
思路:
将n分解为n个1,排成一排,在这些1之间有n-1个空格,在这n-1个空格处填上‘+’表示将两边的1相加,填上‘-’表示将这个空格废除。这样每一种填‘+’或‘-’的方法对应n个有序拆分,根据配对原理,R(n)等于n-1个空格填‘+’或‘-’的方法数目,填‘-’的方法数明显就是n-1, 所以填‘+’的方法数就是2n-1。
例2:平行四边形的个数——配对原理
题目描述 Description
如图(左)所示,把三角形ABC的三边各n等分,过各等分点做各边的平分线,将三角形ABC分割成一些小的平行四边形,计算这些小平行四边形的个数。
思路:
先计算不平行于BC的小平行四边形的个数,把这些小平行四边形的集合记为A。
如图(右)所示,延长AB至D,取BD=AB/n,延长AC至E,取CE=AB/n。将直线DE平分为n+1段,得到n+2个点(图中我只画出了四个点实际上有六个平分点在DE上)。观察DE边上任意四点组(I,J,K,L)的集合B,过这四点,左边两点向右做平行线,右边亮点向左边做平行线,做AB和AC的平行线,唯一确定一个边不平行于BC的小平行四边形(右图灰色部分)。
因此,|A|=|B|=C(n+2,4),即从DE上的n+2个点选取4个点为一组的方法总数
又因为三角形有三边,每一条边都可以做类似选取,所以总的平行四边形的个数就是3×C(n+2,4)。
例3:书架上的书——容斥原理
题目描述 Description
在书架上放有编号为1,2,…,n的n本书。现将n本书全部取下然后再放回去,当放回去时要求每本书都不能放在原来的位置上。例如:n=3。
原来位置为:1,2,3。
放回去时只能为:3,1,2或2,3,1这两种。
问题:求当n=5时满足以上条件的方法有多少种?
思路:
在前面的“旅行”这个问题中,我讲过了错排问题,这题当然可以用错排问题公式来解,但这个专题是数论中的计数问题,当然要用逼格高一点的数论方法来求解。
我们分别用A1~A5表示1~5号位现在要求每本书都不能在自己的位置上,也就是求|∩∩|
专题——计数原理