- 離散數學資源
- 離散數學 - 快速指南
- 離散數學 - 資源
- 離散數學 - 討論
離散數學 - 計數理論
在日常生活中，我們經常需要找出某一系列事件所有可能結果的數量。例如，從50名男性和38名女性中，有多少種方法可以選擇一個由6名男性和4名女性組成的評審團？可以生成多少個不同的10位數個人所得稅識別號（PAN），其前五位是英文字母大寫，接下來的四位是數字，最後一位又是英文字母大寫？為了解決這些問題，我們使用數學計數理論。計數主要包括基本計數規則、排列規則和組合規則。
加法規則和乘法規則
加法規則和乘法規則用於將複雜的計數問題分解成簡單的問題。
加法規則 - 如果一系列任務$T_1, T_2, \dots, T_m$分別可以用$w_1, w_2, \dots w_m$種方法完成（條件是這些任務不能同時進行），那麼完成其中一項任務的方法數為$w_1 + w_2 + \dots +w_m$。如果我們考慮兩個不相交的任務A和B（即$A \cap B = \emptyset$），那麼在數學上$|A \cup B| = |A| + |B|$
乘法規則 - 如果一系列任務$T_1, T_2, \dots, T_m$分別可以用$w_1, w_2, \dots w_m$種方法完成，並且每個任務都在前一個任務發生後才進行，那麼完成這些任務的方法數為$w_1 \times w_2 \times \dots \times w_m$。在數學上，如果任務B在任務A之後進行，則$|A \times B| = |A|\times|B|$
示例
問題 - 一個男孩住在X地，想去Z地的學校。他必須先從家X到達Y地，然後再從Y地到達Z地。他可以乘坐3條公交線路或2條火車線路從X地到達Y地。從那裡，他可以選擇4條公交線路或5條火車線路到達Z地。從X地到Z地有多少種方法？
解答 - 從X地到Y地，他可以有$3 + 2 = 5$種方法（加法規則）。然後，他可以有$4 + 5 = 9$種方法從Y地到Z地（加法規則）。因此，從X地到Z地，他可以有$5 \times 9 = 45$種方法（乘法規則）。
排列
排列是某些元素的一種排列方式，其中順序很重要。換句話說，排列是元素的有序組合。
示例
從集合S ={x, y, z}中每次取兩個元素，所有排列為：
$xy, yx, xz, zx, yz, zy$。
我們必須從數字集合$S = \lbrace 1, 2, 3 \rbrace$中組成一個三位數的排列。當我們排列這些數字時，將形成不同的三位數。排列將是 = 123, 132, 213, 231, 312, 321
排列數
從'n'個不同的元素中取'r'個元素的排列數記為$n_{P_{r}}$
$$n_{P_{r}} = \frac{n!}{(n - r)!}$$
其中 $n! = 1.2.3. \dots (n - 1).n$
證明 - 假設有'n'個不同的元素。
有n種方法填充第一個位置。填充第一個位置後，剩下(n-1)個元素。因此，有(n-1)種方法填充第二個位置。填充第一個和第二個位置後，剩下(n-2)個元素。因此，有(n-2)種方法填充第三個位置。現在我們可以將填充第r個位置的方法數推廣為[n – (r–1)] = n–r+1
所以，從第一個位置到第r個位置的填充方法總數為：
$n_{ P_{ r } } = n (n-1) (n-2)..... (n-r + 1)$
$= [n(n-1)(n-2) ... (n-r + 1)] [(n-r)(n-r-1) \dots 3.2.1] / [(n-r)(n-r-1) \dots 3.2.1]$
因此，
$n_{ P_{ r } } = n! / (n-r)!$
一些重要的排列公式
如果有n個元素，其中$a_1$個是某種型別的相同元素，$a_2$個是另一種型別的相同元素；$a_3$個是第三種類型的相同元素，以此類推，$a_r$個是第$r$種類型的相同元素，其中$(a_1 + a_2 + ... a_r) = n$。
那麼，這n個物件的排列數為 = $n! / [(a_1!(a_2!) \dots (a_r!)]$。
從n個不同的元素中取n個元素的排列數 = $n_{P_n} = n!$
從n個不同元素中取r個元素的排列數，當x個特定元素總是佔據特定位置時 = $n-x_{p_{r-x}}$
當r個指定元素總是放在一起時，n個不同元素的排列數為 − $r! (n−r+1)!$
當r個指定元素永遠不會放在一起時，n個不同元素的排列數為 − $n!–[r! (n−r+1)!]$
從n個不同元素中取x個元素的環狀排列數 = $^np_{x}/x$
n個不同元素的環狀排列數 = $^np_{n}/n$
一些問題
問題1 - 從一堆6張不同的卡片中，有多少種方法可以排列它們？
解答 - 因為我們一次從6張卡片中取6張卡片，所以排列數為$^6P_{6} = 6! = 720$
問題2 - 單詞'READER'的字母有多少種排列方式？
解答 - 單詞'READER'是一個6個字母的單詞（2個E，1個A，1個D和2個R）。
排列數將是 $= 6! /\: [(2!) (1!)(1!)(2!)] = 180.$
問題3 - 單詞'ORANGE'的字母有多少種排列方式，使得子音只佔據偶數位置？
解答 - 單詞'ORANGE'中有3個母音和3個子音。子音本身的排列方式數量 = $^3P_{3} = 3! = 6$。剩餘的3個空位將用3個母音填充，有$^3P_{3} = 3! = 6$種方法。因此，排列總數為$6 \times 6 = 36$
組合
組合是一些給定元素的選擇，其中順序無關緊要。
從n個元素中取r個元素的所有組合數為：
$$^nC_{ { r } } = \frac { n! } { r!(n-r)! }$$
問題1
求集合$\lbrace1, 2, 3, 4, 5, 6\rbrace$中含有3個元素的子集個數。
解答
集合的基數為6，我們必須從集合中選擇3個元素。這裡，順序無關緊要。因此，子集個數為$^6C_{3} = 20$。
問題2
一個房間裡有6名男性和5名女性。有多少種方法可以選擇3名男性和2名女性？
解答
從6名男性中選擇3名男性的方法數為$^6C_{3}$，從5名女性中選擇2名女性的方法數為$^5C_{2}$
因此，方法總數為 − $^6C_{3} \times ^5C_{2} = 20 \times 10 = 200$
問題3
從總共9名學生中選擇3個不同的3人小組有多少種方法？
解答
我們將小組編號為1、2和3
為第一個小組選擇3名學生的方法數 − $^9C_{3}$
在選擇第一個小組後，為第二個小組選擇3名學生的方法數 − $^6C_{3}$
在選擇第一個和第二個小組後，為第三個小組選擇3名學生的方法數 − $^3C_{3}$
因此，方法總數 $= ^9C_{3} \times ^6C_{3} \times ^3C_{3} = 84 \times 20 \times 1 = 1680$
帕斯卡恆等式
帕斯卡恆等式，最早由布萊斯·帕斯卡在17世紀推匯出來，指出從n個元素中選擇k個元素的方法數等於從(n-1)個元素中選擇(k-1)個元素的方法數與從n-1個元素中選擇k個元素的方法數之和。
在數學上，對於任何正整數k和n：$^nC_{k} = ^n{^-}^1C_{k-1} + ^n{^-}^1{C_k}$
證明 −
$$^n{^-}^1C_{k-1} + ^n{^-}^1{C_k}$$
$= \frac{ (n-1)! } { (k-1)!(n-k)! } + \frac{ (n-1)! } { k!(n-k-1)! }$
$= (n-1)!(\frac{ k } { k!(n-k)! } + \frac{ n-k } { k!(n-k)! } )$
$= (n-1)! \frac{ n } { k!(n-k)! }$
$= \frac{ n! } { k!(n-k)! }$
$= n_{ C_{ k } }$
鴿巢原理
1834年，德國數學家彼得·古斯塔夫·勒熱納·狄利克雷提出了一種他稱之為抽屜原理的原理。現在，它被稱為鴿巢原理。
鴿巢原理指出，如果鴿子的數量少於鴿巢的數量，並且每隻鴿子都被放入一個鴿巢中，那麼至少有一個鴿巢中不止一隻鴿子。如果n只鴿子被放入m個鴿巢中，其中n > m，那麼至少有一個鴿巢中不止一隻鴿子。
示例
十個人在一個房間裡，他們正在進行握手。如果每個人至少握手一次，並且沒有人與同一個人握手不止一次，那麼兩個人進行了相同次數的握手。
在一個30人的班級中，至少有兩名學生的姓名以相同的字母開頭。
容斥原理
容斥原理用於計算多個非不相交集合的並集的基數。對於兩個集合A和B，該原理指出：
$|A \cup B| = |A| + |B| - |A \cap B|$
對於三個集合A、B和C，該原理指出：
$|A \cup B \cup C | = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C |$
其一般公式為：
$|\bigcup_{i=1}^{n}A_i|=\sum_{i=1}^n |A_i| - \sum\limits_{1\leq i<j\leq n}|A_i \cap A_j|+\sum\limits_{1\leq i<j<k\leq n}|A_i \cap A_j \cap A_k|- \dots +(-1)^{\n-1}|A_1 \cap \dots \cap A_n|$
問題1
從1到50的整數中，有多少個是2或3的倍數，但不是兩者兼而有之的？
解答
從1到50，有 $50/2 = 25$ 個是2的倍數。
有 $50/3 = 16$ 個是3的倍數。
有 $50/6 = 8$ 個同時是2和3的倍數。
因此，$|A|=25$，$|B|=16$，$|A \cap B|= 8$。
$|A \cup B| = |A| + |B| - |A \cap B| = 25 + 16 - 8 = 33$
問題2
在一個有50名學生的群體中，24人喜歡冷飲，36人喜歡熱飲，每個學生至少喜歡其中一種飲料。有多少人既喜歡咖啡又喜歡茶？
解答
設X為喜歡冷飲的學生集合，Y為喜歡熱飲的學生集合。
因此，$| X \cup Y | = 50$，$|X| = 24$，$|Y| = 36$
$|X \cap Y| = |X| + |Y| - |X \cup Y| = 24 + 36 - 50 = 10$
因此，有10名學生既喜歡咖啡又喜歡茶。