組合計(jì)數(shù)問(wèn)題研究

1、組合計(jì)數(shù)問(wèn)題研究 高一c班 張?zhí)旌澜M合計(jì)數(shù)就是計(jì)算集合元素的個(gè)數(shù)，它是組合數(shù)學(xué)的重要組成部分。合計(jì)數(shù)理論是組合數(shù)學(xué)中一個(gè)最基本的研究方向，主要研究滿足一定條件的安排方式的數(shù)目及其計(jì)數(shù)問(wèn)題。一、常用計(jì)數(shù)方法：1、基本方法和公式：枚舉法加法原理：做一件事情，有幾種方式，在第一種方式中m種不同的方法，在第二種方式中有n種不同的方法，在最后一種方式中有r種不同的方法，那么完成這件事情共有m+n+r種不同的方法。乘法原理：做一件事情，有幾個(gè)步驟，在第一步中m種不同的方法，在第二步中有n種不同的方法，在最后一步中有r種不同的方法，那么完成這件事情共有mnr種不同的方法。遞推方法：尋求遞推公式如果一個(gè)數(shù)列的

2、第n項(xiàng)an與該數(shù)列的其他一項(xiàng)或多項(xiàng)之間存在對(duì)應(yīng)關(guān)系，這個(gè)關(guān)系就稱為該數(shù)列的遞推公式。如斐波納契數(shù)列的遞推公式為an=a（n-1）+a（n-2）；等差數(shù)列遞推公式：an=a(n-1)+d（d為公差）；等比數(shù)列遞推公式：bn=b(n-1) q （q為公比）排列組合公式：組合計(jì)算公式從n個(gè)不同元素中，任取m(mn)個(gè)元素按照一定的順序排成一列，叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)排列；從n個(gè)不同元素中，任取m(mn)個(gè)元素并成一組，叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)組合；2、其他方法：母函數(shù)（生成函數(shù)） 配對(duì)原理 子集類 歸納法 二、解題心得歸納：1、運(yùn)用加法原理或乘法原理：例題1:將編號(hào)為1

3、，2，3，4，5的五個(gè)小球放入編號(hào)為1，2，3，4，5的五個(gè)盒子中，每個(gè)盒子只放入一個(gè)，一共有多少種不同的放法？若編號(hào)為1的球恰好放在了1號(hào)盒子中，共有多少種不同的放法？若至少有一個(gè)球放入了同號(hào)的盒子中（即對(duì)號(hào)放入），共有多少種不同的放法？解答： 54321=120種4321=24種1）從五個(gè)球中選定1個(gè)球?qū)μ?hào)放入，有5種選法，其余的4個(gè)球均不對(duì)號(hào)放入，有9種放法，這樣共有59=24種放法2）從五個(gè)球中選定2個(gè)球?qū)μ?hào)放入，有10種選法，其余的3個(gè)球均不對(duì)號(hào)放入，有2種放法，這樣共有102=20種放法3）從五個(gè)球中選定3個(gè)球?qū)μ?hào)放入，有10種選法，其余的2個(gè)球均不對(duì)號(hào)放入，有1種放法，這樣共有1

4、01=10種放法3）五個(gè)球均對(duì)號(hào)放入，有1種放法總共76種不同方法例題2：正整數(shù)324000能被多少個(gè)正整數(shù)整除？多少個(gè)正偶數(shù)整除？解答：32400=253453 正整數(shù)：654=120個(gè) 正偶數(shù)：554=100個(gè)2、尋求遞推公式例題：一個(gè)樓梯共有10級(jí)臺(tái)階，規(guī)定每步可以邁一級(jí)臺(tái)階或二級(jí)臺(tái)階，最多可以邁三級(jí)臺(tái)級(jí)，從地面上到最上面一級(jí)臺(tái)階，一共可以有多少種不同的邁法？解答：從簡(jiǎn)單情況入手尋求遞推公式：（1）若有1級(jí)臺(tái)階，則只有一種邁法：a1=1；（2）若有2級(jí)臺(tái)階，則有兩種邁法，則a2=2；（3）若有3級(jí)臺(tái)階，則有4種邁法，a3=4；（4）若有4級(jí)臺(tái)階，a4=a1+a2+a3=7（種）相應(yīng)有a5

5、=a4+a2+a3=13（種） a6=a5+a4+a3=24（種） a10=a9+a8+a7=274（種）共有274種邁法3、運(yùn)用排列組合公式例題：以正十邊形的頂點(diǎn)作為三角形的頂點(diǎn) 請(qǐng)問(wèn)這樣一共可以構(gòu)成多少個(gè)銳角或鈍角三角形？解答：總共的三角形個(gè)數(shù)=120個(gè)直角三角形：在圓內(nèi)接正十邊形中以其頂點(diǎn)為端點(diǎn)的直徑共有5條，以每條直徑為斜邊的直角三角形各有8個(gè)，因此直角三角形共有40個(gè)?？梢詷?gòu)成銳角或鈍角三角形80個(gè)。三、知識(shí)拓展補(bǔ)充：生成函數(shù)（母函數(shù)）（涉及到牛頓二項(xiàng)式定理）生成函數(shù)是組合數(shù)學(xué)中尤其是計(jì)數(shù)方面的一個(gè)重要理論和工具。其實(shí)質(zhì)在于構(gòu)造這么一個(gè)多項(xiàng)式函數(shù)g(x)，使得x的n次方系數(shù)為f(n)

6、。生成函數(shù)的優(yōu)勢(shì)在于，某些生成函數(shù)可以化簡(jiǎn)為一個(gè)很簡(jiǎn)單的函數(shù)。比如：從 4個(gè)同學(xué)隨機(jī)選n個(gè)同學(xué)出來(lái)有多少種選法。學(xué)過(guò)簡(jiǎn)單的排列與組合的同學(xué)都知道，答案就是c4n。也就是說(shuō)。從n=0開始，問(wèn)題的答案分別是1,4,6,4,1,0,0,0,.。那么它的生成函數(shù)g(x)就應(yīng)該是g(x)=1+4x+6x2+4x3+x4。這不就是二項(xiàng)式展開嗎？于是，g(x)=(1+x)4。例題：我們要從蘋果、香蕉、橘子和梨中拿一些水果出來(lái)，要求蘋果只能拿偶數(shù)個(gè)，香蕉的個(gè)數(shù)要是5的倍數(shù)，橘子最多拿4個(gè)，梨要么不拿，要么只能拿一個(gè)。問(wèn)按這樣的要求拿n個(gè)水果的方案數(shù)。解答：g(x)=(1+x2+x4+.) (1+x5+x10+

7、.)(1+x+x2+x3+x4)(1+x) =.(套用等比數(shù)列通項(xiàng)和公式)=(1-x)-2 =c(1,0)+c(2,1)x+c(3,2)x2+c(4,3)x3. =1+2x+3x2+4x3+5x4+. 指數(shù)為n的系數(shù)是n+1，故n+1就是我們所求得解。四、邏輯分析推理在解決問(wèn)題中的關(guān)鍵性例題1：若有序正整數(shù)對(duì)（a,b)(ab)滿足a+b=2008，ab互質(zhì)，滿足條件的(a,b)共有多少對(duì)？解答：a + b = 2008。a 、b奇偶性相同。而a、b同為偶數(shù)時(shí)，必含有公因數(shù)2，不能互質(zhì)。因此a、b必同為奇數(shù)。比1004小的奇數(shù)總共有502個(gè)，其中2008=23251,因此舍去a=1251、325

8、1的情況，共有500對(duì)正整數(shù)對(duì)。例題2：（2010浙江高考）有4位學(xué)在同一天的上、下午參加“身高與體重”、“立定跳遠(yuǎn)”、“肺活量”、“握力”、“臺(tái)階”五個(gè)項(xiàng)目的測(cè)試，每位同學(xué)上、下午各測(cè)試一個(gè)項(xiàng)目，且不重復(fù)若上午不測(cè)“握力”項(xiàng)目，下午不測(cè)“臺(tái)階”項(xiàng)目，其余項(xiàng)目上、下午都各測(cè)試一人則不同的安排方式共有多少種（用數(shù)字作答）？解答：先安排4位同學(xué)參加上午的四項(xiàng)測(cè)試，共有a44種不同安排方式。接下來(lái)安排下午的“身高與體重”“立定跳遠(yuǎn)”“肺活量”“握力”測(cè)試。假設(shè)a、b、c同學(xué)上午分別安排的是“身高與體重”“立定跳遠(yuǎn)”“肺活量”測(cè)試，若d同學(xué)選擇“握力”測(cè)試，安排a、b、c同學(xué)分別交叉測(cè)試，有2種；若d同學(xué)選擇“身高與體重”“立定跳遠(yuǎn)”“肺活量”測(cè)試中的1種，有a31種方式，安排a、b、c同學(xué)進(jìn)行測(cè)試有3種；所以總共有安排方式a44（2+ a313）=264種綜上所述，組合計(jì)數(shù)問(wèn)題包含內(nèi)容很多而且十分有技巧性，它囊括了枚舉法、加法原理與乘法原理、排列組合、容斥