數(shù)學中組合計數(shù)的解題思想方法

蔣科新

[摘要]探討數(shù)學中一些組合計數(shù)的解題思想方法，有兩個基本的計數(shù)原理、配對法、遞推方法、母函數(shù)法等.

[關鍵詞]組合計數(shù)解題思想方法計數(shù)原理

[中圖分類號]G633.6[文獻標識碼]A[文章編號]16746058（2015）290040

本文探討兩個一般原理及其蘊含的某些計數(shù)解題的公式.

組合計數(shù)的解題思想方法主要有以下內容：兩個基本的計數(shù)原理、配對原理、遞推方法、母函數(shù)等.

一、兩個基本的計數(shù)原理

加法原理：設集合S劃分為部分S1，S2，…，Sn，則S的元素的個數(shù)可以通過找出他們的每一個部分的元素的個數(shù)來確定，我們把這些數(shù)相加，得到|S|=|S1|+|S2|+…+|Sn|.

乘法原理：如果一項任務有p個結果，而不論第一項任務的結果如何，第二項任務都有q個結果，那么兩項任務連續(xù)執(zhí)行就有pq個結果.

二、配對法

配對法是指對于有限集A與B，如果存在集合A到B的雙射T，則可以將集合A中的元素a與它在B中的象T（a）配成一對，由此可以知道|A|=|B|.

【例1】為了保密需要，一個組織組成了有11個委員的委員會，且在保險柜上加了若干把瑣.最少應在保險柜上加多少把鎖才能保證任何6個委員同時到場就可以開瑣，而任何5個委員都不能開瑣？

解：設x=（x1，x2，x3，x4，x5）是從11個委員中抽取出的5個.由題意知，必有一把鎖不能被x打開，不妨設u是這樣一把鎖.我們作映射f：x→u.下面證明f是單射，否則設f（x）=f（y）=u，x≠y，則x∪y中至少有6個人，但是他們都不能打開鎖u，矛盾.所以f是單射.于是至少要加C511把鎖.

【例2】從n種物體中取出k件，同一種物體可以重復且同一種物體不加區(qū)別，問有多少種取法？

解：其與方程x1+x2+…+xn=k的非負整數(shù)解的個數(shù)Cn-1n+k-1是一樣的.

三、遞推法

遞推法的解題流程：計算一些初始值a1，a2，a3→建立an與前面的項之間的關系→求解一般公式.

【例3】在正方形內部有n個點，它們并上正方形的四個頂點為集合M.現(xiàn)在把這個正方形剪成一些三角形，使得每個三角形的頂點都是M中的點，且除了頂點為三角形的點，其他位置都不含有M中的點，問能剪出多少個三角形？

解：這樣的題目應先對n比較小的時候試驗，找出一般的遞推法.容易看到f（1）=4，f（2）=6，f（n+1）=f（n）+2.由此容易得到結論.

【例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ù)解題的關鍵是要理解母函數(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.于是所求的概率為2930455610≈0.0485.

【例6】設n≥2是自然數(shù)，兩個自然數(shù)集合{a1，a2，…，an}≠{b1，b2，…，bn}，而集合{ai+aj|i

{bi+bj|i

.（這里的i，j均為大于2的自然數(shù)）

求證：存在自然數(shù)h，使得n=2h.

證明：設f（x）=aa1+xa2+…+xan，g（x）=xb1+xb2+…+xbn.于是由條件有f（x）2-

f（x2）=g（x）2-g（x2）f（x）2-g（x）2=f（x2）-g（x2）

.又容易看到，

f（1）-g（1）=0（x-1）=f（x）-g（x）

.設f（x）-g（x）=（x-1）kp（x），p（1）≠0.于是有

f（x）2-g（x）2=f（x2）-g（x2）=（x2-1）kp（x2），

所以f（x）+g（x）=（x2-1）kp（x2）f（x）-g（x）=（x+1）kp（x2）p（x）.

令x=1，我們有2n=

2kp（1）p（1）=2kn=2k-1.

【例7】有紅、白、黑3種球各一個，每次允許重復地取出5個球，要求紅色球至多選兩次，白球至多選3次，黑球至多選1次，問有多少種不同的取法？

解：用1+x+x2表示紅球，1+x+x2+x3表示白球，1+x表示黑球.則問題即為（1+x+x2+x3）（1+x+x2）（1+x）中x5的系數(shù)，即有2種不同的取法.

（責任編輯鐘偉芳）