第3章 問(wèn)題求解(第1節(jié) 組合數(shù)學(xué)初步)

第三章11772[n]pnp亦延用至今。按此法，nPnn!。nHrm2nmnN＝m1＋m2＋m3＋…＋mnm1×m2×m3×…×mnn排列：從nm(m≤n)個(gè)元素，按照一定的順序排成一列，叫做nmnPmn

(n組合：從nm(m≤n)nmnm(m≤n)個(gè)元素，C(n,k)P(5,5)種站法；4*4*P(4,4)種站法；P(5,5)+4*4*P(4,4)種站法。3*P(4,4)種方法。4*P(4,4)P(4,4)+3*P(4,4)+4*P(4,4)+P(3,3)*P(4,4)=312(1分析：（1）7P(7,7)*2-P(6,6)*2*2P(5,2)。763例：求方程的正整數(shù)解的個(gè)例：求方程的非負(fù)整數(shù)解的個(gè)數(shù)Catalan個(gè)三角形，設(shè)所有滿足條件的方案數(shù)是，定義，求。我們?cè)噲D找出，數(shù)列就是著名的Catalan數(shù)列，在組合數(shù)學(xué)的許多問(wèn)題上都有很重要的應(yīng)用Catalan數(shù)列的遞推關(guān)系正如上式，再加上一點(diǎn)生成函數(shù)的知識(shí)就可以推導(dǎo)出它的通項(xiàng)公《IntroductoryCombinatoricsRichardA．Brualdi）78CatalanCatalan定理：n個(gè)+1和n個(gè)-1構(gòu)成的2n項(xiàng)，并且其部分和滿knCatalann+1n10，則稱其為可接受的，否則個(gè)數(shù)。我們嘗試計(jì)算出的值和的值以得到的值任意一個(gè)有n112n對(duì)于任意一個(gè)不可接受的數(shù)列中一定存在一個(gè)最小的k，使得Catalan（2由乘法原理可知這個(gè)問(wèn)題滿足遞推關(guān)系（1Catalan分析：2、3n1n1總數(shù)（模型的轉(zhuǎn)換希望讀者認(rèn)真思考Catalan有n2StirlingStirling數(shù)的相關(guān)知識(shí)完全略去，請(qǐng)有興趣的讀者參考《組合數(shù)學(xué)》《IntroductoryCombinatorics，RichardABrualdi）822S(n,k)k*S(n-1,k)S(n-1,k-1)；S(n,1)=1（n≥1），S(n,n)=1n-1nk*S(n-1,k)。StirlingS(6,3)n=3231312設(shè)表示i這個(gè)數(shù)在原來(lái)位置上的排列的集合，則錯(cuò)位排列的個(gè)現(xiàn)在我們來(lái)算n-1C(n,1)*(n-1)!=n!種情況。1k，k>1外的n-1個(gè)數(shù)的一個(gè)錯(cuò)位排列，方案數(shù)為。事實(shí)上在n較小的時(shí)候，計(jì)算更多的是通過(guò)遞推關(guān)系而不是通項(xiàng)公式，但是通項(xiàng)公72（沒有兒子的結(jié)點(diǎn)分析：設(shè)S表示二叉樹的結(jié)點(diǎn)總數(shù)，表示有i個(gè)兒子的結(jié)點(diǎn)的個(gè)數(shù)。兩次計(jì)算結(jié)果相互對(duì)照可以得出，于是例題的答案是8CAC化的技巧得到了的值。nn+12k+1令，如果n個(gè)籠子至少有個(gè)鴿子。k-11112證明：令表示第123此外，，而且由于每周下棋最多是12盤，即。因此，我們有此外，序列也是一個(gè)嚴(yán)格遞增的序列154j+1，j+2，j+3，……，i21列T中的數(shù)之和恰好為9，那么n的最小值是 設(shè)表示前i個(gè)數(shù)的和，并規(guī)定，事實(shí)上原題要求出最小的n，使得存滿足。于是我們可以把S數(shù)組看做鴿子，用不能同時(shí)取的一組（即9{20,29}{21,30}{22,31}{23,32}{24}{25}{26}n=18（S19）一定滿足條件。n=17下不合法的序列：111111111011111111。n18SGf[N]Nf[N]可以轉(zhuǎn)移f[N-1]到f[N-M]，f[N]就必勝否則必?cái)　?2，SG1。SG函數(shù)后我們之前遞推判斷必勝必?cái)〉囊?guī)則也可用于#include<iostream>usingnamespacestd;constintNUM=5;intr(intn){inti;if(n<=NUM)returnn;for(i=1;i<=NUM;i++)if(r(n-i)<0)returni;return-1;}intintn; return0;}輸入輸出 4。Nim的SG函數(shù)為。根據(jù)SG函數(shù)的定義舉一個(gè)簡(jiǎn)單的例子，axorb=cbxorc=aaxorc=b下面我們用反證法進(jìn)行證明，假設(shè)存在一個(gè)狀態(tài)的SG函數(shù)和它的一個(gè)后繼狀態(tài)的SG ，即除xorx數(shù)就是它本身，于是可知，從而x=0，與游戲者不能不取的條件矛盾，故原命Nim替x作為第k堆的石子數(shù)之后所有石子堆的石子數(shù)xor的值為0于是我們只需證明s1cxorx1所以我們甚至無(wú)需繼續(xù)比較就可以得出結(jié)論：例題【NOIP2006普及組】現(xiàn)有5堆石子,石子數(shù)依次為3，5，7，19，50，甲乙兩人輪 3^5^7^19^50=32>0，所以當(dāng)前的狀態(tài)是必勝態(tài)，先手有必勝策略。而石子的個(gè)數(shù)中，5061，50xor3218G=(V,E)是一個(gè)無(wú)向圖，如果頂jiinA,jinB)，Gxy x(7-x)x12。順序排列，每次可以交換任意兩個(gè)元素，最少需要交換（）次。A．4B．5C．64，于是做一次交換。此時(shí)序列變成{-5，4，23，16，77，8，53，100}。然X1NX其中，用行列式可以表示k-1N-置換環(huán)的個(gè)數(shù)。ij，iji>