第六章容斥原理及應(yīng)用64帶有禁止位置的排列-資料下載頁(yè)
2025-08-01 13:19本頁(yè)面
【正文】 元素的循環(huán)排列再去掉本單位人相鄰并排 37 坐的方案數(shù) :(2n1)! － 2n(n1)!種 。 將集合 {1,2,3… .n}的元素由小到大按順時(shí)針?lè)较蚺懦梢粋€(gè)圓環(huán) ， 并規(guī)定數(shù)字小的在前 。當(dāng)前這個(gè)排列為標(biāo)準(zhǔn)排列 。 問(wèn)：使得每個(gè)數(shù)字前面的數(shù) 不是標(biāo)準(zhǔn)排列時(shí)的數(shù) ， 這樣 的新排列數(shù)是多少 ？ … .. 3 n 2 1 38 解：這是一個(gè)典型的環(huán)型錯(cuò)位排列； 令 S為集合 {1,2,3,…, n}的全部環(huán)型 n排列的集合， | S |=(n1) !。 Pj為在環(huán)型排列中出現(xiàn) j(j+1)模式的性質(zhì)，( j =1,2,…. n, 注意 n+1=1)。 Aj為滿足性質(zhì) Pj的排列的集合，與直線排列的區(qū)別在于 j的取值達(dá)到 n，因此： nn AAAq ??? . . . . .21?39 下來(lái)分析每個(gè) ?Aj?的數(shù)量 。 A1中的排列必定 出現(xiàn) 12這樣的子串 ， 即對(duì) n1個(gè)元素的集合{12,3,4….n}進(jìn)行環(huán)型排列 。 所以有 ?A1?=(n2)! 對(duì)一般的每個(gè) ?Aj?有 ?Aj?=(n2)! ； 對(duì) Aj中任意兩個(gè)的交 Ai∩Aj, 比如是 A1∩A2或 者 A1∩A3, 中的排列包含兩種模式： (1)共享同一個(gè)元素，如 12 23。 40 (2)沒(méi)有共享的元素，如 12 45； (1)情況下就如同排列中有子串 123， n個(gè)元素中有三個(gè)合并成一個(gè)，就是對(duì) n2個(gè)元素的集合{ 123, 4, 5,… n}的環(huán)型排列 。 ?A1∩A2?=(n3)! ； (2) 情況下就如同排列中有子串 12和 34，就是 { 12, 34 , 5,… n}的環(huán)型排列 ?A1∩A3?=(n3)! ,一般地： ?Ai∩Aj?= (n3)! 。更一般地，對(duì)于集合 {1,2, ….n}中的每個(gè) k組合 {i1, i2, ….ik}有： 41 由于對(duì)每一個(gè) k = 1,2,….n1(有相鄰的子串就一定少一個(gè)元素 )，存在集合 {1,2, ….n1}的 個(gè) k組合，應(yīng)用容斥原理 (P107) )!1(. . . . . .21 ??? knAAA kiii ???!11)1(......)!4(3)!3(2)!2(1)!1(.......211?????????????????????????????????????????????????????????????????????nnnnnnnnnAAnAnSqnjiin?42 我們已經(jīng)完成的有： Q1 = 1； Q2 = 1； Q3 = 3； Q4 = 11； Q1, Q2,Q3,… 與錯(cuò)位排列數(shù)緊密相關(guān)，實(shí)際上我們有結(jié)論： Qn= Dn+Dn1 (n≥2) (見(jiàn)習(xí)題 23)，因此我們可以通過(guò)錯(cuò)位排列數(shù) Dn來(lái)計(jì)算 Qn 例如 Q6 =D6+D61 =256 + 44=300 （見(jiàn) P113） 53!144!234!324!414!55 ??????????????????????????????????????Q43 總 結(jié) 本次課我們介紹了禁止位置的排列和部分禁止位置的排列等知識(shí)。 重點(diǎn)掌握 非攻擊 型車(chē)在放棋盤(pán)中的放置方法和求法；部分禁止位置的排列數(shù) Qn的公式 44 本次授課到此結(jié)束 作業(yè)如下 : P121 25, 26， 27， 28 {1， 2， 3， 4， 5， 6}的排列 i1 i2 i3 i4 i5 i6 的個(gè)數(shù)。其中： i1 ?1,5； i3 ?2,3,5； i4 ?4； i6 ?5,6； 45 {1， 2， 3， 4， 5， 6}的排列 i1 i2 i3 i4 i5 i6 的個(gè)數(shù)。其中： i1 ?1,2,3； i2 ?1； i3 ?1； i5 ?5,6； i6 ?5,6； 。她們可以有多少種方法改變座位，使得每個(gè)女孩前面的女孩都與原先的不同。 46 。使得每個(gè)男孩都面對(duì)另一個(gè)男孩。能夠有多少種方法改變座位使得每個(gè)人面對(duì)的男孩都不同。 下次上課內(nèi)容： 某些數(shù)列
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1