排列組合問題的若干解題策略.ppt

排列組合問題的若干解題策略,一，相鄰問題-整體捆綁法,例1，7名學(xué)生站成一排，甲已必須站在一起，有多少種方法？,捆綁法：要求某幾個(gè)元素必須排在一起的問題，可以用捆綁法來解決問題。即將需要相鄰的元素合并為一個(gè)元素，再與其他元素一起作排列，同時(shí)要注意合并元素內(nèi)部也可以做排列。一般地：n個(gè)人站成一排，其中某m個(gè)人相鄰，可用“捆綁法”解決，共有 種排法,二，不相臨問題選空插入法,插入法：對(duì)于某兩個(gè)元素或者幾個(gè)元素要求不相鄰的問題，可以用插入法，即先選好沒有限制條件的元素，然后將有限制條件的元素按要求插入排好元素的空擋之中即可。若n個(gè)人站成一排，其中m個(gè)人不相鄰，可用插空法解決，共有 種排法,練習(xí)：學(xué)校組織老師學(xué)生一起看電影，同一排電影票12張。8個(gè)學(xué)生，4個(gè)老師，要求老師在學(xué)生中間，且老師互不相鄰，共有多少種不同方法？,三；特殊元素優(yōu)先考慮法,例3；1名老師和4名獲獎(jiǎng)學(xué)生排成一排照相留念，若老師不排在兩端，則共有多少種不同的排法？,練習(xí)；乒乓球隊(duì)的10名隊(duì)員中有3名主力隊(duì)員，派5名隊(duì)員參加比賽，3名主力隊(duì)員要安排在一、三、五位置，其余7名隊(duì)員選2名安排在二、四位置，那么不同的出場安排共有多少種？,對(duì)于含有限定條件的排列組合問題，可以考慮優(yōu)先安排特殊位置，然后再考慮其他位置的安排。,四；排除法,例4；6個(gè)人站成一排，若甲不站在排頭也不站在排尾，有多少種不同排法？,練習(xí)；6個(gè)人站成一排，若甲不站在排頭，已不在排尾，有多少種不同排法？,排列的問題有時(shí)比較復(fù)雜，特別是分類時(shí)，所以有時(shí)可以從所有的排列中，把不符合的排列剔除，這樣的解題方法叫排除法。,典型例題,例一；用0、1、2、3、4、5這五個(gè)數(shù)字，組成沒有重復(fù)數(shù)字的三位數(shù)，其中偶數(shù)有多少個(gè)？,典型例題,例二；A、B、C、D、E五人并排站成一排，如A、B必相鄰，且B在A右邊，那么不同的排法有多少種？,分析；將特殊元素A、B按B在A的右邊“捆綁”看成一個(gè)大元素，與另外三個(gè)元素全排列，由A、B不能交換，故不在松綁，所以共有 種排法,典型例題,練1；5人成一排，要求甲、已相鄰，有幾種排法？,練2；5名學(xué)生和3名老師站成一排照相，3名老師必須站在一起的不同排法共有多少種？,練3；計(jì)劃展出不同的畫10幅，其中一幅水彩畫、4幅油畫、5幅國畫，排成一行陳列，要求同一品種的畫必須連在一起，并且水彩畫不能放在兩端，那么不同的陳列方式有多少種？,典型例題,練習(xí)4；7人站成一行，如果甲、已兩人不相鄰，則不同的排法種數(shù)是多少？,練習(xí)5；要排一個(gè)有6個(gè)歌唱節(jié)目和4個(gè)舞蹈節(jié)目的演出清單，任何兩個(gè)舞蹈不相鄰，有多少種不同排法？,練習(xí)6；由數(shù)字0、1、2、3、4、5組成沒有重復(fù)數(shù)字的六位數(shù)，其中個(gè)位數(shù)字小于十位數(shù)字的共有多少個(gè)？,三；復(fù)雜問題-總體排除法或排異法,例3；正六邊形的中心和頂點(diǎn)共7個(gè)點(diǎn)，以其中3個(gè)點(diǎn)為頂點(diǎn)的三角形共有多少個(gè)？,練習(xí)；班里有43個(gè)同學(xué)從中任抽5人，正、副班長、團(tuán)支部書記至少有一人在內(nèi)的抽法有多少種？,有些問題直接法考慮比較難比較復(fù)雜，或分類不清或多種時(shí)，而他的反面往往比較簡潔，可考慮用排除法，先求