组合数学第三章VIP专享VIP免费

例[1，20]中2或3的倍数的个数[解]2的倍数是:2,4,6,8,10,12,14,16,18,20.10个3的倍数是：3，6，9，12，15，18。6个但答案不是10+6=16个，因为6，12，18在两类中重复计数，应减去。故答案是：16-3=13§3.1容斥原理引论容斥原理研究有限集合的交或并的计数。[DeMorgan定理]若A，B都是集合U的子集，则§3.2容斥原理(a)ABAB(b)ABABDeMogan定理的推广：设1,2,...,nAAAU是的子集212212............nnnnAAAAAAAAAA11则(a)A(b)A§3.2容斥原理最简单的计数问题是求有限集合A和B的并的元素数目。显然有ABABAB(1)定理：§3.2容斥原理UBAAB定理：(2)ABCABCABACBCABC§3.2容斥原理ABCACBCAB§3.2容斥原理ABC例一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理两门课的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。问这学校共有多少学生？§3.2容斥原理令：M为修数学的学生集合；P为修物理的学生集合；C为修化学的学生集合；170,130,120,4520,22,3PCMPMCPCMPCM§3.2容斥原理1701301204520223336MPCPCMPMMCPCMPCM即学校学生数为336人。§3.2容斥原理同理可推出：ABCDABCDABBCADABCABDBCDABCDAC利用数学归纳法可得一般的定理：§3.2容斥原理定理：设1,2,...,nAAA是有限集合，则1211112......(1)...nnniijiijiknjnAAAAAAAAAAAnii=1j>ik>j+A§3.2容斥原理121211112.........(1)...nnnnniijiijjkninAAANAAAANAAAAAAAAnii=1j>ik>jA-§3.2容斥原理例1求a,b,c,d,e,f六个字母的全排列中不允许出现ace和df图象的排列数。解：设A为ace作为一个元素出现的排列集，B为df作为一个元素出现的排列集，A∩B为同时出现ace、df的排列数。§3.3例根据容斥原理，不出现ace和df的排列数为：=6!-(5!+4!)+3!=582§3.3例4!,5!,3!.ABABAB例2求从1到500的整数中能被3或5除尽的数的个数。解：令A为从1到500的整数中被3除尽的数的集合，B为被5除尽的数的集合500500166,100;355003315ABAB§3.3例被3或5除尽的数的个数为16610033233ABABAB例3求由a,b,c,d四个字母构成的位符号串中，a,b,c,d至少出现一次的符号串数目。§3.3例解：令A、B、C分别为n位符号串中不出现a，b，c符号的集合。由于n位符号串中每一位都可取a，b，c，d四种符号中的一个，故不允许出现a的n位符号串的个数应是3n，即32nnBCABACCBA§3.3例1ABCa，b，c至少出现一次的n位符号串集合即为ABC4()(33243)1nnnnABCABACCBABCABC§3.3例求欧拉函数φ(n)：小于n且与n互素的数的个数。解：若n分解为素数的乘积1212...kaaaknppp设1到n的n个数中为pi倍数的集合为Ai,i=1,2,…,k则欧拉函数1212...,1,2,...,.,,1,2,...,.kaaakiiijijnpppnAikpnAAijkijpp......§3.3例1212121311212...(...)(...)111(1)(1)(1)kknkkAAAnnnnnpppppnnnpppppppnppp(n)=§3.3例260235,111(60)60(1)(1)(1)16235n例如则即比60小且与60无公因子的数有16个：7，11，13，17。19。23，29，31，37，41，43，47，49，53，59，此外尚有一个1。§3.3例n个元素依次给以标号1，2，…，n。N个元素的全排列中，求每个元素都不在自己原来位置上的排列数。设Ai为数i在第i位上的全体排列，=1，2，…，n。因数字i不能动，因而有：错排问题(1)!£¬1,2,...,iAnin(2)!,1,2,...,,ijAAninij同理§3.4错排问题每个元素都不在原来位置的排列数为12...!(,1)(1)!(,2)(2)!(,)1!111!(1)1!2!!nAAAnCn...