組合數(shù)學(xué)教案第9講

1、教案教研室:數(shù)學(xué)分析教研室 教師姓名:授課時(shí)間:課程名稱 專業(yè)課選講 授課專業(yè)和班級(jí) 數(shù)學(xué) 0603授課內(nèi)容 §3.4相對(duì)位置上有限制的排列問題 授課學(xué)時(shí) 2學(xué)時(shí) 教學(xué)目的 應(yīng)用容斥原理解決實(shí)際問題教學(xué)重點(diǎn) 總集 S 及各個(gè)子集iA 的建立教學(xué)難點(diǎn) 涉及的集合中的元素的個(gè)數(shù)的求法教具和媒體使用 板書教學(xué)方法 講授法、討論法教 學(xué) 過 程 包括復(fù)習(xí)舊課、 引入新課、 重點(diǎn)難點(diǎn)講授、 作業(yè)和習(xí)題布置、問題討論、歸納總結(jié)及課后輔導(dǎo)等內(nèi)容時(shí)間分配 (90分鐘 一、復(fù)習(xí)舊課 重集的r 組合錯(cuò)排問題二、引入新課三、重點(diǎn)難點(diǎn)講授1、相對(duì)位置上有限制的排列問題2、有限制的排列問題與錯(cuò)排問題的關(guān)系3、

2、應(yīng)用四、作業(yè)和習(xí)題布置五、歸納總結(jié)10分 5分 30分 20分 15分 5分 5分1、相對(duì)位置上有限制的排列問題2、有限制的排列問題與錯(cuò)排問題的關(guān)系3、應(yīng)用講授新拓展內(nèi)容課后總結(jié)教研室主任簽字 年 月 日講稿授 課 內(nèi) 容備注一、復(fù)習(xí)舊課1、重集的 -r 組合 2、錯(cuò)排問題 二、引入新課n 個(gè)小學(xué)生列隊(duì)散步,除第一個(gè)學(xué)生外,每個(gè)學(xué)生前面都有另一個(gè)學(xué)生,由于學(xué)生們不喜歡每天排在自己前面的同學(xué)總是一個(gè)人,他們希 望每天都要改變一個(gè)排在自己前面的那個(gè)人,問有多少種方式改變他們 的位置。三、重點(diǎn)難點(diǎn)講授這個(gè)問題實(shí)質(zhì)上是一個(gè)相對(duì)位置上有限的排列問題。將它抽象成一 般的數(shù)學(xué)問題:對(duì)于給定的正整數(shù) n ,計(jì)

3、算集合1,2, ···, n 的且不 允許出現(xiàn) 12,23,34, ···, n n 1(-的全排列個(gè)數(shù) n Q 。對(duì)于這個(gè)問題,有下列定理,其結(jié)論就是該問題的解。 定理 1:對(duì)于 1n 有! 2(21! 1(11! -+- -=n n n n n Q n ! 1111(. 1-+-n n n 證明:設(shè) S 是集合1,2, ···, n !n S =令 1,., 2, 1(-=n j p j 表示 S 中的排列具有形式 1(+j j 出現(xiàn)這一性 質(zhì)。而 j A 1,., 2, 1(-=n j 表示 S 中

4、具有性質(zhì) j p 的排列組成的集合。于是S 中不具有性質(zhì) 121,., , -n p p p 的排列的集合為 121. -n 。 因而有121. -=n n Q講稿授 課 內(nèi) 容備注由容斥原理有121. -=n n Q -=+-=ji ji n i i A A A S 111211. 1(. -+-n n j i k j iA A A A A A由于 j A 表示 S 中具有性質(zhì) j p 的排列所組成的集合。于是 1A 中的一 個(gè)排列可以看作是具有 1(-n 元素12, ···, n 的一個(gè)排列,有!1(1-=n A 同理!1(-=n A j 1,., 3, 2(

5、-=n j 又由于 j i A A 表示 S 中同時(shí)具有性質(zhì) j i p p , 的排列所組成的集合。 于是 21A A 中的一個(gè)排列可以看作是具有 2(-n 個(gè)元素123, 4, 5, ···n 的一個(gè)排列,因此有!2(21-=n A A 同理! 2(31-=n A A !2(-=n A A ji 一般地,有!(. 21k n A A A ki i i -= 將以上值代人 n Q 表達(dá)式可得! 2(21! 1(11! -+- -=n n n n n Q n講稿授 課 內(nèi) 容備注!111 1(. 1-+-n n n 總結(jié):相對(duì)位置上有限制的錯(cuò)排也是錯(cuò)排的問題,可以

6、看作是錯(cuò)排 問題的一種特殊情況。定理 2:當(dāng) 2n 時(shí),有1-+=n n n D D Q 例 有 n 名兒童坐在一旋轉(zhuǎn)木馬上,問有多少種方式改變他們的座次,能使得:每個(gè)兒童有一個(gè)不同的兒童坐在他們的前面。解:問題的實(shí)質(zhì)是求集合 n ,., 2, 1的圓排列中不出現(xiàn) 12, 23, ···, n n 1(-, 1n 的圓排列個(gè)數(shù)。設(shè) S 是集合 n ,., 2, 1的所有圓排列組成的集合,則 !1(-=n S 又設(shè) i p 1,., 2, 1(-=n i 表示 S 中圓排列具有 1(+i i 形式這一性質(zhì)。n p 表示圓排列具有 1n 形式這一性質(zhì)。令 ,., 2,

7、 1(n i A i =表示 S 中具有性質(zhì) i p 的元素組成的集合,則 n . 21就表示 S 中不具有性質(zhì)n p p p ,., , 21的元素組成的集合。由容斥原理=+-=ji ji ni i n A A A S 121. nn j i k j iA A A A A A. 1(. 21-+-由于 1A 是所有圓排列中出現(xiàn) 12的圓排列的集合, 故 1A 的一個(gè)圓排列可以看成是具有 1-n 個(gè)元素的集合 n ,., 3, 12的一個(gè)圓排列,因此有講稿授 課 內(nèi) 容備注!2(1-=n A 同理!2(-=n A i ni ,., 3, 2-類似, 21A A 中的一個(gè)圓排列可以看成是具有 2-n 個(gè)元素的集合n ,., 4, 123的一個(gè)圓排列,故有!3(21-=n A A 同理! 3(-=n A A j i ,., 2, 1, ; (n j i j i =一般地,對(duì)于 11-n k ,有! 1(. 21-=k n A A A k i i i 1. 21=nA A A 故所求方式數(shù)為.! 2(1! 1(. 21+-=n n n n 1 1(! 01 1(1 -+ -+-n n n n n n 四、作業(yè)和習(xí)題布置 課本中 1855-P 。五、歸納總結(jié)本節(jié)介紹相對(duì)位置上有限制的排列問題和相對(duì)位置上有限制的排 列問題與錯(cuò)排問題的關(guān)系,在應(yīng)用時(shí)技巧性較強(qiáng),需多加練習(xí)。講 授 課 內(nèi)