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

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

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

3、單射 . 于是至少要加C511 把鎖 .【例 2】從 n 種物體中取出k 件，同一種物體可以重復且同一種物體不加區(qū)別，問有多少種取法？解：其與方程x1+x2+xn=k 的非負整數(shù)解的個數(shù)Cn-1n+k-1 是一樣的 .三、遞推法遞推法的解題流程：計算一些初始值a1，a2，a3建立 an與前面的項之間的關(guān)系求解一般公式.【例 3】在正方形內(nèi)部有n 個點，它們并上正方形的四個頂點為集合 M.現(xiàn)在把這個正方形剪成一些三角形，使得每個三角形的頂點都是M中的點，且除了頂點為三角形的點，其他位置都不含有 M中的點，問能剪出多少個三角形？解：這樣的題目應先對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）表明：當 n 是奇數(shù)時， f （n）是偶數(shù)；當 n 是偶數(shù)時， f （n）是奇數(shù) .21990+1 是奇數(shù)，則 m是偶數(shù) . 不妨設 m=2n1，則有 f （ n1）=21989. 于是n1 是奇數(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)的點數(shù)之和為30 的概率是多少？解：用母函數(shù)來解，設f （ x）=x+x2+x3+x4+x5+x6. 容易看到，連續(xù)投10 次，其點數(shù)之和為30 的方法數(shù)是 f （ x）10=（ x+x2+x3+x4+x5+x6） 10 的展開式中 x30 的系數(shù)，經(jīng)計算得到該系數(shù)是 2930455. 于是所求的