组合数学讲义及答案4章容斥原理.pdf

组合数学 第四章 容斥原理 1/49 第 四 章第 四 章 容 斥 原 理容 斥 原 理 是组合学中的一个基本计数理论。也称是组合学中的一个基本计数理论。也称 “包容与排斥原理” 、“包容与排斥原理” 、 “入与出原理” 、 “包含排斥原理”或“交互分类原理” 。“入与出原理” 、 “包含排斥原理”或“交互分类原理” 。 加法法则的限制：要求将计数的集合划分为若干个互不相交加法法则的限制：要求将计数的集合划分为若干个互不相交 的子集，且这些子集都比较容易计数。的子集，且这些子集都比较容易计数。 问题：实际中又有很多计数问题要找到容易计数而又两两不问题：实际中又有很多计数问题要找到容易计数而又两两不 相交的子集并非易事。但往往能够知道某一集合的若干相交相交的子集并非易事。但往往能够知道某一集合的若干相交 子集的计数，进而把所要求的集合中的元素个数计算出来。子集的计数，进而把所要求的集合中的元素个数计算出来。 4.1 引引 言言 （一）（一） 研究内容研究内容 （1）实例实例 【例】求不超过【例】求不超过 20 的正整数中是的正整数中是 2 的倍数或的倍数或 3 的倍数的数的的倍数的数的 个数。个数。 不超过不超过 20 的正整数中是的正整数中是 2 的倍数的数有的倍数的数有 2 20 10 个，个， 即即 A 2, 4, 6, 8, 10, 12, 14, 16, 18, 20； 是是 3 的倍数的数有的倍数的数有 3 20 6 个，即个，即 B 3, 6, 9, 12, 15, 18 ； 二者相加为二者相加为 10616 个。个。 实际为实际为 13 个：即个：即 2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20； 原因：把既是原因：把既是 2 的倍数，又是的倍数，又是 3 的倍数的数重复算了一的倍数的数重复算了一 次，这样的数恰好有次，这样的数恰好有 32 20 3 个，即个，即 6, 12, 18。 正确的统计方法：正确的统计方法：106313 个。个。 （2）内容内容 研究若干个有限集合的交或并的计数问题。研究若干个有限集合的交或并的计数问题。 组合数学 第四章 容斥原理 2/49 （二）（二） 集合的表示集合的表示 用用大写字母大写字母表示一个集合，如表示一个集合，如 A、B、C、S 等，用小写字母等，用小写字母 表示集合的元素，如表示集合的元素，如 a、b、c、x、y、z 等。元素等。元素 a 属于集合属于集合 A， 记为记为Aa ，不属于，不属于 A，记为，记为Aa . 空集记为空集记为 。 （三）（三） 集合的运算集合的运算 （1） 并（和） ：记为并（和） ：记为BA或或 AB； （2） 交（积） ：记为交（积） ：记为BA或或 AB； （3） 差：记为差：记为 AB （4） 对立集（非） ：即对立集（非） ：即ASA 显然有显然有 ABBA AAB （四）（四） 优先级优先级 先取非，次为交，再次为并或差。先取非，次为交，再次为并或差。 出现在同一算式中的同级运算，按从左向右的顺序进行。出现在同一算式中的同级运算，按从左向右的顺序进行。 先括号内，后括号外。先括号内，后括号外。 （五）（五） 运算定律运算定律 （1） 交换律：交换律： ABBA， ABBA； （2） 结合律：结合律： (AB)CA(BC), (AB)CA(BC)； （3） 分配律：分配律：A(BC)ABAC, ABC(AB)(AC)； （4） De.Morgan 定律（互反律） ：定律（互反律） ： n AAA 21 n AAA 21 ， n AAA 21 n AAA 21 . （六）（六） 集合的势集合的势 当集合当集合 A 中的元素为有限个时，称中的元素为有限个时，称 A 为有限集合，其元素个为有限集合，其元素个 数记为数记为A，亦称为，亦称为 A 的的势势。关于。关于A，有如下简单性质：，有如下简单性质： （1） 若集合若集合 A、 B 不相交， 即不相交， 即 AB ， 则， 则BA AB； （2） 若若BA ，则，则BA AB。 组合数学 第四章 容斥原理 3/49 （3） BA AAB 4.2 容容 斥斥 原原 理理 （一）（一） 容斥原理容斥原理 【引理引理 4.2.1】 设设 A，B 为有限集合，则有为有限集合，则有 ABBABA （4.2.1） （证）（证）对于对于 AB 中的元素中的元素 a，在等式左边恰被统计一次，而，在等式左边恰被统计一次，而 在等式右边被统计的次数，分为三种情形统计：在等式右边被统计的次数，分为三种情形统计： （1）Aa ，但，但Ba ，则，则 a 也恰被统计一次；也恰被统计一次； （2）Aa ，但，但Ba ，同样恰被统计一次，同样恰被统计一次； （3）Aa 且且Ba ，那么必有，那么必有ABa ，从而，从而 a 被统计被统计 11 11 次。次。 所以，所以，a 在等式两边被统计的次数是相同的。在等式两边被统计的次数是相同的。 【定理定理 4.2.1】 （】 （容斥原理容斥原理） 设设 A1，A2，An为有限集合，则为有限集合，则 n AAA 21 n n nkji kji nji ji n i i AAAAAAAAA 21 1 111 1 (4.2.2) 证证 用数学归纳法证明。用数学归纳法证明。 (1) 当当 n2 时，由引理时，由引理 4.2.1 知，结论成立。知，结论成立。 (2) 设设对对 n1，结论正确。即，结论正确。即 121 n AAA 121 2 1111 1 1 1 n n nkji kji nji ji n i i AAAAAAAAA (4.2.3) (3)对于对于 n，有，有 组合数学 第四章 容斥原理 4/49 n n i i n i i AAA 1 11 1 1 1 1 n i inn n i i AAAA (4.2.4) 利用式利用式(4.2.3)： 1 1 1 1 n i ni n i in AAAA 1 1 n i niA A 1111 1 1nkji nkji nji nji n i ni AAAAAAAAA nn n AAAA 121 2 1 将上式与式将上式与式(4.2.3)代入式代入式(4.2.4)整理即得式整理即得式(4.2.2) . （二）（二） 逐步淘汰原理逐步淘汰原理 【定理定理 4.2.2】 （】 （逐步淘汰原理逐步淘汰原理） 设设 A1，A2，An为有限集合为有限集合 S 的子集，则的子集，则 n AAA 21 n n nkji kji nji ji n i i AAAAAAAAAS 21 111 1 (4.2.5) 证证 【证法一】利用【证法一】利用 De.Morgan 定律和集合求差运算性质，可定律和集合求差运算性质，可 得得 n AAA 21 n AAA 21 n AAAS 21 n AAAS 21 S nkji kji nji ji n i i AAAAAA 111 n n AAA 21 1 1 组合数学 第四章 容斥原理 5/49 n n nkji kji nji ji n i i AAAAAAAAAS 21 111 1 【证法二】 （为证明公式【证法二】 （为证明公式(4.2.6)铺垫） 。铺垫） 。 设有限集合设有限集合 S 和与和与 S 中的元素有关的性质集合中的元素有关的性质集合 P P1， P2， ， ， Pn。 AiS 中具有性质中具有性质 Pi的所有元素构成的子集。的所有元素构成的子集。Ai Aj AkS 中同时具有性质中同时具有性质 Pi、Pj、Pk的元素的集合。的元素的集合。 SAiS 中不具有性质中不具有性质 Pi的所有元素。的所有元素。 n AAA 21 是是 S 中不具有中不具有 P 中任何性质的元素之集合。中任何性质的元素之集合。 分析分析：式：式(4.2.5)左边是左边是 S 中不具有性质集合中不具有性质集合 P 中任何一种性质中任何一种性质 的元素个数。因此要证明式的元素个数。因此要证明式(4.2.5)成立，只要证明对成立，只要证明对 S 中的任何一中的任何一 个元素个元素 a， 如果， 如果 a 不具备不具备 P 中任何一个性质， 则中任何一个性质， 则 a 在等式右边被统在等式右边被统 计一次。否则，计一次。否则，a 被统计被统计 0 次。次。 设元素设元素Sa 且且 a 不具有任何性质，则不具有任何性质，则 a 不属于任何一个不属于任何一个 Ai 或若干个或若干个 Ai的交集，因此，的交集，因此，a 在右边被统计的次数为在右边被统计的次数为 101001 n 其次，若其次，若Sb ，且，且 b 同时具有同时具有 P 中的中的 k 种性质，那么，子种性质，那么，子 集集 A1、A2、An中必有某中必有某 k 个都含有元素个都含有元素 b，从而，从而 b 在在S中中 被统计一次，在被统计一次，在 n i i A 1 中被统计中被统计 k 次，在次，在 nji jiA A 1 中被统计中被统计 2 Ck 次，次， . 因此，按照式（因此，按照式（4.2.5） ，统计的总次数为） ，统计的总次数为 n k n k k k k k k kkk CCCCCC111 1 1 210 011 k 其中规其中规定：定：rk 时，时，0C r k 。证毕。证毕。 组合数学 第四章 容斥原理 6/49 （三）（三） 一般问题一般问题 （1）问题问题 已解决的问题已解决的问题：计算集合：计算集合 S 中具有某些性质的元素个数，以及不中具有某些性质的元素个数，以及不 具备这些性质的元素个数。具备这些性质的元素个数。 新的新的问题问题：如何计算：如何计算 S 里恰好具有里恰好具有 P 中中 k 个性质的元素个数。即个性质的元素个数。即 容斥原理的更一般情形。容斥原理的更一般情形。 （2）例子例子 设某单位共有设某单位共有S11 人， 其中有人， 其中有 1 A7 人会英语，人会英语， 2 A5 人会德语，人会德语， 21A A2 人同时会英、德人同时会英、德两种语言。两种语言。 会会 0 种语言（即不具有任何性质）的人数为：种语言（即不具有任何性质）的人数为： 21 AA S( 1 A 2 A) 21A A11(75)21（人）（人） 恰好会两种语言（即具有两种性质）的人数恰好会两种语言（即具有两种性质）的人数 21A A2 问：恰好会一种语言的人有多少？问：恰好会一种语言的人有多少？ 从集合的角度，可以分别计算：从集合的角度，可以分别计算： （1）会英语而不会德语的人数）会英语而不会德语的人数为为 21A A 211 AAA 1 A 21A A725 （2）会德语而不会英语的人数为）会德语而不会英语的人数为 21 AA 2 A 21A A3 所以，恰好会英、德语中一种语言的人数为所以，恰好会英、德语中一种语言的人数为 2121 AAAA 21A A 21 AA 1 A 2 A2 21A A8 注意注意， 21 AA 1 A 2 A 21A A108，原因在于，原因在于 21 AA 表示至少会一种语言的人数，其中自表示至少会一种语言的人数，其中自然含有同时会两种然含有同时会两种 组合数学 第四章 容斥原理 7/49 语言的人。语言的人。 （3）符号符号 设设 S 为一个集合，为一个集合，A i是是 S 上具有性质上具有性质 P i的元素集，令的元素集，令 0 qS 1 q n i i A 1 1 A 2 A n A q2 nji jiA A 1 ( 21A A 31A A n AA1)( 32A A n AA2) nn AA 1 q3 nkji kji AAA 1 ( 321 AAA 421 AAA n AAA 21 ) ( 431 AAA 531 AAA n AAA 31 ) nn AAA 11 （ 432 AAA 532 AAA n AAA 32 ） ） nn AAA 12 nnn AAA 12 qn n AAA 21 kNS 中恰好具有中恰好具有 k 种性质的元素个数（种性质的元素个数（k0,1, ,n） 。） 。 例如例如 0N n AAAAA 3221 1N n AAAA 321 n AAAA 321 nn AAAA 121 （4）结论结论 定理定理 4.2.3（一般公式一般公式） Nk n k n kn k k kk k kk qCqCqCq 1 2211 n kn n kn kkkkk qCqCqCq 1 2 2 21 1 1 组合数学 第四章 容斥原理 8/49 (4.2.6) 一般公式也称为一般公式也称为 Jordan 公式公式。 证证 类似于定理类似于定理 4.2.2 的证法二。的证法二。 设设 S 中元素中元素 a 具有具有 j 种性质，分三种情况予以讨论：种性质，分三种情况予以讨论： （1）jk 时，时，a 在在 qi 中同样不可能被统计；中同样不可能被统计； （3）jk： ，在： ，在 qk中，中，a 被统计了被统计了 k j C次，在次，在 qk1中，中，a 被统计被统计 了了 1 k j C次，在次，在 j q中被统计了中被统计了 j j C1 次，在次，在 qj 1，qj2， qn中被统计了中被统计了 0 次。即次。即 qk r rk j C （r0，1，nk） 。） 。 a 在式在式(4.2.6)右端总共被统计的次数为右端总共被统计的次数为 j j k j kj k j k k k j k k k j CC1CCCCC 2 2 1 1 )2()1( CCCCCC kj kj k j kj kj k j kj kj k j jj kj k j kj CC1 rj kj k j k r r j CCCC kj kj kj kjkjkj k j CCCCC 1 210 kj j k j CC kj k j C 11 0 定理得证。定理得证。 （四）（四） 对称原理对称原理 若性质若性质 n PPP, 21 是对称的，即具有是对称的，即具有 k 个性质的事物的个个性质的事物的个 数不依赖于这数不依赖于这 k 个性质的选取，总是等于同一个数值，则称这个个性质的选取，总是等于同一个数值，则称这个 值为值为公共数公共数，记作，记作 k R。例：。例： n AAAR 211 组合数学 第四章 容斥原理 9/49 nn AAAAAAR 131212 nnn AAAAAAAAAR 124213213 nn AAAR 21 记记SR 0 ，称子集，称子集 n AAA, 21 具有具有对称性质对称性质。则。则 k k n k i iiik RCAAAq k 1 21 定理定理 4.2.4（对称原理、对称筛）对称原理、对称筛） 若子集若子集 n AAA, 21 具有具有 对称性质，则有对称性质，则有 n AAA 21 1 1R Cn 2 2R Cn n n n n RC 1 1 n i i i n i RC 1 1 1 1 (4.2.7) 0N n n n n nn RCRCRCR1 2 2 1 1 0 n i i i nR C 0 1 (4.2.8) Nk k k n k k RCC 1 1 1 k k n k k RCC 2 2 2 k k n k k RCC n n n k n kn RCC 1 2 22 21 11 1 0 k k nkk k nkk k nk RCCRCCRCC n n n kn n kn RCC 1 (4.2.9) 或或 Nk n kn kn kn kknkknkkn k n RCRCRCRCC 1 2 2 1 10 (4.2.10) （五）（五） 总结总结 容斥原理用法总结容斥原理用法总结 在应用容斥原理求解计数问题时，可按在应用容斥原理求解计数问题时，可按 下列步骤进行：下列步骤进行： （1） 根据问题的实际情况， 构造一个有限集） 根据问题的实际情况， 构造一个有限集 S t eee, 21 和一个性质集和一个性质集 P n PPP, 21 ， i A是是 S 中具有性质中具有性质 i P的所有元的所有元 素组成的子集， 问题的关键是构造的性质集素组成的子集， 问题的关键是构造的性质集 P， 要使得， 要使得 k AAA 21 组合数学 第四章 容斥原理 10/49 容易计算出来（容易计算出来（k1, 2, , n） 。） 。 （2）统计）统计 S 中恰好具有中恰好具有 k 种特征的元素的个数时，将问题种特征的元素的个数时，将问题转转 化为求化为求 S 中恰好具有中恰好具有 P 中中 k 个性质的元素个数个性质的元素个数 Nk（k 0,1,2,n） ， 可利用逐步淘汰原理或一般公式， 即式） ， 可利用逐步淘汰原理或一般公式， 即式(4.2.5)或或(4.2.6)。 （3）当统计）当统计 S 中至少具有中至少具有 P 中一种性质的元素个数中一种性质的元素个数 L1时，时， 利用容斥原理，即式利用容斥原理，即式(4.2.2)，或由，或由 L1 0NS 求得。求得。 （4）注意）注意 nNNNNS 210 ，故可由此式，故可由此式 求得求得 S 中至少具有中至少具有 k 种特征的元素个数种特征的元素个数 Lk。如。如 k2 时，有时，有 L2 10NNS 4.3 应应 用用 4.3.1 排列组合排列组合问题问题 例例4.3.1 求求 a,b,c,d,e,f 六个字母的全排列中不允许出现六个字母的全排列中不允许出现 ace 和和 df 图像的排列数。图像的排列数。 解解 令令 A 表示表示 ace 作为一个元素出现的排列集合，作为一个元素出现的排列集合，B 为为 df 作为一个元素出现的排列集合，那么，作为一个元素出现的排列集合，那么，AB 为为 ace、df 同时出现的同时出现的 排列集合。因此排列集合。因此 A4！ ，！ ， B5！ ，！ ， AB3！ 由容斥原理，所求的排列数为由容斥原理，所求的排列数为 BA 6!(5!4!)3!582 另：求另：求 ace 和和 df 图像至少出现一次的排列数：图像至少出现一次的排列数： ABBABA 4!5!3!138 例例4.3.2 错排问题：错排问题：n 个元素依次给以标号个元素依次给以标号 1,2,n，进行全，进行全 排列，求每个元素都不在自己原来位置上的排列数。排列，求每个元素都不在自己原来位置上的排列数。 解解 令令 Ai表示数表示数 i 排在第排在第 i 个位置上的所有排列，则公共数个位置上的所有排列，则公共数 1 R i A（n1） ！ ，） ！ ， i1,2, ,n . 组合数学 第四章 容斥原理 11/49 同理同理 2 R jiA A（n2） ！） ！, i,j1,2, ,n , ij 3 R kji AAA（n3） ！） ！, i,j,k1,2, ,n ； i，j,k 两两不等两两不等 一般一般 k R k iii AAA 21 （nk） ！ ， k1,2, ,n 所求排列数为所求排列数为 Dn n AAA 21 n! 1 n C (n1)! 2 n C (n2)! ! 01 n n n C ! 0 ! 0 ! ! )!2( )!2( ! 2 ! )!1( )!1( ! 1 ! ! n n n n n n n n n ! 1 1 ! 2 1 ! 1 1 1! n n n 例例4.3.3 保位问题保位问题（亦称（亦称不动点问题不动点问题或或相遇问题相遇问题） ：将原始自） ：将原始自 然排列然排列 1,2,n 重新作成各种排列，求恰有重新作成各种排列，求恰有 m 个元素在其原来自个元素在其原来自 身位置的排列数（记作身位置的排列数（记作 mDn） 。） 。 解解 设性质设性质 i P：数：数i排在第排在第i个位置；集合个位置；集合 i A：具有性质：具有性质 i P 的全体排列。的全体排列。 k R niiiknAAA kiii k 21 1, ! 21 ；k 1,2, ,n !1!1 1 1 nCnnq n ， ， ， !knCq k nk ，nk 1 由定理由定理 4.2.3 知，知， mDn n mn n mn mmmmm qCqCqCq 1 2 2 21 1 1 !2!1! 22 2 11 1 mnCCmnCCmnC m nm m nm m n ! 01 n n mn n mn CC )!2( ! ! 2 )!2( )!1( ! ! 1 )!1( ! ! m n m m m n m m m n 组合数学 第四章 容斥原理 12/49 ! ! !)!( ! 1 n n mmn n mn )!( 1 1 ! 2 1 ! 1 1 1 ! ! mnm n mn )!( 1 1 ! 2 1 ! 1 1 1 )!( )!( ! ! mnmn mn m n mn mn m n mn DC mn D m n ! ! 另法：从另法：从 n 个元素中取个元素中取 m 个，有个，有 m n C种取法，且这种取法，且这 m 个元素个元素 保持不动，其余保持不动，其余 nm 个元素互相错排，有个元素互相错排，有 Dn m种，故共有种，故共有 mn m n DC 种排法。种排法。 特例，当特例，当 m0 时，即为错排问题，时，即为错排问题， 0 n D就是错排数就是错排数 Dn 4.3.2 初等数论问题初等数论问题 例例4.3.4 求不超过求不超过 120 的素数个数。的素数个数。 解解 （1）因）因 112121，故不超过，故不超过 120 的和数既是的和数既是 2、3、5、7 的倍数，而且其因子不可能都大于的倍数，而且其因子不可能都大于 11。即若。即若 1201 n且且 nab 为和数，则为和数，则 a 和和 b 中必有一个小于中必有一个小于 11。例如。例如 55511， 194297 （2）设）设 1201, xikxxAi为数为数i的倍数集（的倍数集（i 2, 3 ,5, 7） 60 2 120 2 A，40 3 120 3 A， 24 5 120 5 A， 17 7 120 7 A，20 32 120 32 AA， 0 7532 120 7532 AAAA （3）利用逐步淘汰原理计算）利用逐步淘汰原理计算 组合数学 第四章 容斥原理 13/49 7532 AAAA 7532 AAAAS 757353725232 AAAAAAAAAAAA 753752732532 AAAAAAAAAAAA 7532 AAAA 120(60402417)(20128853) (421 1)0 27 （4）但是，这）但是，这 27 个数未包含个数未包含 2,3,5,7 本身，却将非素数本身，却将非素数 1 含在含在 其中，故所求素数个数为其中，故所求素数个数为 274130 例例4.3.5 （Euler 问题）问题） 求求 1n 中与中与 n 互质的数的个数互质的数的个数(n) （称作（称作 Euler 函数） 。这是数论中一个著名的函数。例如：函数） 。这是数论中一个著名的函数。例如： (1) 1，(2)1，(3)2，(4)2，(5)4，(6)2 . 特别是当特别是当 n 是一个素数是一个素数 p 时，时，(p)p1 . 解解 分解分解 n 为素数幂的乘积为素数幂的乘积 k k pppn 21 21 （Pi 为素数） ，并设数集为素数） ，并设数集 N1，2，n，Ai为为 N 中能被中能被 Pi整除的整除的 那些数的全体，显然那些数的全体，显然 i i p n A ，i1,2, ,k ji ji pp n AA ， 1ijk K K ppp n AAA 21 21 于是于是 (n) k AAA 21 k k k ikjijii ppp n pp n p n n 2111 1 组合数学 第四章 容斥原理 14/49 k ppp n 1 1 1 1 1 1 21 k i i p n 1 1 1 4.3.3 集合的划分集合的划分 将集合划分为若干个非空部分后，部分与部分之间可以毫无区将集合划分为若干个非空部分后，部分与部分之间可以毫无区 分，也可以标上号以示区别。前者称为分，也可以标上号以示区别。前者称为无序划分无序划分，后者称为，后者称为有序有序 划分划分。 例例4.3.6 将一个将一个 n 元集划分成元集划分成 r 个非空子集，并且给每个子个非空子集，并且给每个子 集分别标上号：集分别标上号：1，2，r。试证由此得到的全部划分方案数为。试证由此得到的全部划分方案数为 D(n, r) r i n i r i ir 0 C1 1 0 C1 r i n i r i ir 证证 设设 S 为将为将 n 元集划分成有序元集划分成有序 r 部分的全部划分方案集 （每部分的全部划分方案集 （每 一部分可空） ，一部分可空） ，Ai表示第表示第 i 部分为空的全部方案集，那么部分为空的全部方案集，那么 n rS n r rAAA1 21 n ji rAA2 ，1ijr 0 21 n r rrAAA D(n，r) r AAA 21 n r r rn r n r n rrCrCrCr 121 21 1 0 1 r i n i r i irC 当当 rn 时，有：时，有： 1 1 21 121! n n nn n n n n CnCnCnn 改为无序划分，得改为无序划分，得 rnD r rnS, ! 1 , 2 即即 组合数学 第四章 容斥原理 15/49 r i n ir r i ni iirC r irirC r rnS 00 2 ,1 ! 1 ,1 ! 1 , 此类模型还对映以下问题：将此类模型还对映以下问题：将 n 个人分为个人分为 r 组的分法数（无序组的分法数（无序 划分） ，或将划分） ，或将 n 个小学生分为个小学生分为 r 个班，班号为个班，班号为 1，2，r，每班，每班 至少一人，求分法数（有序划分） 。类似的还有至少一人，求分法数（有序划分） 。类似的还有 n 元集元集 A 到到 r 元集元集 B 的满射共有的满射共有 D(n，r)种。所谓满射就是指种。所谓满射就是指 B 中每个元素至少有一中每个元素至少有一 个原像。个原像。 4.3.4 其它应用其它应用 例例4.3.7 求完全由求完全由 n 个布尔变量确定的布尔函数的个数。个布尔变量确定的布尔函数的个数。 解解 （1）分析：当分析：当 n2 时，两个自变量时，两个自变量 x，y 共有共有 224 种种 状态：状态： 00,01,10,11 。 有有2416种不同函数， 其取值情况见表种不同函数， 其取值情况见表4.3.1 。 表表 4.3.1 n2 时的布尔函数表时的布尔函数表 由一个或零个变量确定的函数：如由一个或零个变量确定的函数：如 f 3实际上是实际上是 x 的函数，与的函数，与 y 无关；无关；f 5则只是则只是 y 的函数，与的函数，与 x 无关。无关。f 10y，f 12x，f 151， 自变量自变量 x 0 0 1 1 y 0 1 0 1 函函 数数 f0 0 0 0 0 0 f1 xy 0 0 0 1 f2 xy 0 0 1 0 f3 x 0 0 1 1 f4 xy 0 1 0 0 f5 y 0 1 0 1 f6 (xy) (xy) 0 1 1 0 f7 xy 0 1 1 1 f8 xy 1 0 0 0 f9 (xy) (xy) 1 0 0 1 f10 y 1 0 1 0 f11 xy 1 0 1 1 f12 x 1 1 0 0 f13 xy 1 1 0 1 f14 xy 1 1 1 0 f15 1 1 1 1 1 组合数学 第四章 容斥原理 16/49 f 160。 完全由完全由 x、y 确定的函数应为确定的函数应为 10 个。个。 （2）设）设 n 个布尔变量个布尔变量 x1, x2, xn的布尔函数为的布尔函数为 f（x1, x2, xn） ，） ，S 是由所有是由所有 f 组成的函数的集合，组成的函数的集合， （3）设）设 Ai为为 S 中中 xi不出现的函数类（不出现的函数类（i1,2, , n） 。则） 。则 n S 2 2 1 2 21 2 n n AAA 2 2 2 n jiA A，1ijn 222 21 nn n AAA 所以所以 n AAA 21 n 2 2 1 21 2 n n C 2 22 2 n n C 21 n n n C 例如，例如， n2 时，时， 21 AA 2 2 2 21 2 2 C2 2 2 C168210 n3 时，时， 321 AAA 2222 3 3 22 3 21 3 2 23 CCC 25648122218 例例4.3.8 证明把证明把 n 分成各部分不能被分成各部分不能被 d 所整除的剖分数等于所整除的剖分数等于 把把 n 划分成每一部分不出现划分成每一部分不出现 d 次或次或 d 次以上的剖分数。次以上的剖分数。 （证）（证） npn 的所有剖分数的所有剖分数 n 的含有数的含有数 x 的剖分数等于数的剖分数等于数 nx 的剖分数的剖分数 xnp 。 推广为：推广为： n 的含有的含有 x， y， z， 的剖分数等于数， 的剖分数等于数 nxyz 的剖分数的剖分数 p(nxyz)。 例：例：n20，x8：20875（1275） ，） ，20864 2（12642） 组合数学 第四章 容斥原理 17/49 npx每一部分都不能被每一部分都不能被d所整除的所整除的n的剖分数，的剖分数， npy 每一部分出现的次数都不能超过每一部分出现的次数都不能超过 d1 的剖分数。的剖分数。 思路： 从思路