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

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

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

3、算集合1,2, ···, n 的且不 允許出現(xiàn) 12,23,34, ···, n n 1(-的全排列個數(shù) n Q 。對于這個問題,有下列定理,其結(jié)論就是該問題的解。 定理 1:對于 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 中的一 個排列可以看作是具有 1(-n 元素12, ···, n 的一個排列,有!1(1-=n A 同理!1(-=n A j 1,., 3, 2(

5、-=n j 又由于 j i A A 表示 S 中同時具有性質(zhì) j i p p , 的排列所組成的集合。 于是 21A A 中的一個排列可以看作是具有 2(-n 個元素123, 4, 5, ···n 的一個排列,因此有!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 表達式可得! 2(21! 1(11! -+- -=n n n n n Q n講稿授 課 內(nèi) 容備注!111 1(. 1-+-n n n 總結(jié):相對位置上有限制的錯排也是錯排的問題,可以

6、看作是錯排 問題的一種特殊情況。定理 2:當 2n 時,有1-+=n n n D D Q 例 有 n 名兒童坐在一旋轉(zhuǎn)木馬上,問有多少種方式改變他們的座次,能使得:每個兒童有一個不同的兒童坐在他們的前面。解:問題的實質(zhì)是求集合 n ,., 2, 1的圓排列中不出現(xiàn) 12, 23, ···, n n 1(-, 1n 的圓排列個數(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 的一個圓排列可以看成是具有 1-n 個元素的集合 n ,., 3, 12的一個圓排列,因此有講稿授 課 內(nèi) 容備注!2(1-=n A 同理!2(-=n A i ni ,., 3, 2-類似, 21A A 中的一個圓排列可以看成是具有 2-n 個元素的集合n ,., 4, 123的一個圓排列,故有!3(21-=n A A 同理! 3(-=n A A j i ,., 2, 1, ; (n j i j i =一般地,對于 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è)和習題布置 課本中 1855-P 。五、歸納總結(jié)本節(jié)介紹相對位置上有限制的排列問題和相對位置上有限制的排 列問題與錯排問題的關(guān)系,在應用時技巧性較強,需多加練習。講 授 課 內(nèi)