組合數(shù)學(xué)簡(jiǎn)介

組合數(shù)學(xué)

Combinatorics教材課程安排組合數(shù)學(xué)簡(jiǎn)介排列組合公式母函數(shù)遞推關(guān)系容斥原理抽屜原理Polya計(jì)數(shù)組合數(shù)學(xué)簡(jiǎn)介組合數(shù)學(xué)也稱為組合分析或組合學(xué)，按研究的對(duì)象歸于離散數(shù)學(xué)家族。早在中國(guó)古代的洛書、河圖中就有組合數(shù)學(xué)的思想。組合數(shù)學(xué)的歷史淵源扎根于數(shù)學(xué)娛樂和游戲中。現(xiàn)代組合數(shù)學(xué)在純粹和應(yīng)用科學(xué)上都有重要的價(jià)值。組合數(shù)學(xué)與抽象代數(shù)、拓?fù)鋵W(xué)、數(shù)學(xué)基礎(chǔ)、圖論、博弈論、線性規(guī)劃以及許多其它領(lǐng)域都有聯(lián)系。駁雜組合數(shù)學(xué)與計(jì)算機(jī)的相互促進(jìn)關(guān)系。算法速度洛書、河圖洛書、河圖是以不同形狀、個(gè)數(shù)的黑白點(diǎn)排列的圖案，并有許多神秘的解釋。研究?jī)?nèi)容組合數(shù)學(xué)與很多數(shù)學(xué)分支相交叉，因此很難對(duì)它下一個(gè)正式的定義。大體上說，組合數(shù)學(xué)是研究離散結(jié)構(gòu)的存在、計(jì)數(shù)、分析和優(yōu)化等問題的一門學(xué)科。主要內(nèi)容：把有限集合的元素按一定的規(guī)則進(jìn)行安排。這種安排被考究地稱為組態(tài)（Configuration）。解決的問題組態(tài)的存在性組態(tài)的枚舉、分類和計(jì)數(shù)組態(tài)的構(gòu)造組態(tài)的優(yōu)化幻方幻方是最古老最流行的一個(gè)數(shù)學(xué)游戲之一。在中世紀(jì)時(shí)期曾存在與幻方相關(guān)的玄想，人們將幻方佩戴身上辟邪。本杰明·富蘭克林就是一個(gè)幻方迷，他的論文中包含很多有趣的例子。問題：用n2個(gè)整數(shù)1,2,…,n2構(gòu)造一個(gè)n×n矩陣，使每行、每列、對(duì)角線元素之和均相等。這個(gè)相等的和叫做幻和?；梅降膯栴}對(duì)任意的正整數(shù)n，n階幻方存在嗎？對(duì)于某個(gè)正整數(shù)n，如果n階幻方存在，有多少不同的形式？構(gòu)造存在的n階幻方?；梅揭浑A幻方二階幻方不存在三階幻方四階幻方有880個(gè)結(jié)論：對(duì)任意n≥1，n≠2，均可構(gòu)造一個(gè)n階幻方。但構(gòu)造方法復(fù)雜，不唯一。奇數(shù)階幻方的構(gòu)造較簡(jiǎn)單，偶數(shù)階較復(fù)雜?；梅襟wn階幻方體(magiccube)是以下述方式由整數(shù)1,2,…,n3構(gòu)造一個(gè)n×n×n立方陣列，其在下述每一條直線上的n個(gè)元素的和s都是相同的：(i)平行于立方體一條邊的直線；(ii)每個(gè)截面上的兩條對(duì)角線；(iii)四條空間對(duì)角線。數(shù)s叫做幻方體的幻和。不存在2階幻方體也不存在3階幻方體證明不存在4階幻方體要困難的多。一個(gè)8階的幻方體在Cardner的一篇論文中給出。棋盤的覆蓋問題用1×2格的骨牌覆蓋8×8棋盤。(1)能否在棋盤上放置32個(gè)骨牌使之完全覆蓋該棋盤？(2)若存在，則有多少種不同的完全覆蓋？(3)去掉了兩個(gè)對(duì)角處格子的殘缺棋盤，問能否用31枚骨牌恰將其覆蓋？棋盤的覆蓋問題3×3棋盤能否用1×2的骨牌完美覆蓋呢？m×n的棋盤滿足什么條件時(shí)，能被1×2的骨牌完美覆蓋呢？等價(jià)于分子生物學(xué)中的二聚物問題。Fischer在論文StatisticalMechanicsofDimersonaPlaneLattice中得出涉及三角函數(shù)的用來(lái)計(jì)算m×n棋盤不同完美覆蓋數(shù)的更一般公式。對(duì)于m×n的棋盤，1×b骨牌(b牌,b-omino)的情形呢？b=1情形monomino單牌b=2情形更一般的情形？先給一個(gè)充分條件此條件是否必要呢？b是素?cái)?shù)b不是素?cái)?shù)結(jié)論：一張m行n列棋盤有一個(gè)b-牌的完美覆蓋當(dāng)且僅當(dāng)b是m的一個(gè)因子或者b是n的一個(gè)因子。進(jìn)一步問題：一張m行n列棋盤有一個(gè)b-牌的完美覆蓋時(shí)，覆蓋的方式有多少呢？棋盤的覆蓋問題棋盤的覆蓋問題問題：證明用形可以完全覆蓋剪去任一小方格后得到的(2n×2n-1)形棋盤。Nim取子游戲Nim取子游戲是由兩個(gè)人面對(duì)若干堆硬幣（或石子）進(jìn)行的游戲。設(shè)有k≥1堆硬幣，各堆分別含有n1，n2，…，nk枚硬幣。游戲的目的是選擇最后剩下的硬幣。游戲規(guī)則如下：1.兩個(gè)游戲人交替進(jìn)行游戲（游戲人I：第一個(gè)取子者；游戲人II：第二個(gè)取子者）；2.當(dāng)輪到每個(gè)游戲人取子時(shí)，選擇這些堆中的一堆，并從所選的堆中取走至少一枚硬幣（游戲人可以取走他所選堆中的全部硬幣）；3.當(dāng)所有的堆都變成空堆時(shí)，最后取子的游戲人即為勝者。對(duì)應(yīng)的組合問題是，確定游戲人I獲勝還是游戲人II獲勝，以及游戲人應(yīng)該如何取子才能保證獲勝（獲勝策略）。Nim取子游戲一堆硬幣的情況兩堆硬幣的情況兩堆硬幣數(shù)相同平衡兩堆硬幣數(shù)不同不平衡結(jié)論：平衡游戲，II按照I取子數(shù)量在另一堆中取子即可獲勝；不平衡游戲，I從大堆中取走硬幣使兩堆數(shù)量相等，后I每次取子數(shù)量與II相同，I即可獲勝。用二進(jìn)制表示k堆情形：平衡與不平衡結(jié)論：游戲人II能夠在平衡游戲中獲勝，游戲人I能夠在非平衡取子游戲中獲勝。36軍官問題設(shè)有分別來(lái)自6個(gè)軍團(tuán)共有6種不同軍銜的36名軍官，他們能否排成6×6的編隊(duì)使得每行每列都有各種軍銜的軍官一名，并且每行每列上的不同軍銜的6名軍官還分別來(lái)自不同的軍團(tuán)？18世紀(jì)瑞士數(shù)學(xué)家歐拉提出36個(gè)序偶(i,j)(i=1,2,…,6,j=1,2,…,6)能否排成6×6陣列，使得每行和每列，這6個(gè)整數(shù)1,2,…,6都能以某種順序出現(xiàn)在序偶第一個(gè)元素的位置上，并以某種順序出現(xiàn)在第二個(gè)元素的位置上？是否存在這樣的兩個(gè)6×6矩陣，其元素取自1,2,…,6使得

i)整數(shù)1,2,…,6以某種順序出現(xiàn)在矩陣的每一行和每一列；

ii)當(dāng)這兩個(gè)矩陣并置時(shí)，所有36個(gè)序偶(i,j)(i=1,2,…,6,j=1,2,…,6)全部出現(xiàn)？36軍官問題3階拉丁方：在矩陣每行和每列上，整數(shù)1,2和3中的每一個(gè)都出現(xiàn)一次。問題轉(zhuǎn)化為：是否存在兩個(gè)正交的6階拉丁方？正交拉丁方對(duì)于n為奇數(shù)和4的倍數(shù)，歐拉指出了如何構(gòu)造一對(duì)n階正交拉丁方。歐拉猜想，不存在像6,10,14,18,…這樣階數(shù)的拉丁方。通過窮舉法，Tarry在1901年證明了歐拉的猜想對(duì)n=6成立。大約在1960年前后，三位數(shù)理統(tǒng)計(jì)學(xué)家成功證明了歐拉猜想對(duì)于所有大于6的n都是不成立的。集合論集合中元素個(gè)數(shù)的定義（集合的勢(shì)）一一對(duì)應(yīng)的思想有限集無(wú)限集可數(shù)集(可列集)常見數(shù)集的勢(shì)正偶數(shù)集與正整數(shù)集兩個(gè)可數(shù)集的并仍為可數(shù)集可數(shù)個(gè)可數(shù)集的并仍為可數(shù)集自然數(shù)集與有理數(shù)集實(shí)數(shù)確實(shí)比自然數(shù)多四個(gè)基本的計(jì)數(shù)原理加法原理

做一件事，完成它可以有n類辦法，在第一類辦法中有m1種不同的方法，在第二類辦法中有m2種不同的方法，…，在第n類辦法中有mn種不同的方法，那么完成這件事共有N=m1+m2+m3+…+mn種不同方法。乘法原理做一件事，完成它需要分成n個(gè)步驟，做第一步有m1種不同的方法，做第二步有m2種不同的方法，……，做第n步有mn種不同的方法，那么完成這件事共有N=m1×m2×…×mn種不同的方法。減法原理除法原理例題137名運(yùn)動(dòng)員打乒乓球，單淘汰賽，問決出冠軍需要打多少場(chǎng)比賽？方法一：方法二：例題n元集合的子集有多少個(gè)？加法原理乘法原理所有n長(zhǎng)的0,1序列有多少個(gè)？例題求n元集合的含某固定元的子集的個(gè)數(shù)？設(shè)Sn={1,2,…,n}，求例題設(shè)A,B為有限集，。從A到B的映射有多少個(gè)？若m=n，則從A到B的雙射有多少個(gè)？若m≤n，則從A到B的單射有多少個(gè)？若m≥n，則從A到B的滿射有多少個(gè)？集合B上的冪等映射有多少個(gè)？集合B上的部分映射有