📄 3_3.htm
字号:
<html><head><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><link rel="stylesheet" href="../style.css"><title>3_3 例</title></head><body><p align="center"><font size="5"><b>§3 例</b></font></p><p><b>[例1]</b> 求a,b,c,d,e,f六个字母的全排列中不允许出现ace和df图象的排列数。<br><b>[解]</b> 设A为ace作为一个元素出现的排列集，<br> B为 df作为一个元素出现的排列集，<br> A∩B为同时出现ace、df的排列集。<br>∴ |A|=4!；|B|=5!；|A∩B|=3!；<br>根据容斥原理，不出现ace和df的排列数为：<br><img src="3_3_1.gif" width="204" height="32"></p><p><b>[例2]</b> 求从1到500的整数中能被3或5除尽的数的个数。<br><b>[解]</b> 令A为从1到500的整数中被3除尽的数的集合，B为被5除尽的数的集合,A∩B为能同时被3和5整除的数的集合.<br><img src="3_3_2.gif" width="389" height="45"><br>故能被３或５整除的数的个数为：<br>｜A∪B｜=｜A｜+｜B｜－｜A∩B｜=166+100－33＝233<br></p><p><b>[例3]</b> 求由a,b,c,d四个字母构成的位符号串中，a,b,c,d至少出现一次的符号串数目。<br><b>[解]</b> 令A、B、C分别为n位符号串中不出现a，b，c符号的集合。由于n位符号串中每一位都可 取a，b，c，d四种符号中的一个，故不允许出现a的n位符号串的个数应是3<sup>n</sup>，即：<br>｜A｜=｜B｜=｜C｜=3<sup>n</sup>；<br>｜A∩B｜=｜A∩C｜=｜B∩C｜=2<sup>n</sup>；<br>｜A∩B∩C｜=1<br>a，b，c至少出现一次的n位符号串集合即为：<img src="3_3_3.gif" align="top"width="70" height="24"><br><img src="3_3_4.gif" width="294" height="80"></p><p><b>[例4]</b> 求小于120的素数的个数.<br><b>[解]</b> 因为11<sup>2</sup>=121；故不超过120的合数必然是2、3、5、7的倍数，而且不超 过120的合数的因子不可能都超过11。 <br> 设A<sub><i>i</i></sub>为不超过120的数<i>i</i>的倍数集，<i>i</i>＝2,3,5,7<br><img src="3_3_5.gif" width="466" height="472"><br><blink><font color="#FF0000">注意</font></blink>：27并非就是不超过120的素数个数，因为这里排除了2，3，5，7着四个数，又包含了1这个非素数。2， 3，5，7本身是素数。故所求的不超过120的素数个数为: 27+4-1=30</p><p><b>[例5]</b> 用26个英文字母作不允许重复的全排列，要求排除dog，god，gum，depth， thing字样的出现，求满足这些条件的排列数。<br><b>[解]</b> 所有排列中，令：<br> A<sub>1</sub>为出现dog的排列的全体；<br> A<sub>2</sub>为出现god的排列的全体；<br> A<sub>3</sub>为出现gum的排列的全体；<br> A<sub>4</sub>为出现depth的排列的全体；<br> A<sub>5</sub>为出现thing的排列的全体；<br> 出现dog字样的排列，相当于把dog作为一个单元参加排列，故｜A<sub>1</sub>｜＝24!<br>类似有：｜A<sub>2</sub>｜＝｜A<sub>3</sub>｜＝24!，｜A<sub>4</sub>｜＝｜A<sub>5</sub>｜＝22!<br>由于god,dog不可能在一个排列中同时出现，故：｜A<sub>1</sub>∩A<sub>2</sub>｜＝0；<br>类似有：｜A<sub>2</sub>∩A<sub>3</sub>｜＝0；｜A<sub>1</sub>∩A<sub>4</sub>｜＝0。<br>由于dog和gum可以在dogum字样中同时出现，故：｜A<sub>1</sub>∩A<sub>3</sub>｜＝22!<br>类似的理由god和depth可以在godepth字样中同时出现，故｜A<sub>2</sub>∩A<sub>4</sub>｜＝20!<br>god和thing可以在thingod字样中同时出现，故：<br>｜A<sub>2</sub>∩A<sub>5</sub>｜＝20!；｜A<sub>1</sub>∩A<sub>5</sub>｜＝0；｜A<sub>4</sub>∩A<sub>5</sub>｜＝19!<br>｜A<sub>3</sub>∩A<sub>4</sub>｜＝｜A<sub>3</sub>∩A<sub>5</sub>｜＝20!<br>｜A<sub>1</sub>∩A<sub>2</sub>∩A<sub>3</sub>｜＝0；｜A<sub>1</sub>∩A<sub>2</sub>∩A<sub>4</sub>｜＝0<br>｜A<sub>1</sub>∩A<sub>2</sub>∩A<sub>5</sub>｜＝｜A<sub>1</sub>∩A<sub>3</sub>∩A<sub>4</sub>｜＝0<br>｜A<sub>1</sub>∩A<sub>3</sub>∩A<sub>5</sub>｜＝｜A<sub>1</sub>∩A<sub>4</sub>∩A<sub>5</sub>｜＝0<br>｜A<sub>2</sub>∩A<sub>3</sub>∩A<sub>4</sub>｜＝｜A<sub>2</sub>∩A<sub>3</sub>∩A<sub>5</sub>｜＝0<br> 由于god、depth、thing不可以同时出现，故｜A<sub>2</sub>∩A<sub>4</sub>∩A<sub>5</sub>｜＝0<br> ｜A<sub>3</sub>∩A<sub>4</sub>∩A<sub>5</sub>｜＝17!<br>其余多于3个集合的交集均为空集，不一一列举。故所求的满足要求的排列数为：<br>26!－3×24!－2×22!＋22!＋4×20!＋19!－17!＝26!－3×24!－22!＋4×20!＋19!－17! </p><p><b>[例6]</b> 求完全由n个布尔变量确定的布尔函数的个数.<br><b>[解]</b> 设f(x<sub>1</sub>,x<sub>2</sub>,...,x<sub>n</sub>)中x<sub><i>i</i></sub>不出现的 布尔函数类为:A<sub>i</sub>，i=１，２，．．．，n． <br> 由于n个布尔变量x<sub>1</sub>，x<sub>2</sub>，...，x<sub>n</sub>的不同的真值 表数目与2<sup>n</sup>位２进制数数目相同，故为<img src="3_3_6.gif"align="top" vspace="-14" width="22" height="22">个．根据容斥原理，满足问题要求的函数数目为：<br><img src="3_3_7.gif" width="333" height="162"><br>这10个布尔函数为：<br>x<sub>1</sub>∧x<sub>2</sub>，x<sub>1</sub>∧x<sub>2</sub>，x<sub>1</sub>∧x<sub>2</sub>，<br>x1∧x2， x<sub>1</sub>∨x<sub>2</sub>，x<sub>1</sub>∨x<sub>2</sub>，x<sub>1</sub>∨x<sub>2</sub>， x<sub>1</sub>∨x<sub>2</sub>，<br>(x<sub>1</sub>∨x<sub>2</sub>)∧(x<sub>1</sub>∨x<sub>2</sub>)， (x<sub>1</sub>∨x<sub>2</sub>)∧(x<sub>1</sub>∨x<sub>2</sub>)</p><p><b>[例7]</b> 欧拉函数．欧拉函数<img src="3_3_8.gif" align="top"vspace="-15" width="34" height="21">是求小于且与n互素的数的个数．<br><b>[解]</b> 若n分解成素数的乘积：<img src="3_3_9.gif" align="top"vspace="-15" width="114" height="26"><br>设1到n的n个数中为<i>p</i><sub>i</sub>倍数的集合为A<sub>i</sub>，i＝1,2,...,k．则：<br>｜A<sub>i</sub>｜＝n／<i>p</i><sub>i</sub>，i＝1,2,...,k．</p><p>｜A<sub>i</sub>∩A<sub>j</sub>｜＝n／(<i>p</i><sub>i</sub><i>p</i><sub>j</sub>)，i,j＝1,2,...,k，i≠j．<br> ．．．．．．<br><img src="3_3_10.gif" align="top" vspace="-15"><br>例如当n＝60＝2<sup>2</sup>×3×5，则<br><img src="3_3_11.gif"><br>即比60小且与60无公因子的数有16个：7,11,13,17,19,23,29,31,37,41,43,47,49,53,59,此外尚有一个1． </p></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -