關于組合數學教學的一點注記

摘要：組合數學作為離散數學的一個分支，是理工科專業尤其是數學專業的大學生必須學習的一門課程。本文結合自己多年的教學實踐，對組合數學的教學作了一些探討。

關鍵詞：組合數學；教學；組合思想

中圖分類號：G642.41 文獻標志碼：A 文章編號：1674-9324（2014）01-0095-02

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

一、利用組合分析法求解

組合分析法即為在證明組合恒等式或解決組合問題時不是進行代數推導，而是對組合恒等式或組合問題所代表的組合意義進行分析，通過建立一一對應的方法說明等式兩邊或兩個組合問題恰好是對同一個組合模型進行計數。在教學時，一定要講清組合分析法的本質，同時要指明應用組合分析法的關鍵是建立一一對應關系的兩邊一定描述的是同一個組合模型。問題的求解：將所有的n位數碼分成兩組：①只含2的n位數碼為一組，組中只有一個n位數碼，它不出現數碼0，0是偶數。②至少含一個0或者1的n位數碼為另一組，組中共有3n-1個n位數碼。在這組數碼中，按2出現的模式再分成一些類，因在每一類的數碼中，0出現偶數次的數碼占一半，故這一組中0出現偶數次的數碼共有■。由①、②可知，0出現偶數次的數碼總數共有1+■=■個。

二、利用容斥原理求解

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

三、利用遞推關系求解

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

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

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

四、利用生成函數求解

冪級數是良好的數學工具。冪級數的系數形成的序列與冪級數是一一對應的。如果兩個冪級數之間存在某種關系，那么相應的兩個系數系列也必然存在一定得關系。組合分析中的許多問題可以歸結為求一個與n有關的數H（n），即本質是求一個未知序列{H（n）}。在教學時，應該指出利用生成函數解決問題的關鍵，即合理的構造相應地生成函數，再將問題轉化為求生成函數中某項的系數問題。問題的求解：設an表示由0、1、2組成的且0出現偶數次的n位數碼的個數。規定a0=1，則{an}的指數型生成函數為：fe（x）=（1+■+■+…）（1+x+■+■+■+…）2=e2x·■=■（e3x+ex）=■（■3n■+■■）=■■·■

從而，an=■ （n=0，1，2，…）。

作為本科數學專業的學生，組合數學主要學習組合計數的思想方法，而排列組合、容斥原理、遞推關系以及生成函數都能解決組合計數的相關問題，從而體現了它們之間的統一性，這也是能夠同時利用它們解決同一計數問題的原因。但是使用不同的方法解決問題時，所表現出的難易程度又有差別，這又體現了這些方法之間的差異性。對于一個實際問題，究竟采用什么方法，這就需要根據實際情況而定。但我們在教學與學習的過程中，一題多解是掌握這些方法的一條很好的途徑。

參考文獻：

[1]陳敬華.關于組合數學的若干基本思想方法[J].湖北師范學院學報（自然科學版），2001，21（2）：86-89.

[2]曲婉玲.組合數學[M].北京：北京大學出版社，1989.

[3]匡正.組合數學習題精解[M].哈爾濱：哈爾濱工業大學出版社，2005.

基金項目：重慶師范大學青年基金資助項目（2011XLQ29）。

作者簡介：汪定國（1976-），男，講師，主要從事圖論，組合數學的研究。endprint

摘要：組合數學作為離散數學的一個分支，是理工科專業尤其是數學專業的大學生必須學習的一門課程。本文結合自己多年的教學實踐，對組合數學的教學作了一些探討。

關鍵詞：組合數學；教學；組合思想

中圖分類號：G642.41 文獻標志碼：A 文章編號：1674-9324（2014）01-0095-02

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

一、利用組合分析法求解

組合分析法即為在證明組合恒等式或解決組合問題時不是進行代數推導，而是對組合恒等式或組合問題所代表的組合意義進行分析，通過建立一一對應的方法說明等式兩邊或兩個組合問題恰好是對同一個組合模型進行計數。在教學時，一定要講清組合分析法的本質，同時要指明應用組合分析法的關鍵是建立一一對應關系的兩邊一定描述的是同一個組合模型。問題的求解：將所有的n位數碼分成兩組：①只含2的n位數碼為一組，組中只有一個n位數碼，它不出現數碼0，0是偶數。②至少含一個0或者1的n位數碼為另一組，組中共有3n-1個n位數碼。在這組數碼中，按2出現的模式再分成一些類，因在每一類的數碼中，0出現偶數次的數碼占一半，故這一組中0出現偶數次的數碼共有■。由①、②可知，0出現偶數次的數碼總數共有1+■=■個。

二、利用容斥原理求解

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

三、利用遞推關系求解

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

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

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

四、利用生成函數求解

冪級數是良好的數學工具。冪級數的系數形成的序列與冪級數是一一對應的。如果兩個冪級數之間存在某種關系，那么相應的兩個系數系列也必然存在一定得關系。組合分析中的許多問題可以歸結為求一個與n有關的數H（n），即本質是求一個未知序列{H（n）}。在教學時，應該指出利用生成函數解決問題的關鍵，即合理的構造相應地生成函數，再將問題轉化為求生成函數中某項的系數問題。問題的求解：設an表示由0、1、2組成的且0出現偶數次的n位數碼的個數。規定a0=1，則{an}的指數型生成函數為：fe（x）=（1+■+■+…）（1+x+■+■+■+…）2=e2x·■=■（e3x+ex）=■（■3n■+■■）=■■·■

從而，an=■ （n=0，1，2，…）。

作為本科數學專業的學生，組合數學主要學習組合計數的思想方法，而排列組合、容斥原理、遞推關系以及生成函數都能解決組合計數的相關問題，從而體現了它們之間的統一性，這也是能夠同時利用它們解決同一計數問題的原因。但是使用不同的方法解決問題時，所表現出的難易程度又有差別，這又體現了這些方法之間的差異性。對于一個實際問題，究竟采用什么方法，這就需要根據實際情況而定。但我們在教學與學習的過程中，一題多解是掌握這些方法的一條很好的途徑。

參考文獻：

[1]陳敬華.關于組合數學的若干基本思想方法[J].湖北師范學院學報（自然科學版），2001，21（2）：86-89.

[2]曲婉玲.組合數學[M].北京：北京大學出版社，1989.

[3]匡正.組合數學習題精解[M].哈爾濱：哈爾濱工業大學出版社，2005.

基金項目：重慶師范大學青年基金資助項目（2011XLQ29）。

作者簡介：汪定國（1976-），男，講師，主要從事圖論，組合數學的研究。endprint

摘要：組合數學作為離散數學的一個分支，是理工科專業尤其是數學專業的大學生必須學習的一門課程。本文結合自己多年的教學實踐，對組合數學的教學作了一些探討。

關鍵詞：組合數學；教學；組合思想

中圖分類號：G642.41 文獻標志碼：A 文章編號：1674-9324（2014）01-0095-02

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

一、利用組合分析法求解

組合分析法即為在證明組合恒等式或解決組合問題時不是進行代數推導，而是對組合恒等式或組合問題所代表的組合意義進行分析，通過建立一一對應的方法說明等式兩邊或兩個組合問題恰好是對同一個組合模型進行計數。在教學時，一定要講清組合分析法的本質，同時要指明應用組合分析法的關鍵是建立一一對應關系的兩邊一定描述的是同一個組合模型。問題的求解：將所有的n位數碼分成兩組：①只含2的n位數碼為一組，組中只有一個n位數碼，它不出現數碼0，0是偶數。②至少含一個0或者1的n位數碼為另一組，組中共有3n-1個n位數碼。在這組數碼中，按2出現的模式再分成一些類，因在每一類的數碼中，0出現偶數次的數碼占一半，故這一組中0出現偶數次的數碼共有■。由①、②可知，0出現偶數次的數碼總數共有1+■=■個。

二、利用容斥原理求解

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

三、利用遞推關系求解

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

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

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

四、利用生成函數求解

冪級數是良好的數學工具。冪級數的系數形成的序列與冪級數是一一對應的。如果兩個冪級數之間存在某種關系，那么相應的兩個系數系列也必然存在一定得關系。組合分析中的許多問題可以歸結為求一個與n有關的數H（n），即本質是求一個未知序列{H（n）}。在教學時，應該指出利用生成函數解決問題的關鍵，即合理的構造相應地生成函數，再將問題轉化為求生成函數中某項的系數問題。問題的求解：設an表示由0、1、2組成的且0出現偶數次的n位數碼的個數。規定a0=1，則{an}的指數型生成函數為：fe（x）=（1+■+■+…）（1+x+■+■+■+…）2=e2x·■=■（e3x+ex）=■（■3n■+■■）=■■·■

從而，an=■ （n=0，1，2，…）。

作為本科數學專業的學生，組合數學主要學習組合計數的思想方法，而排列組合、容斥原理、遞推關系以及生成函數都能解決組合計數的相關問題，從而體現了它們之間的統一性，這也是能夠同時利用它們解決同一計數問題的原因。但是使用不同的方法解決問題時，所表現出的難易程度又有差別，這又體現了這些方法之間的差異性。對于一個實際問題，究竟采用什么方法，這就需要根據實際情況而定。但我們在教學與學習的過程中，一題多解是掌握這些方法的一條很好的途徑。

參考文獻：

[1]陳敬華.關于組合數學的若干基本思想方法[J].湖北師范學院學報（自然科學版），2001，21（2）：86-89.

[2]曲婉玲.組合數學[M].北京：北京大學出版社，1989.

[3]匡正.組合數學習題精解[M].哈爾濱：哈爾濱工業大學出版社，2005.

基金項目：重慶師范大學青年基金資助項目（2011XLQ29）。

作者簡介：汪定國（1976-），男，講師，主要從事圖論，組合數學的研究。endprint