📄 3_6.htm
字号:
<html><head><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><title>§6 一般公式</title><meta name="GENERATOR" content="Microsoft FrontPage 3.0"><link rel="stylesheet" href="../style.css"></head><body><p align="center"><font size="5"><b>§6 一般公式</b></font></p><p> 若将§３.2中的例子改为“单修一门数学的学生有多少？”“只修一门课的学生有多少”“只修两门课的学生有多少？”则相应的答案表示如下：<br>｜M∩<span class="overline">P</span>∩<span class="overline">C</span>｜；<br>｜M∩<span class="overline">P</span>∩<span class="overline">C</span>｜+｜<spanclass="overline">M</span>∩P∩<span class="overline">C</span>｜+｜<spanclass="overline">M</span>∩<span class="overline">P</span>∩C｜<br>｜M∩P∩<span class="overline">C</span>｜+｜M∩<span class="overline">P</span>∩C｜+｜<spanclass="overline">M</span>∩P∩C｜<br> 设有与性质1, 2 , ··· , n相关的元素N个，A<sub>i</sub>为有第 i 种性质的元素的 集合.i=1,2,…,n.P<sub>k</sub>为至少有k种性质的元素的个数；q<sub>k</sub>为恰有k种性质的元素的个数。<br><img src="3_6_1.gif" width="261" height="205"></p><p><b>[定理]</b> <img src="3_6_2.gif" align="middle" width="160" height="48"><br><img src="3_6_3.gif" width="273" height="48"><br><b>[证1]</b> 设某一元素恰有k种性质，则其对P<sub>k</sub>的某一项的贡献为１，而对P<sub>k+1</sub>，P<sub>k+2</sub> , ··· ,P<sub>n</sub>的贡献都是０。若某一元的性质少于k种,则其对P<sub>k</sub>，P<sub>k+1</sub>，···，P<sub>n</sub>的贡献都是０。 若恰有k + j种性质，则其对Pk的贡献是C(k+j,k),对P<sub>k+i</sub>的贡献是C(k+j,k+i).<br><img src="3_6_4.gif" width="328" height="248"><br><img src="3_6_5.gif" width="272" height="212"><br></p><p><b>[证2]</b> 根据定义:<img src="3_6_6.gif" align="middle" width="201"height="53"><br>q<sub>k</sub>由P<sub>k+j</sub>的代数和组成，符号 (－1)<sup>j</sup> ，计算P<sub>k+j</sub>的重复度 ：k+j个集的交的绝对值的项的总个数为C(n,k)C(n-k,j) , 共C(n,k+j)种。每一项的重复度为 C(n,k)C(n-k,j)／C(n,k+j) =C(k+j,k)种 ,从而P<sub>k+j</sub>的重复度也是C(k+j,k)种.<br><img src="3_6_7.gif" width="194" height="98"></p><p><b>[证3]</b> 对N做归纳．<br>N=1时，设此元有m种性质，m ＜ n ,不妨设A<sub>1</sub> =A<sub>2</sub>= ··· =A<sub>m</sub>={ a<sub>1</sub> }。显然 P<sub>j</sub> =C(m,j)，若 j＞m，则 P<sub>j</sub> = 0；由定义，得<br><img src="3_6_8.gif" width="298" height="528"></p><p><b>[例]</b> 某校有12个教师，已知教数学的有８位，教物理的有６位，教化学的５位；数、理５位，数、化４位，理、化３位；数理化３位。问教其他课的有几位？只教 一门的有几位？只好教两门的有几位？<br><b>[解]</b> 令教数学的教师属于A<sub>1</sub>，教物理的属于A<sub>2</sub>，教化学的属于A<sub>3</sub>。则<br>P<sub>0</sub>＝１２，<br>P<sub>1</sub>＝| A<sub>1</sub> |+| A<sub>2</sub>|+| A<sub>3</sub> |＝8+6+5＝１９;<br>P<sub>2</sub>＝| A<sub>1</sub>∩A<sub>2</sub>|+ | A<sub>1</sub>∩A<sub>3</sub>|+| A<sub>2</sub>∩A<sub>3</sub>|＝12；<br>P<sub>3</sub>＝| A<sub>1</sub>∩A<sub>2</sub>∩A<sub>3</sub>|＝3；<br>故 教其他课的老师数为：<br> q<sub>0</sub>＝P<sub>0</sub> －P<sub>1</sub> +P<sub>2</sub>－P<sub>3</sub>＝２<br>恰好一门的教师数：<br> q<sub>1</sub>＝P<sub>1</sub>－2P<sub>2</sub> + 3P<sub>3</sub>＝4<br>恰好教两门的老师数为：<br> q<sub>2</sub>＝P<sub>2</sub>－3P<sub>3</sub>＝3</p><p><b>[例]</b> n 对夫妻围坐问题．<br>设 n 对夫妻围圈而坐，男女相间，每个男人都不和他的妻子相邻，有多少种可能的方案？<br><b>[解]</b> 不妨设 n 个女人先围成一圈，方案数为( n－1 )! 。对任一这样的给定方案， 顺时针给每个女人以编号1 , 2 , ··· , n。设第i号与第 i + 1号女人之间的位置为第 i 号位置， 1≤ i ≤n－1。第 n 号女人与第1 号之间的位置为第 n 号位置。设第 i 号女人的丈夫的编号也为第 i 号， 1≤ i ≤ n。让 n 个男人坐到上述编号的 n 个位置上。设 a<sub>i</sub>是坐在第 i 号位置上的男人，则<br>a<sub>i</sub> ≠ i ，i + 1，１≤ i ≤n－1；a<sub>n</sub>≠n，1。<br>这样的限制也即要求在下面3行n列的排列中<br>1 2 3 ··· ··· n-1 n<br>2 3 4 ··· ··· n 1<br>a<sub>1</sub> a<sub>2</sub> a<sub>3</sub> ··· ··· a<sub>n-1</sub> a<sub>n</sub><br>每列中都无相同元素。满足这样的限制的排列 a<sub>1</sub>a<sub>2</sub> ···a<sub>n</sub>称为<b>二重错排</b>。<br>设二重错排的个数为U<sub>n</sub>，原问题所求的方案数就是U<sub>n</sub> ( n－1)！。<br> 设A<sub>i</sub>为 a<sub>i</sub> = I 或 I + 1 (1≤ I ≤n－1 )，a<sub>n</sub> = n或1的排列 a<sub>1</sub> a<sub>2</sub> ··· a<sub>n</sub>的集合。则｜A<sub>i</sub>｜= 2 (n－1)! ，关键是计算<img src="3_6_9.gif" align="middle" width="90" height="49"><br> 也就是从( 1 , 2 ) ( 2 , 3 ) ··· ( n－１, n ) ( n , 1)这n对数的k 对中各取一数，且互不相 同的取法的计数。这相当于从1 , 2 , 2 , 3 ,3 ,4, ···,n－1, n－1, n , n , 1中取 k 个互不相邻数的组合 的计数，但首尾的１不能同时取。回想无重复不相邻组合的计数：<br>C’( n , r ) = C ( n－r + 1 , r ) ,<br>这里所求的是<br>C(2n-k+1,k)－C(2n-4-(k-2)+1,k-2)=C(2n-k,k)×2n／(2n-k)<br><img src="3_6_10.gif"></p></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -