汪定國(guó)

（重慶師范大學(xué) 數(shù)學(xué)學(xué)院，重慶 400047）

關(guān)于組合數(shù)學(xué)教學(xué)的一點(diǎn)注記

汪定國(guó)

（重慶師范大學(xué) 數(shù)學(xué)學(xué)院，重慶 400047）

組合數(shù)學(xué)作為離散數(shù)學(xué)的一個(gè)分支，是理工科專業(yè)尤其是數(shù)學(xué)專業(yè)的大學(xué)生必須學(xué)習(xí)的一門課程。本文結(jié)合自己多年的教學(xué)實(shí)踐，對(duì)組合數(shù)學(xué)的教學(xué)作了一些探討。

組合數(shù)學(xué)；教學(xué)；組合思想

組合數(shù)學(xué)作為離散數(shù)學(xué)的一個(gè)分支，其內(nèi)容駁雜，方法繁多，對(duì)長(zhǎng)期接受連續(xù)型數(shù)學(xué)的初學(xué)者而言，往往感到抓不住要領(lǐng)。然而，多種組合思想方法之間并不是孤立的，它們緊密聯(lián)系，相輔相成。在教學(xué)過(guò)程中，將各種思想方法能夠串在一起，對(duì)于組合數(shù)學(xué)的學(xué)習(xí)、組合思維的培養(yǎng)會(huì)十分有益。排列組合、容斥原理、遞推關(guān)系以及生成函數(shù)是本科組合數(shù)學(xué)中比較重要的教學(xué)內(nèi)容，同時(shí)也是解決組合問題時(shí)常用的幾種組合思想方法。本文通過(guò)利用這幾種思想方法解決同一個(gè)組合問題，以此表明這幾種方法之間的統(tǒng)一性與差異性，對(duì)組合數(shù)學(xué)的教學(xué)和學(xué)習(xí)進(jìn)行一個(gè)簡(jiǎn)單探討。問題：由0、1、2三個(gè)數(shù)字作成的含有偶數(shù)個(gè)0的n位數(shù)碼的個(gè)數(shù)是多少？

一、利用組合分析法求解

組合分析法即為在證明組合恒等式或解決組合問題時(shí)不是進(jìn)行代數(shù)推導(dǎo)，而是對(duì)組合恒等式或組合問題所代表的組合意義進(jìn)行分析，通過(guò)建立一一對(duì)應(yīng)的方法說(shuō)明等式兩邊或兩個(gè)組合問題恰好是對(duì)同一個(gè)組合模型進(jìn)行計(jì)數(shù)。在教學(xué)時(shí)，一定要講清組合分析法的本質(zhì)，同時(shí)要指明應(yīng)用組合分析法的關(guān)鍵是建立一一對(duì)應(yīng)關(guān)系的兩邊一定描述的是同一個(gè)組合模型。問題的求解：將所有的n位數(shù)碼分成兩組：①只含2的n位數(shù)碼為一組，組中只有一個(gè)n位數(shù)碼，它不出現(xiàn)數(shù)碼0，0是偶數(shù)。②至少含一個(gè)0或者1的n位數(shù)碼為另一組，組中共有3n-1個(gè)n位數(shù)碼。在這組數(shù)碼中，按2出現(xiàn)的模式再分成一些類，因在每一類的數(shù)碼中，0出現(xiàn)偶數(shù)次的數(shù)碼占一半，故這一組中0出現(xiàn)偶數(shù)次的數(shù)碼共有。由①、②可知，0出現(xiàn)偶數(shù)次的數(shù)碼總數(shù)共有個(gè)。

二、利用容斥原理求解

容斥原理的基本形式的應(yīng)用具有一定的局限性，在教學(xué)時(shí)，有必要介紹容斥原理的一般形式以及更廣泛的應(yīng)用。設(shè)n元集S，具有性質(zhì)集P={P1，P2，…，Pm}。現(xiàn)在問題是求出集S中恰好具有P中r個(gè)，性質(zhì)的元素個(gè)數(shù)N（r）（0≤r≤m）。令（m）=N（P1，P2，…，Pm）。其中N（P1，P2，…，Pm）表示同時(shí)具有性質(zhì)P1，P2，…，Pm的元素個(gè)數(shù)。若記W（r）表示S中至少具有r（1≤r≤m）個(gè)性質(zhì)的元素個(gè)數(shù)，首先有以下的容斥原理的一般形式：定理1：N（r）=W（r）-，其中0≤r≤m。同時(shí)，還可以很容易得到以下結(jié)論：定理2：設(shè)E（x）=N（0）+N（1）x+N（2）x2+…+N（m）xm，則：由此定理不難得到一個(gè)推論：設(shè)n元集S={x1，x2，…，xn}的元有性質(zhì)集P={P1，P2，…，Pm}，則S中具有偶數(shù)個(gè)性質(zhì)的元素個(gè)數(shù)為：N（0）+N（2）+N（4）+…=W（0）；S中具有奇數(shù)個(gè)性質(zhì)的元素個(gè)數(shù)為。利用這些結(jié)論，可以得到上述問題應(yīng)用容斥原理的解決方法。問題的求解：設(shè)由0，1，2三個(gè)數(shù)字作成的全體n位數(shù)碼的集合為S，則|S|=3n。又設(shè)Pi表示n位數(shù)碼中的第i個(gè)位置為0，（i=1，2，…，n）。那么因?yàn)椋?，恰具有偶?shù)個(gè)0的n位數(shù)碼的數(shù)目為：N（0）+N（2）+N（4）+… =W（0）

三、利用遞推關(guān)系求解

給定一個(gè)數(shù)列H（0），H（1），…，H（n），…，（或H{（n）}），如果存在若干項(xiàng)之間的關(guān)系式（等式），從某個(gè)非負(fù)整數(shù)n起都有效，這個(gè)關(guān)系式叫做遞推關(guān)系。針對(duì)一個(gè)實(shí)際問題，在教學(xué)時(shí)，應(yīng)該強(qiáng)調(diào)遞推關(guān)系的建立是正確解決相關(guān)組合問題的關(guān)鍵。問題的求解：用f（n）表示由0、1、2組成的且0出現(xiàn)偶數(shù)次的n位數(shù)碼的個(gè)數(shù)，n=1，2，…，顯然f（1）=2。當(dāng)n≥2時(shí)，將這樣的f（n）個(gè)n位數(shù)碼分為以下兩類。

1.第1個(gè)位置不是0的這樣的n位數(shù)碼為一類，這時(shí)，第1個(gè)位置必是1或2，有兩種選擇，而后面的n-1位只要是0出現(xiàn)偶數(shù)次的n-1位數(shù)碼即可，故這一類共有2f（n-1）個(gè)。

2.第一個(gè)位置是0的這樣的n位數(shù)碼為另一類，這時(shí)后面的n-1位只要是0出現(xiàn)奇數(shù)次的n-1位數(shù)碼即可，故這一類共有：3n-1-f（n-1）個(gè)，（后n-1位任取0、1、2共3n-1個(gè)n位數(shù)碼，f（n-1）表示0出現(xiàn)偶數(shù)次的n-1位數(shù)碼）。所以由加法原理，得：f（n）=2f（n-1）+3n-1-f（n-1）=f（n-1）+3n-1，規(guī)定f（0）=1，得遞推關(guān)系：。解這個(gè)遞推關(guān)系：f（n）=f（n-1）+3n-1=f（n-2）+3n-2+3n-1=f（n-3）+3n-3+3n-2+3n-1，用歸納法證明：當(dāng)n=0時(shí)=1；當(dāng)n=1時(shí)，f（1）=，結(jié)論均成立。設(shè)當(dāng)n=k時(shí)結(jié)論成立，下證n=k+1時(shí)：f（k+1）=f（k） +3k=，所以當(dāng)n=k+1時(shí)結(jié)論也成立。

四、利用生成函數(shù)求解

冪級(jí)數(shù)是良好的數(shù)學(xué)工具。冪級(jí)數(shù)的系數(shù)形成的序列與冪級(jí)數(shù)是一一對(duì)應(yīng)的。如果兩個(gè)冪級(jí)數(shù)之間存在某種關(guān)系，那么相應(yīng)的兩個(gè)系數(shù)系列也必然存在一定得關(guān)系。組合分析中的許多問題可以歸結(jié)為求一個(gè)與n有關(guān)的數(shù)H（n），即本質(zhì)是求一個(gè)未知序列{H（n）}。在教學(xué)時(shí)，應(yīng)該指出利用生成函數(shù)解決問題的關(guān)鍵，即合理的構(gòu)造相應(yīng)地生成函數(shù)，再將問題轉(zhuǎn)化為求生成函數(shù)中某項(xiàng)的系數(shù)問題。問題的求解：設(shè)an表示由0、1、2組成的且0出現(xiàn)偶數(shù)次的n位數(shù)碼的個(gè)數(shù)。規(guī)定a0=1，則{an}的指數(shù)型生成函數(shù)為

作為本科數(shù)學(xué)專業(yè)的學(xué)生，組合數(shù)學(xué)主要學(xué)習(xí)組合計(jì)數(shù)的思想方法，而排列組合、容斥原理、遞推關(guān)系以及生成函數(shù)都能解決組合計(jì)數(shù)的相關(guān)問題，從而體現(xiàn)了它們之間的統(tǒng)一性，這也是能夠同時(shí)利用它們解決同一計(jì)數(shù)問題的原因。但是使用不同的方法解決問題時(shí)，所表現(xiàn)出的難易程度又有差別，這又體現(xiàn)了這些方法之間的差異性。對(duì)于一個(gè)實(shí)際問題，究竟采用什么方法，這就需要根據(jù)實(shí)際情況而定。但我們?cè)诮虒W(xué)與學(xué)習(xí)的過(guò)程中，一題多解是掌握這些方法的一條很好的途徑。

[1]陳敬華.關(guān)于組合數(shù)學(xué)的若干基本思想方法[J].湖北師范學(xué)院學(xué)報(bào)（自然科學(xué)版），2001，21（2）：86-89.

[2]曲婉玲.組合數(shù)學(xué)[M].北京：北京大學(xué)出版社，1989.

[3]匡正.組合數(shù)學(xué)習(xí)題精解[M].哈爾濱：哈爾濱工業(yè)大學(xué)出版社，2005.

G642.41

A

1674-9324（2014）01-0095-02

重慶師范大學(xué)青年基金資助項(xiàng)目（2011XLQ29）。

汪定國(guó)（1976-），男，講師，主要從事圖論，組合數(shù)學(xué)的研究。