解決排列問題的常用方法.ppt

解決排列問題的常用方法,復(fù)習(xí)引入：,什么叫做從n個不同元素中取出m個元素的一個排列？,從n個不同元素中取出m（mn）個元素，按照一定的順序排成一列，叫做從n個不同元素中取出m個元素的一個排列.,從n個不同的元素中取出m（mn)個元素的所有排列的個數(shù)，叫做從n個不同元素中取出m個元素的排列數(shù). 用符號 表示,什么叫做從n個不同元素中取出m個元素的排列數(shù)？,排列數(shù)的兩個公式是什么？,（n，mN*，mn）,（一）特殊元素的“優(yōu)先安排法”,對于特殊元素的排列組合問題，一般應(yīng)先考慮特殊元素，再考慮其他元素。,例1用0，1，2，3，4這五個數(shù)，組成沒有重復(fù)數(shù)字 的三位數(shù)，其中偶數(shù)共有（ ） A.24 B.30 C.40 D.60,分析：由于該三位數(shù)是偶數(shù)，所以末尾數(shù)字必須是偶數(shù)， 又因?yàn)?不能排首位，故0就是其中的“特殊”元素，應(yīng)優(yōu)先安排。按0排在末尾和不排在末尾分為兩類；,0排在末尾時，有 個 0不排在末尾時，有 個 由分類計數(shù)原理，共有偶數(shù)30個.,例2：（1）7位同學(xué)站成一排，共有多少種 不同的排法？,分析：問題可以看作7個元素的全排列.,(2) 7位同學(xué)站成兩排(前3后4)，共有多少種不同的排法？,分析:根據(jù)分步計數(shù)原理,(3) 7位同學(xué)站成一排，其中甲站在中間的位置,共有多少種不同的排法？,分析:可看作甲固定,其余全排列,(4) 7位同學(xué)站成一排，甲、乙只能站在兩端的排法共有多少種？,單三步,(5) 7位同學(xué)站成一排，甲、乙不能站在排頭和排尾的排法共有多少種？,解法一:(特殊位置法),第一步:從其余5位同學(xué)中找2人站排頭和排尾,有 種;,第二步:剩下的全排列,有 種;,答：共有2400種不同的排列方法。,單三步,解法二:(特殊元素法),第一步:將甲乙安排在除排頭和排尾的5個位置中的兩個位置上,有 種;,第二步:其余同學(xué)全排列,有 種;,答：共有2400種不同的排列方法。,(5) 7位同學(xué)站成一排，甲、乙不能站在排頭和排尾的排法共有多少種？,單三步,解法三:(排除法),先全排列有 種,其中甲或乙站排頭有 種, 甲或乙站排尾的有 種,甲乙分別站在排頭和 排尾的有 種.,答：共有2400種不同的排列方法。,(5) 7位同學(xué)站成一排，甲、乙不能站在排頭和排尾的排法共有多少種？,單三步,（二）總體淘汰法,對于含有否定詞語的問題，還可以從總體中把不符合要求的除去，此時應(yīng)注意即不能多減又不能少減，例如在例1中，也可以用此方法解答。五個數(shù)組成三位數(shù)的全排列有 個，排好后發(fā)現(xiàn)0不能排在首位，而且3，1不能排在末尾，這兩種不合條件的排法要除去，故有30個偶數(shù)。,（三）合理分類和準(zhǔn)確分步,解含有約束條件的排列組合問題，應(yīng)按元素的性質(zhì)進(jìn)行分類，事情的發(fā)生的連續(xù)過程分步，做到分類標(biāo)準(zhǔn)明確，分步層次清楚，不重不漏。,例2.五人從左到右站成一排，其中甲不站排頭，乙不站第二個位置，那么不同的站法有（ ） A.120 B.96 C.78 D.72,分析：由題意，可先安排甲，并按其進(jìn)行分類討論：,若甲在第二個位置上，則剩下的四人可自由安排，有 種方法.,若甲在第三或第四個位置上，則根據(jù)分布計數(shù)原理，不同的站法有 種站法。,再根據(jù)分類計數(shù)原理，不同的站法共有,（四）想鄰問題捆綁法,對于某幾個元素要求相鄰的排列問題，可先將相鄰的元素“捆綁”在一起，看作一個“大”的元素，與其它元素排列，然后再對相鄰的元素內(nèi)部進(jìn)行排列。,例3）7人站成一排照相，要求甲，乙，丙三人相鄰，分別有多少種站法？,分析：先將甲，乙，丙三人捆綁在一起看作一個元素，與其余4人共有5個元素做全排列，有 種排法，然后對甲，乙，丙三人進(jìn)行全排列 由分步計數(shù)原理可得： 種不同排法,例4：七個家庭一起外出旅游，若其中四家是一個男孩，三家是一個女孩，現(xiàn)將這七個小孩站成一排照相留念。,若三個女孩要站在一起，有多少種不同的排法？,解：將三個女孩看作一人與四個男孩排隊，有 種排法，而三個女孩之間有 種排法，所以不同的排法共有： （種）。,捆綁法,單三步,若三個女孩要站在一起，四個男孩也要站在一起，有多少種不同的排法？,說一說,相鄰,變式1：七個家庭一起外出旅游，若其中四家是一個男孩，三家是一個女孩，現(xiàn)將這七個小孩站成一排照相留念。,單三步,捆綁法:,對于相鄰問題,常常先將要相鄰的元素捆綁在一起,視作為一個元素,與其余元素全排列,再松綁后它們之間進(jìn)行全排列.這種方法就是捆綁法.,單三步,（五）不相鄰問題插空法,對于某幾個元素不相鄰得排列問題，可先將其它元素排好，然后再將不相鄰的元素在已排好的元素之間及兩端的空隙之間插入即可。,例4）7人站成一排照相，要求甲，乙，丙三人不相鄰，分別有多少種站法？,分析：可先讓其余4人站好，共有 種排法，再在這4人之間及兩端的5個“空隙”中選三個位置讓甲，乙，丙插入，則有 種方法，這樣共有 種不同的排法。,若三個女孩互不相鄰，有多少種不同的排法？,解：先把四個男孩排成一排有 種排法，在每一排列中有五個空檔（包括兩端），再把三個女孩插入空檔中有 種方法，所以共有： （種）排法。,插空法,變式2：七個家庭一起外出旅游，若其中四家是一個男孩，三家是一個女孩，現(xiàn)將這七個小孩站成一排照相留念。,男生、女生相間排列，有多少種不同的排法？,解：先把四個男孩排成一排有 種排法，在每一排列中有五個空檔（包括兩端），再把三個女孩插入空檔中有 種方法，所以共有： （種）排法。,插空法,變式3：七個家庭一起外出旅游，若其中四家是一個男孩，三家是一個女孩，現(xiàn)將這七個小孩站成一排照相留念。,甲、乙兩人的兩邊必須有其他人，有多少種不 同的排法？,解：先把其余五人排成一排有 種排法，在每一排列中有四個空檔（不包括兩端），再把甲、乙插入空檔中有 種方法，所以共有： （種）排法。,插空法,變式4：七個家庭一起外出旅游，若其中四家是一個男孩，三家是一個女孩，現(xiàn)將這七個小孩站成一排照相留念。,插空法:,對于不相鄰問題,先將其余元素全排列,再將這些不相鄰的元素插入空擋中,這種方法就是插空法.,單三步,（六）順序固定問題用“除法”,對于某幾個元素順序一定的排列問題，可先將這幾個元素與其它元素一同進(jìn)行排列，然后用總的排列數(shù)除以這幾個元素的全排列數(shù).,例5五人排隊，甲在乙前面的排法有幾種？,分析：若不考慮限制條件，則有 種排法，而甲，乙之間排法有 種，故甲在乙前面的排法只有一種符合條件，故 符合條件的排法有 種.,（七）分排問題用“直排法”,把n個元素排成若干排的問題，若沒有其他的特殊要求，可采用統(tǒng)一排成一排的方法來處理.,例6七人坐兩排座位，第一排坐3人，第二排坐4人，則有多少種不同的坐法？,分析：7個人，可以在前后排隨意就坐，再無其他限制條件，故兩排可看作一排處理，所以不同的坐法有 種.,（八）實(shí)驗(yàn),題中附加條件增多，直接解決困難時，用實(shí)驗(yàn)逐步尋求規(guī)律有時也是行之有效的方法。,例7將數(shù)字1，2，3，4填入標(biāo)號為1，2，3，4的四個方格內(nèi)，每個方格填1個，則每個方格的標(biāo)號與所填的數(shù)字均不相同的填法種數(shù)有（ ）,A.6 B.9 C.11 D.23,分析：此題考查排列的定義，由于附加條件較多，解法較為困難，可用實(shí)驗(yàn)法逐步解決。,第一方格內(nèi)可填2或3或4。如填2，則第二方格中內(nèi)可填1或3或4。,若第二方格內(nèi)填1，則第三方格只能填4，第四方格應(yīng)填3。,若第二方格內(nèi)填3，則第三方格只能填4，第四方格應(yīng)填1。,同理，若第二方格內(nèi)填4，則第三方格只能填1，第四方格應(yīng)填3。因而，第一格填2有3種方法。,不難得到，當(dāng)?shù)谝桓裉?或4時也各有3種，所以共有9種。,（九）消序,例8有4名男生，3名女生高矮互不相等，先將他們排成一行，要求從左到右，女生從矮到高排列，有多少種排法？,分析：先在7個位置上任取4個位置排男生，有種排法。剩余的3個位置排女生，因要求“從矮到高”排，只有一種排法，,所以共有,（十）住店法,解決“允許重復(fù)排列問題”要注意區(qū)分兩類元素：,一類元素可以重復(fù)，另一類不能重復(fù)，把不能重復(fù)的元素看作“客”，能重復(fù)的元素看作“店”，再利用乘法原理直接求解。,例9七名學(xué)生爭奪五項冠軍，每項冠軍只能由一人獲得，獲得冠軍的可能的種數(shù)有（ ）,A. B. C D.,分析：因同一學(xué)生可以同時奪得n項冠軍，故學(xué)生可重復(fù)排列，將七名學(xué)生看作7家“店”，五項冠軍看作5名“客”，每個“客”有7種住宿法，由乘法原理得 種。,