【文章內(nèi)容簡介】 C(m,n)C(mn,0)=C(m,n)C(n,n) 由上知：左邊=[C(n,0)+C(n,1)+ … +C(n,n)]C(m,n) 由 =C(n,0) +C(n,1) +C(n,2) +…+C(n,n) ()nxy?nx1ny?2nxy?ny 令 x=y=1 可得 C(n,0) +C(n,1) +C(n,2) +…+C(n,n)= 左邊=2 nC(m,n)=右邊 命題得證。n 題 從 n 個人中選 r 個圍成一圓圈，問有多少種不同的方案？解：圓排列:共有 P(n,r)/r 種不同的方案。 題 在由 n 個 0 及 n 個 1 構(gòu)成的字符串中，在任意前 k 個字符中，0 的個數(shù)不少于 1 的個數(shù)的字符串有多少？解：轉(zhuǎn)化為格路問題(弱領(lǐng)先條件 ),即從(0,0)到(n,n),只能從對角線上方走 ,可以碰到對角線,故方案數(shù)為 C(2n,n)C(2n,n1。 題 (a) 按照 的要求，寫出鄰位對換法（排列的生成算法之二）的相應算法 .(b) 寫出按照鄰位對換法由給定排列生成其下一個排列的算法.解：1：給定排列求相應序號：設 Int I 為每一排列的對應序號 I=1 （初始化）假定 A[1：n] 和 E[2：n]；D[2：n] ；B[1：n]都是整數(shù)數(shù)組，其中 B[1：n]為給定序列123S[] []1 q0 A[nBI1 kiiDiES???： 從 到 作始 ， ， 終 ；： ； 判 斷 ： 是 否 與 ： 相 等若 相 等 則 輸 出 值否 則 ；： 從 降 到 作始 []kE[]。 p[k]。p 1 0 [], q ???若 則 作否 則 作始 若 則 作始 終2 p。rA[p]。[1]。 [1] S 否 則 作始 轉(zhuǎn) 終終終2：給定序號求相應排列：設 Int I 為每一排列的對應序號 I=1 （初始化） M 為給定序列號 M=N假定 A[1：n] 和 E[2：n]；D[2：n] ；都是整數(shù)數(shù)組123S[] [][]1 q0 I i1nA[i] kAiniDiEiMS???： 從 到 作始 ， ， 終 ；： ； 判 斷 是 否 與 相 等若 相 等 則 從 到 輸 出 ；否 則 ；： 從 n2 D[]kE[]。 pD[k]。p 0 []1, q ???降 到 作始 若 則 作否 則 作始 若 則 作始 終2 p。rA[p]。[1]。 [] S ?否 則 作始 轉(zhuǎn) 終終終(a) 由給定排列生成其下一個排列的算法 。轉(zhuǎn)指 向 ；大 的 數(shù) 一 律 改 變 箭 頭 的比： 數(shù) 互 換 位 置 。和 它 箭 頭 所 指 一 側(cè) 相 鄰，設 為 的 數(shù) 值 最 大 者 ，求 處 于 活 動 狀 態(tài) 各 數(shù) 中： 停 止 。中 無 一 處 于 活 動 狀 態(tài) 則若 在：生 成 下 一 個 排 列從 排 列 1211 S m p? ?? 題 對于給定的正整數(shù) N，證明，當 時，C(N,K)是最大值。12NK???????或 若 是 奇 數(shù) 若 是 偶 數(shù)證明：要證明 C（N，K）是最大值，只需證明 C（N，K）大于 C（N，K1 ）即可根據(jù)以往證明大小值的經(jīng)驗，可以用相減或是相除的方法來證明，就此題，相減不合適，采用相除可以消除等式中的一些項C（N，K）/ C（N，K1）=（N ！/K！（NK）?。?（（K1）?。∟K+1）！/N！） =（NK+1 ）/K當 n 為偶數(shù)，k=n/2 時 （ NK+1）/K=（（n+2）/n ）* （2/n ）=（n+2）/n 19當 n 為奇數(shù),k=(n1)/2 時 （ NK+1）/K=((n+3)/2) * (2/(n1))=1+4/(n1) 1當 n 為奇數(shù), k=(n+1)/2 時 （NK+1）/K=((n+1)2) * (2/(n+1)) =1綜上所述,當 n 取以上三種情況, C（N，K）取最大值 題 證明在由字母表{0,1,2}生成的長度為 n 的字符串中. (a) 0 出現(xiàn)偶數(shù)次的字符串有 個；312n?(b) ，其中 . nnnq?????????????????2q?????證：(a)歸納法：當 n=1 時,0 出現(xiàn)偶數(shù)次的字符串有 (31+1)/2=2 個(即 1,2),成立。假設當 n=k 時,0 出現(xiàn)偶數(shù)次的字符串有(3 k+1)/2 種。總的字符串有 3 種。0 出現(xiàn)奇數(shù)次的字符串有(3 k1)/2 種。當 n=k+1 時，0 出現(xiàn)偶數(shù)次的字符串包括兩部分：n=k 時,0 出現(xiàn)偶數(shù)次再增加一位不是 0 的，共有 2(3k+1)/2 種，0 出現(xiàn)奇數(shù)次再增加一位 0,共有(3 k1)/2 種。所以共有 2(3k+1)/2+(3k1)/2=(3k+1+1)/2 種，證畢。(b) 等式左邊第 m 項是 0 出現(xiàn) m 次的字符串數(shù)，總和就是 0 出現(xiàn)偶數(shù)次的字符串數(shù)，右邊由(a)得是 0 出現(xiàn)偶數(shù)次的字符串數(shù)，兩邊顯然相等。 題 （a）用組合方法證明 和 都是整數(shù)。 （b）證明 是整數(shù)。n2)!(n3? )!(12n?解：(a) ①方法一：因為： 所以!)12(!)(???n !)12(!2)?????nnn是整數(shù)，因此 是整數(shù)。!)12(!??nn2!方法二：設有 2n 個不同球放入 n 個不同的盒子里，每盒兩個，這個方案數(shù)應該是整數(shù)。對 2n 個球進行排列得到方案數(shù)為(2n)!。而把 2 個球放入同一個盒子里不計順序，應該把全排列數(shù)除掉這些重復計算的次數(shù)，n 個盒子內(nèi)部的排列共重復計算了 2 次。得到 2n 個不同球放入 n 個不同的盒子里，每盒兩個的方案數(shù) n2)!(②若有 3n 個不同的球,放入 n 個不同盒子,每個盒子放三個，這個方案應該是整數(shù)。對這 3n 個球進行排列得到方案數(shù)為(3n)!。而把 3 個球放入同一個盒子里不計順序，應該把全排列數(shù)除掉這些重復計算的次數(shù)，n 個盒子內(nèi)部的排列共重復計算了 3！次。得到 3n 個不同的球放入 n 個不同的盒子里，每盒三個的方案數(shù) nn23)!(!??(b) 有 個不同的球，放入 n 個相同的盒子里，每盒 n 個，求方案數(shù)，方案數(shù)應該是一個整數(shù)。2按前面(a)的方法，應該得到(n 2)!/(n!)n 是整數(shù)。另外由于 n 個盒子相同，放入不同的盒子是沒有區(qū)別的，應該把 n 個盒子的排列數(shù) n!除去。因此得到(n 2)!/(n!)n+1 是整數(shù)。 題 在 1 到 n 的自然數(shù)中選取不同且互不相鄰的 k 個數(shù),有多少種選取方案？ 解: 設從 1n 中選取互不相鄰的 k 個數(shù)的方案為 g(n,k)。若選 n，則方案為 g(n2,k1),若不選 n,則方案數(shù)位 g(n1,k).顯然 g(n,k)=g(n2,k1)+g(n1,k)，且只有當 n≥2k1 時,g(n,k)0,否則 g(n,k)=0,可給定初始值 g(2k1,k)=1,g(2k2,k)=0. 題 (a) 在 2n 個球中，有 n 個相同. 求從這 2n 個球中選取 n 個的方案數(shù).(b) 在 3n+1 個球中，有 n 個相同 . 求從這 3n+1 個球中選取 n 個的方案數(shù).解(a）：有 n 個相同就有 n 個不相同取 n 個不相同和 0 個相同的為 C(n,n), 取 n1 個不相同的球和 1 個相同的球為 C(n,n1)，等等。所以總的方案數(shù)為 ????nCC2,1, ???解(b）：方法同上，方案數(shù)為 ??C,02??10由于 C(2n+1,0)=C(2n+1,2n+1),… ,C(2n+1,n)=C(2n+1,n+1)??????12,121,20,12 ????nnCnCn?則 2n? 題 5 臺教學機器 m 個學生使用，使用第一臺和第二臺的人數(shù)相等，有多少種分配方案？解：當使用第 1 臺機器的學生為 n 個時，使用第 2 臺機器的學生也為 n,從 m 個學生中選出 2n 個使用這兩臺機器，剩余的學生可以任意使用剩下的機器的組合數(shù)為 C(m,2n)C(2n,n)3(m2n)。所以總的方案數(shù)為 ????????23),2(,0)2(qCqnnm 題 (1)在有 5 個 0，4 個 1 組成的字符串中，出現(xiàn) 01 或 10 的總次數(shù)為 4 的字符串，有多少個？(2)在有 m 個 0，n 個 1 組成的字符串中，出現(xiàn) 01 或 10 的總次數(shù)為 k 的字符串，有多少個？解：(1)、先將 5 個 00000 排成一排，1 若插在兩個 0 中間，即： “010”則出現(xiàn) 2 個“01”或“10”；若插在兩端，則出現(xiàn) 1 個“01”或“10”；要使出現(xiàn)“01”， “10”總次數(shù)為 4，有兩種辦法：把兩個 1 插入 0 的空當內(nèi)，剩下的 1 插入 1 的后面（類似 010111000） 。把 1 個 1 插入 0 的空當，再取兩個 1 分別插入兩端，剩下的 1 插入 1 的前面。 （類似 10100011） 。由 1 和 2 得： 30*3424??C(2)、m 個 0 產(chǎn)生 m1 個空當。若 k 為偶數(shù)時：要得到出現(xiàn)“01”與“10”總次數(shù)為 k，可以先按上題中 1 的情況討論，則在 m1 個空當中分別插入個 1 即可，也就是 。剩下的 1 如何插入的問題與書 P20 頁的定理 類似(在 n 個不同元素中取 r 個允許重復21km?的組合，其組合數(shù)為（C（n+r1,r)） ，在這里無區(qū)別的球的個數(shù)也就是剩下的 1 的個數(shù)（即 n ） ，盒子的個數(shù)也就是2k插入到 m1 個空當中的 1 的個數(shù)(即 )，則得出剩下的 1 的插入方法有 。即第一種情況的總的插入方法為：2k 21knC?。212*knkm?同理可得，按 2 的情況討論后的第二種情況的總的插入方法為： 。212*??knkm1 和 2 得總的插入方法為： 。21212**????knkmnkmCC若 k 為奇數(shù)時：則必有且只有一個 1 插入字符串的頭或尾,剩下的 1 按照 1 的方法插入,只有這樣才能使 k 為奇數(shù)。所以插入的總方法為： 。212??knkm 題 從 N={1,2,…,20}中選出 3 個數(shù)，使得沒有兩個數(shù)相鄰，問有多少種方案？解：相當于從 N={1,2,…,20}個數(shù)中取 3 個作不相鄰的組合，故方案數(shù)為 C(203+1,3)=C(18,3)種 題 從 s={1,2, n}中連取 k 個數(shù)，使之沒有兩個數(shù)相鄰，求不同方案數(shù)。?解：在 n 個數(shù)中選 k 個數(shù)，使之沒有兩個數(shù)相鄰，相當于在 nk+1 位置中插入 k 個數(shù)，k 個數(shù)中沒有倆個數(shù)相鄰。有 種方案。有定理 直接可得。!)1(1Ckn????? 題 把 n 個無區(qū)別的球放進有標志 1，2，…，n 的 n 個盒子中，每個盒子可放多于一個球，求有多少種方案？解：把 n 個無標志的球放進 n 個有標志的盒子中，每個盒子允許多于一個球是允許重復的組合所以是=????????1???211 題 .m 個 1，n 個 0 進行排列，求 1 nm.解：相當于 n 個 0 排列后,使 m 個 1 做不相鄰的插入，共產(chǎn)生 n+1 1 插入有 n+1 種情況，第二個是 n 種情況…第 m 個 1 插入就有 nm+1 種情況。所以是（n+1） （n） （n1）…（nm+1） ，即此題解為 pn+1 m。 題 偶數(shù)位的對稱數(shù)，即從左向右讀法與從優(yōu)向左的讀法相同，如 3223。試證這樣的數(shù)可被 11 整除。證明： 根據(jù)所有偶數(shù)位置上的數(shù)字及所有奇數(shù)位置上的數(shù)字分別相加，再求出兩個和的差，如果所得的差能被 11 整除，那么這個整數(shù)必能被 11 整除。例如 12344321，偶數(shù)位上是：2，4，3，1。奇數(shù)位上是：1，3，4，2因為對稱數(shù)是偶數(shù)個，所以偶數(shù)為相加與奇數(shù)為相加的和是相等的，他們的差是零，而零能能被任何數(shù)整除，所以原題成立。證畢。 題 n 個男人與 n 個女人沿一圓桌坐下，問兩個女人之間坐 1 個男人的方案數(shù)。又 m 個女人 n 個男人，且mn，沿一圓桌坐下，求無兩個女人并坐的方案數(shù)。解：根據(jù)題意，兩個女人之間坐 1 個男人的方案數(shù) Q (n,n)* P(n,n)無兩個女人并坐的方案數(shù) Q (n,n)* P (n,m) 題 n 個人分別沿著兩張圓坐下，一張 r 人，另一張個 nr 人，試問有多少種不同的方案數(shù)？ 解： C（n,r）*(r1)!(nr1)! 題 一圓周上 n 個點標以 。每一點與其它 n1 個點連以直線，試問這些直線交于圓內(nèi)有多少點？n,2?解：這些直線交于圓內(nèi)有 C（ n,4）個點每 4 個點形成矩形，其對角線有一個交點，故圓內(nèi)交點有： )3(2)1(413)()(),( ?????n因為四個點連在一起構(gòu)成一個四邊形，這個四邊形的對角線相交于一個點，求這些直線交于圓內(nèi)多少點就是求這些點能構(gòu)成幾個四邊形，即轉(zhuǎn)化為從 n 個點取出四個進行組合 題 求序列{ 0，1，8，27， }的母函數(shù)。3n? ?解：由序列可得到 233() nGxx???? ?因為 231n?? ? 1()39。 4xx?? ?設 23139。 ()npx x???? ? 22[()]39。1x??? ?設 23139。 ()nnqxxx?? ? 3 23[()]39。 (1)nx????? ?23139。 nx x? ?由以上推理可知 =[()]39。qx,[7*94(6)],n? ?所以可通過求得 得到序列的母函數(shù)：39。 324Gxx??2321()()[()]6nHxFdxx????? 題 已知序列 ，求母函34,n??????????????????? ? 數(shù)12解： 3*214(3