排列組合中分球問(wèn)題

排列組合中分球問(wèn)題南京師大附中徐安西給定m個(gè)相同的球，將這m個(gè)球放入n不同的盒子，不允許盒子為空，其不同的放置總數(shù)為S〔m,n〕。分析與解：我們也可以這樣理解這個(gè)問(wèn)題，即把一個(gè)數(shù)m分成n份，使得這n份之和為m。例如把5分成2份那么有以下幾種分法：5=1+4=2+3=3+2=4+1;我們就可以看成5個(gè)球排成一排，要求分成2局部，那么只要在5個(gè)球中間4個(gè)位置選1個(gè)位置插入擋板〔如下圖〕，就可以分成2局部。共有C(m-1,n-1)種方法。給定m個(gè)相同的球，將這m個(gè)球放入n不同的盒子，允許盒子為空，其不同的放置總數(shù)為S〔m,n〕。方法一：假設(shè)只有一個(gè)盒子裝球，那么有C〔n,1〕種。假設(shè)有二只盒子裝球，盒子的取法有C(n,2)種，把m個(gè)球分成2份有C(m-1,1)種，所以共有C(n,2)*C(m-1,1)種。假設(shè)有三只盒子裝球，盒子的取法有C(n,3)種，把m個(gè)球分成3份有C(m-1,2)種，所以共有C(n,3)*C(m-1,2)種。以此類推，共有：C〔n,1〕+C(n,2)*C(m-1,1)+C(n,3)*C(m-1,2)+…+C(n,n)*C(m-1,n-1)。種。方法二：用擋板插入的方法：由于允許為空，所以可以在m個(gè)球的左側(cè)增加n個(gè)空位〔如圖：m=5,n=6〕。這樣我們可以吧以下的圖分成n-1份，共有C(m+n-1,n-1)種方法三：我們假設(shè)有m+n個(gè)相同的球，把它放入n個(gè)盒子，并且不允許為空，所以為C(m+n-1,n-1)種，我們也可以這樣思考，n個(gè)盒子，不允許為空，那么我就把每個(gè)盒子里放入一個(gè)球，共用掉n個(gè)球，剩下m個(gè)球可以隨便的放。由于最底層都是1個(gè)球，去掉這一層后放置方案的種數(shù)和剩下m個(gè)球可以隨便的放的種數(shù)相同。所以為C(m+n-1,n-1)。給定m個(gè)有不同標(biāo)號(hào)的球，標(biāo)號(hào)依次為1、2、3、…、m。將這m個(gè)球放入n個(gè)相同的盒子，不允許盒子為空，其不同的放置總數(shù)為S〔m,n〕。例如：S〔4,2〕=7。求：S〔7,4〕=方法一：我們考慮最后一個(gè)球的放置方法，它分為兩種情況，第一種情況為該球獨(dú)占一個(gè)盒子，那么其它的球有S〔m-1,n-1〕種方法。第二種情況那么為沒(méi)有空盒子，那么它必須在n個(gè)盒子中挑出一個(gè)放入，這種情況那么有n*S〔m-1,n〕種方法，所以得到遞推公式為S〔m,n〕=S〔m-1,n-1〕+n*S〔m-1,n〕。我們可以遞推出一個(gè)三角形：在上面的三角形中，有如下特點(diǎn)：=1\*GB3①左右兩邊都為1，第幾行就有幾個(gè)數(shù)，比方第五行有5個(gè)數(shù)1***1.=2\*GB3②S〔m,n〕=S〔m-1,n-1〕+n*S〔m-1,n〕在三角形中可表示為第m行第n個(gè)數(shù)等于m-1行中第n-1個(gè)數(shù)+n乘以m-1行中的第n個(gè)數(shù)。例如S(7,3)=S(6,2)+3*S(6,3)=31+270=301.方法二：因?yàn)槭窍嗤暮凶?，就是將m個(gè)不同的球分成n份。這樣當(dāng)m=7,n=4時(shí)有這樣幾種分法：第一種：分為4，1，1，1第二種：分為3，2，1，1第三種：分為2，2，2，1所以第一種分法有C(7,4)=35種，第二種分法有C(7,3)*C(4,2)=210種，第三種分法有C(7,2)*C(5,2)*C(3,2)/P(3,3)=105種。所以S〔7，4〕=350種。給定m個(gè)有不同標(biāo)號(hào)的球，標(biāo)號(hào)依次為1、2、3、…、m。將這m個(gè)球放入n個(gè)相同的盒子，允許盒子為空，其不同的放置總數(shù)為S〔m,n〕。分析：由于允許為空，我們就可以把問(wèn)題分解成n-1個(gè)子問(wèn)題。=1\*GB3①就是一個(gè)也不允許為空，方法總數(shù)為F〔m,n〕=F〔m-1,n-1〕+n*F〔m-1,n〕。=2\*GB3②只有一個(gè)空箱，所以問(wèn)題就變成了m個(gè)不同的球放入n-1個(gè)相同的盒子，不允許盒子為空，方案總數(shù)為F〔m,n-1〕=F(m-1,n-2)+(n-1)*F(m-1,n-2).=3\*GB3③只有2個(gè)空箱，所以問(wèn)題就變成了m個(gè)不同的球放入n-2個(gè)相同的盒子，不允許盒子為空。以此類推方案數(shù)為S(m,n)=F(m,n)+F(m,n-1)+…+F(m,2)+F(m,1)。其中F(m,n)表示給定m個(gè)有不同標(biāo)號(hào)的球，標(biāo)號(hào)依次為1、2、3、…、m。將這m個(gè)球放入n個(gè)相同的盒子，不允許盒子為空的方案總數(shù)。F〔m,n〕=F〔m-1,n-1〕+n*F〔m-1,n〕給定m個(gè)有不同標(biāo)號(hào)的球，標(biāo)號(hào)依次為1、2、3、…、m。將這m個(gè)球放入n個(gè)不同的盒子，允許盒子為空，其不同的放置總數(shù)為S〔m,n〕。分析：根據(jù)分步計(jì)算，第一個(gè)球有n種放置方法，第二球也有n種放置方法，以此類推共有NM種方法給定m個(gè)有不同標(biāo)號(hào)的球，標(biāo)號(hào)依次為1、2、3、…、m。將這m個(gè)球放入n個(gè)不同的盒子，不允許盒子為空，其不同的放置總數(shù)為S〔m,n〕。分析：我們假設(shè)盒子是相同的，那么此題和第三題是一樣的，由于盒子不同，所以增加了P〔N，N〕種。方案總數(shù)S(m,n)=N!*F(m,n)，其中F〔m,n〕=F〔m-1,n-1〕+n*F〔m-1,n〕給定m個(gè)相同的球，將這m個(gè)球放入n相同的盒子，允許盒子為空，其不同的放置總數(shù)為S〔m,n〕。分析與解：對(duì)于n〔1〕n=1，那么只有1種。設(shè)為F(m,1)〔2〕n=2，那么有[m/2]+1種。設(shè)為F(m,2)〔3〕n=3,我們假設(shè)箱子里的球是從小到多排序好的。第一個(gè)箱子球?yàn)?，那么有F(m,2)種。第一個(gè)箱子為1，那么有F(m-3,2)種。如果第一個(gè)箱子為2，那么有F(m-3*2,2)種。由此可以得到F(m，n)=F(m，n-1)+F(m-n,n-1)+F(m-2*n,n-1)+…+F(m-n*k,n-1).其中m-n*k>=0;F(m,1)=1,F(m,2)=m/2+1;測(cè)試數(shù)據(jù)F(20，4)=108方法二：枚舉法我們可