組合數學

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

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

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

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