有關(guān)排隊(duì)問題的排列組合題解法舉例

有關(guān)排隊(duì)問題的排列組合題解法舉例例1:三個(gè)女生和五個(gè)男生排成一排（1） 如果女生必須全排在一起，可有多少種不同的排法？（2） 如果女生必須全分開，可有多少種不同的排法？（3） 如果兩端都不能排女生，可有多少種不同的排法？（4） 如果兩端不能都排女生，可有多少種不同的排法？解：（1）（捆綁法）因?yàn)槿齻€(gè)女生必須排在一起，所以可以先把她們看成一個(gè)整體，這樣同五個(gè)男生合一起共有六個(gè)元素，然成一排有種不同排法.對(duì)于其中的每一種排法，三個(gè)女生之間又都有對(duì)種不同的排法，因此共有種不同的排法.（2） （插空法）要保證女生全分開，可先把五個(gè)男生排好，每兩個(gè)相鄰的男生之間留出一個(gè)空檔.這樣共有4個(gè)空檔，加上兩邊兩個(gè)男生外側(cè)的兩個(gè)位置，共有六個(gè)位置，再把三個(gè)女生插入這六個(gè)位置中，只要保證每個(gè)位置至多插入一個(gè)女生，就能保證任意兩個(gè)女生都不相鄰.由于五個(gè)男生排成一排有種不同排法，對(duì)于其中任意一種排法，從上述六個(gè)位置中選出三個(gè)來讓三個(gè)女生插入都有種方法，因此共有種不同的排法.（3） 解法1:（位置分析法）因?yàn)閮啥瞬荒芘排詢啥酥荒芴暨x5個(gè)男生中的2個(gè)，有種不同的排法，對(duì)于其中的任意一種排法，其余六位都有種排法，所以共有種不同的排法.解法2：（間接法）3個(gè)女生和5個(gè)男生排成一排共有種不同的排法，從中扣除女生排在首位的種排法和女生排在末位的種排法，但這樣兩端都是女生的排法在扣除女生排在首位的情況時(shí)被扣去一次，在扣除女生排在未位的情況時(shí)又被扣去一次，所以還需加一次回來，由于兩端都是女生有種不同的排法，所以共有種不同的排法.解法3：(元素分析法)從中間6個(gè)位置中挑選出3個(gè)來讓3個(gè)女生排入，有種不同的排法，對(duì)于其中的任意一種排活，其余5個(gè)位置又都有種不同的排法，所以共有種不同的排法，解法1：因?yàn)橹灰髢啥瞬欢寂排?，所以如果首位排了男生，則未位就不再受條件限制了，這樣可有種不同的排法；如果首位排女生，有種排法，這時(shí)末位就只能排男生，有種排法，首末兩端任意排定一種情況后，其余6位都有種不同的排法，這樣可有種不同排法.因此共有種不同的排法.解法2：3個(gè)女生和5個(gè)男生排成一排有種排法，從中扣去兩端都是女生排法種，就能得到兩端不都是女生的排法種數(shù).因此共有種不同的排法.說明：解決排列、組合應(yīng)用問題最常用也是最基本的方法是位置分析法和元素分析法.若以位置為主，需先滿足特殊位置的要求，再處理其它位置，有兩個(gè)以上約束條件，往往是考慮一個(gè)約束條件的同時(shí)要兼顧其它條件.若以元素為主，需先滿足特殊元素要求再處理其它的元素.間接法有的也稱做排除法或排異法，有時(shí)用這種方法解決問題來得簡(jiǎn)單、明快.捆綁法、插入法對(duì)于有的問題確是適用的好方法，要認(rèn)真搞清在什么條件下使用.例27名同學(xué)排隊(duì)照相.⑴若分成兩排照，前排3人，后排4人，有多少種不同的排法？⑵若排成兩排照，前排3人，后排4人，但其中甲必須在前排，乙必須在后排，有多少種不同的排法？（3）若排成一排照，甲、乙、丙三人必須相鄰，有多少種不同的排法？3名女生，⑷若排成一排照，7人中有4名男生，女生不能相鄰，有多少種不面的排法？3分析：（1）可分兩步完成：第一步，從7人中選出3人排在前排，有A7種排法；第二步，347剩下的4人排在后排，有A4種排法，故一共有A7種排法.事實(shí)上排兩排與排成A4A77一排一樣，只不過把第4~7個(gè)位子看成第二排而已，排法總數(shù)都是A7，相當(dāng)于7個(gè)人的4全排列.（2）優(yōu)先安排甲、乙.（3）用“捆綁法〃.（4）用“插空法〃.解：（1）A7A4A75040種.⑵第一步安排甲，有A3種排法；第二步安排乙，有A4種排法；第三步余下的5人排在5剩下的5個(gè)位置上，有A5種排法，由分步計(jì)數(shù)原理得，符合要求的排法共有115AAA1440種.1347⑶第一步，將甲、乙、丙視為一個(gè)元素，有其余4個(gè)元素排成一排，即看成5個(gè)元素的53全排列問題，有A5種排法；第二步，甲、乙、丙三人內(nèi)部全排列，有A3種排法.由分步計(jì)53數(shù)原理得，共有A5A720種排法.4(4)第一步，4名男生全排列，有A4種排法；第二步，女生插空，即將3名女生插入4名3男生之間的5個(gè)空位，這樣可保證女生不相鄰，易知有A5種插入方法.由分步計(jì)數(shù)原理得，43符合條件的排法共有：AA1440種.說明：(1)相鄰問題用"捆綁法〃，即把若干個(gè)相鄰的特殊元素"捆綁〃為一個(gè)"大元素〃，與其他普通元素全排列；最后再“松綁〃，將這些特殊元素進(jìn)行全排列.⑵不相鄰問題用"插空法〃，即先安排好沒有限制條件的元素，然后再將有限制條件的元素按要求插入排好的元素之間.例3八個(gè)人分兩排坐，每排四人，限定甲必須坐在前排，乙、丙必須坐在同一排，共有多少種安排辦法？解法1：可分為“乙、丙坐在前排，甲坐在前排的八人坐法〃和“乙、丙在后排，甲坐在前排的八人坐法〃兩類情況.應(yīng)當(dāng)使用加法原理，在每類情況下，劃分"乙丙坐下〃、"甲坐下〃；“其他五人坐下〃三個(gè)步驟，又要用到分步計(jì)數(shù)原理，這樣可有如下算法：215215AAAA4A4A58640（種）.解法2：采取“總方法數(shù)減去不命題意的所有方法數(shù)〃的算法.把“甲坐在第一排的八17人坐法數(shù)〃看成“總方法數(shù)”，這個(gè)數(shù)目是A4.在這種前提下，不合題意的方法是“甲A711115坐第一排，且乙、丙坐兩排的八人坐法.”這個(gè)數(shù)目是A4.其中第一個(gè)因數(shù)CTOC\o"1-5"\h\zAAA5111表示甲坐在第一排的方法數(shù)，C2表示從乙、丙中任選出一人的辦法數(shù)，A3表示把選出A4的這個(gè)人安排在第一排的方法數(shù)，下一個(gè)A4則表示乙、丙中沿未安排的那個(gè)人坐在第二排5的方法數(shù)，A5就是其他五人的坐法數(shù)，于是總的方法數(shù)為1711115A4A7A4CTOC\o"1-5"\h\zAAA8640（種）.1例4一條長椅上有7個(gè)座位，4人坐，要求3個(gè)空位中，有2個(gè)空位相鄰，另一個(gè)空位與2個(gè)相鄰空位不相鄰，共有幾種坐法？分析：對(duì)于空位，我們可以當(dāng)成特殊元素對(duì)待，設(shè)空座梯形依次編號(hào)為1、2、3、4、5、6、7.先選定兩個(gè)空位，可以在1、2號(hào)位，也可以在2、3號(hào)位〃共有六種2號(hào)，則另一空位可以在4、可能，再安排另一空位，此時(shí)需看到，如果空位在1、5、6、7號(hào)7號(hào)位，亦如此.如果相鄰空位在2、3號(hào)位，另一空位可位，有4種可能，相鄰空位在6、4號(hào)，4、5號(hào)，5、6號(hào)亦如此，所以必以在5、6、7號(hào)位，只有3種可能，相鄰空位在3、須就兩相鄰空位的位置進(jìn)行分類.本題的另一考慮是，對(duì)于兩相鄰空位可以用合并法看成一個(gè)元素與另一空位插入已坐人的4個(gè)座位之間，用插空法處理它們的不相鄰.解答一：就兩相鄰空位的位置分類：42或6、7,共有24A4若兩相鄰空位在1、192（種）坐法.43,3、4,4、5或5、6,共有43A4若兩相鄰空位在2、 288（種）不同坐法，所以所有坐法總數(shù)為192288480（種）.解答二：先排好4個(gè)人，然后把兩空位與另一空位插入坐好的4人之間，共有42AA480（種）不同坐法.解答三：本題還可采用間接法，逆向考慮在所有坐法中去掉3個(gè)空位全不相鄰或全部相4鄰的情況