數(shù)學(xué)中組合計(jì)數(shù)的解題思想方法-精品文檔

1、數(shù)學(xué)中組合計(jì)數(shù)的解題思想方法本文探討兩個(gè)一般原理及其蘊(yùn)含的某些計(jì)數(shù)解題的公式.組合計(jì)數(shù)的解題思想方法主要有以下內(nèi)容：兩個(gè)基本的計(jì)數(shù)原理、配對原理、遞推方法、母函數(shù)等.一、兩個(gè)基本的計(jì)數(shù)原理加法原理：設(shè)集合 S 劃分為部分 S1，S2， ， Sn，則 S 的元素的個(gè)數(shù)可以通過找出他們的每一個(gè)部分的元素的個(gè)數(shù)來確定，我們把這些數(shù)相加，得到 |S|=|S1|+|S2|+ +|Sn|.乘法原理：如果一項(xiàng)任務(wù)有 p 個(gè)結(jié)果，而不論第一項(xiàng)任務(wù)的結(jié)果如何， 第二項(xiàng)任務(wù)都有 q 個(gè)結(jié)果， 那么兩項(xiàng)任務(wù)連續(xù)執(zhí)行就有 pq 個(gè)結(jié)果 . 二、配對法配對法是指對于有限集 A 與 B，如果存在集合 A 到 B 的雙射T

2、，則可以將集合A 中的元素 a 與它在 B 中的象 T（ a）配成一對，由此可以知道 |A|=|B|.【例 1】為了保密需要，一個(gè)組織組成了有11 個(gè)委員的委員會(huì)，且在保險(xiǎn)柜上加了若干把瑣. 最少應(yīng)在保險(xiǎn)柜上加多少把鎖才能保證任何6 個(gè)委員同時(shí)到場就可以開瑣，而任何 5 個(gè)委員都不能開瑣？解：設(shè) x=（x1，x2，x3，x4，x5）是從 11 個(gè)委員中抽取出的 5 個(gè). 由題意知，必有一把鎖不能被x 打開，不妨設(shè)u 是這樣一把鎖 . 我們作映射f ：xu. 下面證明f 是單射，否則設(shè)f （ x）=f （y）=u，xy，則 xy中至少有 6 個(gè)人，但是他們都不能打開鎖 u，矛盾 . 所以 f 是

3、單射 . 于是至少要加C511 把鎖 .【例 2】從 n 種物體中取出k 件，同一種物體可以重復(fù)且同一種物體不加區(qū)別，問有多少種取法？解：其與方程x1+x2+xn=k 的非負(fù)整數(shù)解的個(gè)數(shù)Cn-1n+k-1 是一樣的 .三、遞推法遞推法的解題流程：計(jì)算一些初始值a1，a2，a3建立 an與前面的項(xiàng)之間的關(guān)系求解一般公式.【例 3】在正方形內(nèi)部有n 個(gè)點(diǎn)，它們并上正方形的四個(gè)頂點(diǎn)為集合 M.現(xiàn)在把這個(gè)正方形剪成一些三角形，使得每個(gè)三角形的頂點(diǎn)都是M中的點(diǎn)，且除了頂點(diǎn)為三角形的點(diǎn)，其他位置都不含有 M中的點(diǎn)，問能剪出多少個(gè)三角形？解：這樣的題目應(yīng)先對n 比較小的時(shí)候試驗(yàn)， 找出一般的遞推法 . 容易

4、看到 f （ 1）=4， f （2）=6， f （n+1）=f （n） +2. 由此容易得到結(jié)論 .【例 4】已知 f （ 0）=0，f （ 1）=0，f （ 2n）=2f （n）+1，f（ 2n+1） =f （ 2n）-1 ，求最小的 m，使得 f （m）=21990+1.解： f （2n）=2f （n）+1，f （ 2n+1）=2f （n）表明：當(dāng) n 是奇數(shù)時(shí)， f （n）是偶數(shù)；當(dāng) n 是偶數(shù)時(shí)， f （n）是奇數(shù) .21990+1 是奇數(shù)，則 m是偶數(shù) . 不妨設(shè) m=2n1，則有 f （ n1）=21989. 于是n1 是奇數(shù)，設(shè)n1=2n2+1，f （n2）=21988.四、母函數(shù)法用母函數(shù)解題的關(guān)鍵是要理解母函數(shù)的組合意義.【例 5】投一次骰子出現(xiàn)1，2，3，4，5，6 的概率各是 1/6 ，問連續(xù)投 10 次，使得其出現(xiàn)的點(diǎn)數(shù)之和為30 的概率是多少？解：用母函數(shù)來解，設(shè)f （ x）=x+x2+x3+x4+x5+x6. 容易看到，連續(xù)投10 次，其點(diǎn)數(shù)之和為30 的方法數(shù)是 f （ x）10=（ x+x2+x3+x4+x5+x6） 10 的展開式中 x30 的系數(shù)，經(jīng)計(jì)算得到該系數(shù)是 2930455. 于是所求的