常見(jiàn)的一些排列、組合模式和解法

#1111P*P*P*P6982排列按照元素的排列方式又可分為三種排列⑴線排列；⑵圓排列；⑶重排列。一、線排列：先考察一個(gè)簡(jiǎn)單的問(wèn)題，有紅、藍(lán)、白三只球，要放到編號(hào)為1，2，?，10的十個(gè)盒子中，如果每個(gè)盒子只能裝一只球，問(wèn)把球放到盒子中的不同放法的種類。分析：每次放一只球，不妨依此順序：放紅球T放藍(lán)球T放白球。放紅球的方法有10種(紅球可放在10個(gè)盒子的任一個(gè)中)放藍(lán)球的方法有9種(紅球可放在9個(gè)盒子的任一個(gè)中)放白球的方法有8種(紅球可放在8個(gè)盒子的任一個(gè)中)根據(jù)乘法原理：這些球的不同放法總共有10X9X8=720(種)根據(jù)上例，不難推廣到一般，得到線排列的定義：從n個(gè)不同的元素中，取r個(gè)按次序排列，稱為從n中取r個(gè)排列，記為P(n,r)。顯然，P(n,r)=n(n-1)(n-2)???(n-r+1)=n!/(n-r)!其中，當(dāng)r=0時(shí)，一個(gè)元素也不取，算作是取0個(gè)元素的一種排列，即P(n,0)=1；當(dāng)r=n時(shí)，有P(n,n)=n!，即n的全排列；而把0<r<n的情況稱為選排列。［例］在五天之內(nèi)安排三次考試，且不允許一天內(nèi)有兩次考試，那末一共有多少種安排法？解：不妨把三次考試看作是三只顏色不同的球，五天看作是五個(gè)編號(hào)不同的盒子，P(5,3)=5x4x3=60［思考］確定各位數(shù)中不重復(fù)的四位十進(jìn)制數(shù)的個(gè)數(shù)。、圓排列：從集合S={a「a2,a3,…,a}的n個(gè)不同元素中，取出r個(gè)元素按照某種次序(如逆時(shí)針)排成一個(gè)圓圈，稱這樣的排列為圓排列。氣週屯…牛,週屯…牛％a3a4^ana1a25毎氣週…％-!需要注意的是，一個(gè)圓排列旋轉(zhuǎn)可得另一個(gè)圓排列，這兩個(gè)圓排列是相同的，例如取出r個(gè)元素氣週屯…牛,週屯…牛％a3a4^ana1a25毎氣週…％-!這r個(gè)線排列在圓排列中只能算一個(gè)。一個(gè)圓排列可以產(chǎn)生r個(gè)線排列，而總共有P(n,r)個(gè)線排列，因此圓排列的個(gè)數(shù)為：P(n,r)/r=n!/(r(n-1)!)［例］有8人圍圓桌就餐，問(wèn)有多少種就座方式？如果有兩人不愿坐在一起，又有多P(8,8)8P(8,8)8二7!(種)少種就座方式？解：n=8,r=8,因此8人圍圓桌就餐的就座方式有：設(shè)不愿坐在一起的兩人為甲和乙。不妨考慮甲乙坐在一起時(shí)的情況。此時(shí)，相當(dāng)于7人圍桌而坐,其就坐方式為7!/7（n=7,r=7）。而甲乙坐在一起又有兩種情況，這樣，甲和乙坐在一起時(shí)共有2X6!種就坐方式。因此，甲和乙不坐在一起的就座方式共有：7!-2X6!=3600（種）三、重排列：前面討論的是從n個(gè)互不相同的元素組成的集合S=｛a「a2,…,aj中選r個(gè)元素進(jìn)行排列、在每種排列中每個(gè)元素至多只出現(xiàn)一次的情況。現(xiàn)在考慮允許重復(fù)出現(xiàn)的情況，即考慮在重集S=｛中］,k2?a2,…,/aj中選r個(gè)元素進(jìn)行排列。根據(jù)重復(fù)數(shù)k1，k2，?,kn是否趨向I重排列又可分為無(wú)限重排列和有限重排列。1．無(wú)限重排列：考查把三個(gè)不同顏色的球放在十個(gè)不同的盒子中問(wèn)題。若每個(gè)盒子能容納的球的只數(shù)無(wú)限，那么，藍(lán)球和白球也能像紅球一樣放入十個(gè)盒子中的任一個(gè)，所以放置的方法總數(shù)是：10X10X10=103=1000（種）一般地，從n個(gè)不同元素中取r個(gè)按次序排列，若每個(gè)元素?zé)o限次重復(fù)（即k1=k2=?=k=-），則稱排列為無(wú)限次排列，其排列數(shù)等于nr。"［例］無(wú)線電收發(fā)報(bào)機(jī)有‘?’和‘一’（短、長(zhǎng)）兩種信號(hào)，用四個(gè)信號(hào)代表一個(gè)阿拉伯?dāng)?shù)碼，問(wèn)可以表示多少個(gè)不同碼？解：對(duì)無(wú)線電收發(fā)報(bào)機(jī)來(lái)說(shuō)，有兩種信號(hào)，取四個(gè)表示一個(gè)數(shù)碼，這是一種重排列：四個(gè)信號(hào)：□□□□每個(gè)信號(hào)兩種表示：?—………因此，總共可以表示不同的數(shù)碼個(gè)數(shù)是：24=16（個(gè)）這樣，對(duì)于十進(jìn)制記數(shù)法中只有十個(gè)不同的數(shù)碼是完全夠用了。同理，通用明碼用四個(gè)數(shù)碼表示一個(gè)漢字，可以表示出的漢字個(gè)數(shù)為104=10000。若不允許重復(fù)，四個(gè)十進(jìn)制碼僅能表示P（10,4）=5040個(gè)漢字，顯然是不夠的。2．有限重排列：若允許元素有限次重復(fù)，那S=｛匕牛,k2?a2,…,叫叫｝（ki#^），則從所有元素中取r個(gè)有次序排列的種數(shù)又如何計(jì)算呢？［例］有兩只紅球、一只藍(lán)球和一只白球放到編號(hào)不同的十個(gè)盒子中去的方法總數(shù)是多少？解：將兩只紅球分別涂成深紅色和淺紅色，使之能區(qū)別，于是問(wèn)題轉(zhuǎn)化為四只不同顏色的球放到十個(gè)盒子中去的方法種數(shù)是：P（io,4）=5040。在這5040種方法中,若不區(qū)分紅球的深淺，那么兩種方法變成一種方法，因此，兩只紅球、一只藍(lán)球和一只白球放入十個(gè)編號(hào)不同的盒子的方法種數(shù)有：5040/2=2520。一般地，把r只彩色球放到n個(gè)編號(hào)不同的盒子中去的方法種數(shù)是：P（n,r）r!r!...r!i2t其中，ri表示第i種彩球有ri只，i=1,2，3,…，t,且有r=r1+r2Hrt。當(dāng)r=n時(shí)，有：n!n!...n!12t其中，n1表示n1個(gè)相同元素，…,叫表示nt個(gè)相同元素且有片+出叫=n。［思考］某市區(qū)中的一處棋盤形街道，有南北方向街道（縱街）5條，東西方向街道（橫街）8條，見(jiàn)下圖，某人從東南角走到西北角，要按最短路徑走（就是只能向西或向北走），共有幾種走法？南

附：第三屆全國(guó)青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題（初中組競(jìng)賽用時(shí)：3小時(shí)）―、設(shè)有一個(gè)N*M方格的棋盤（1WNW100,1WMW100）。（30%）求出該棋盤中包含有多少個(gè)正方形、多少個(gè)長(zhǎng)方形（不包括正方形）例如：當(dāng)N=2，M=3時(shí)：正方形的個(gè)數(shù)有8個(gè)，即邊長(zhǎng)為1的正方形有6個(gè)；邊長(zhǎng)為2的正方形有2個(gè)。a

bc

de

其中：a?i分別表示1,2,…，9中的一個(gè)數(shù)字，并要求滿足下列條件：⑴a<f<i；⑵b<d，g<h，c<e；⑶a+b+d+f=f+g+h+i=i+e+c+a=P程序要求：根據(jù)輸入的邊長(zhǎng)P，輸出所有滿足上述條件的三角形的個(gè)數(shù)及其中的一種方案。三、設(shè)有一個(gè)N*M（1WNW50,1WMW50）的街道（如下圖）：（40%）北東南B(9,5)A(1,北東南B(9,5)A(1,1)規(guī)定行人從A出發(fā)，在街道上只能向東或向北方向行走。如下為N=3,M=3的街道圖，從A出發(fā)到達(dá)B共有6條可供走的路徑:B(N,M)A5A2A—A1—A2—A5—B(N,M)A5A2A—A1—A4—A5—BA—A1—A4—A7—BA—A3—A4—A5—BA—A3—A4—A7—BA—A3—A6—A7—B若在N*M的街道中，設(shè)置一個(gè)矩形障礙區(qū)域（包括圍住該區(qū)域的街道）不讓行人通過(guò)，如上圖中用“*”表示的部分。此矩形障礙區(qū)域用2對(duì)頂點(diǎn)坐標(biāo)給出，圖中的2對(duì)頂點(diǎn)