---

什么是計數？

車牌號里的每一個序位數，都是從26個英文字母和10個阿拉伯數字里選取出來，然后按照約定好的順序和規則去排列成一串號碼。想求出都能排列出多少種可能，計算的這個過程就叫計數。

為什么要學習計數原理？
就類似上面的車牌案例，你要是一個一個數，從頭到位的遍歷出來，那確實不用什么學什么計數原理了，但是那樣會很低效?；蛘哒f如果需要計數的范圍很大，用一個一個數的方式本身就無法實現。那么學習計數原理就可以幫你高效地計算出全部可能排列的總數字。

計數原理要學什么？
主要是兩類基本的計數原理，和一種特殊規則：

• 兩類：
  1. 分類加法計數
  2. 分步乘法計數
• 特殊：
  • 排列數和組合數

計數原理的研究范圍：
如何采用最高效的方式去不重復、不遺漏地數清所有可能的情況。

---

分類加法計數（加法原理）

如果一個事件有多種互相獨立的選擇，且每種選擇的方案數是已知的，那么總的方案數就是各種選擇的方案數之和。

如果完成一件事有n類方法，且這n類方法互不重疊，那么完成這件事共有n1 + n2 + ... + n，共 n 種方法。

屬于“或”、“分類”的關系。幾類方案是相互獨立的，選擇任何一類都能完成任務。

例子：從北京到上海，可以坐火車（3個車次）或坐飛機（2個航班）。那么總共有 3 + 2 = 5 種走法。

---

分步乘法計數（乘法原理）

如果一個事件需要分步完成，且每一步的方案數是已知的，那么總的方案數就是每一步方案數的乘積。

如果完成一件事需要分n個步驟，且每個步驟有不同的方法數，那么完成這件事共有n1 * n2 * ... * n，共 n 種方法。

屬于“與”、“分步”。所有步驟必須依次完成，缺一不可。

例子：從北京經上海到廣州，先從北京到上海有3種走法，然后從上海到廣州有4種走法。那么總共有 3 × 4 = 12 種走法。

總結：

• 區分問題屬于分類還是分步很關鍵。
• 分類類似 或（OR） 的關系；
• 分步類似 且（AND） 的關系；

---

階乘

在學習排列數之前，先來了解階乘和遞歸。

階乘函數（符號：!）的意思是把逐一減小的自然數序列相乘。例如：
1! = 1
4! = 4 × 3 × 2 × 1 = 24
7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040

階乘的特點：

• 增長很快！

  ?? 在編程中，如果某算法的運算量是階乘增長關系，那么通常被認為是“不合格”的算法（如旅行商問題的暴力解法）；

階乘和遞歸的關系：
要計算一個階乘的值，我們可以用上一個階乘的值：

比如我們要求 4！= ?
假設我們不知道4！這種運算要怎么求？我們只知道一個規律，要計算一個階乘的值，我們可以用上一個階乘的值。

可以先問：4！ = 4* 3！，
在問：3！ = 3* 2！，
在問：2！ = 2* 1！，
在問：1！= ？
1！= 1， 這個是基準了，不用在向下追問了。那么就可以以此類推地回溯回去了。
2！= 2 * 1 = 2，
3！= 3 * 2 = 6，
4！= 4 * 6 = 24；
最后通過回溯得到答案。

遞歸就類似是階乘運算，換一下量詞，是不是很類似呢？
假設我們不知道某個方法要怎么求？我只知道一個規律，要計算一個方法的值，可以用上一個方法的值。

手算的遞歸，是你在紙上記錄了遞歸的層級變化，最后得出結果。而計算機的遞歸是計算機的寄存器幫忙存儲了層級變量，最后累加得出結果。

---

排列數

排列是研究對象在特定順序下的安排方式。例如，從 4 個元素中選出 2 個，有多少種不同的排列方式？

比如，{a,b,c,d} 四個元素，你每次取2個出來，可以擺多少種？
n=4,
m=2,
可以想象一下，m是兩個位置：( ) , ( ) 在這兩個位置需要不重復的擺放一次各個元素，排序的過程類似編程的冒泡算法（一種處理順序（排列）的簡單算法）。

ab,ac,ad
ba,bc,bd
ca,cb,bd
da,db,dc

可以擺12種。

要從n個元素中取出m個(m ≤ n)元素，需考慮元素的順序，稱為從n個元素中取出m個元素的排列。 ,比如 密碼“123”和“321”是完全不同的。

排列的個數用 P(n, m) 表示，

計算公式為：$$ P(n, m) = \frac{n!}{(n-m)!} $$

---

組合數

組合是研究對象在不考慮順序的情況下，有多少種選擇方式。例如，從 4 個元素中選出 2 個，有多少種不同的組合方式？

比如，{a,b,c,d} 四個元素，你每次取2個出來，可以擺多少種？
n=4,
m=2,
可以想成，m是兩個位置：( ) , ( )

ab,ac,ad
ba,bc,bd
ca,cb,cd
da,db,dc

可以擺6種。

要從n個元素中取出m個(m ≤ n)元素，不考慮元素的順序，稱為從n個元素中取出m個元素的組合。，比如 組隊： 從10個人中選出3個人組成一個委員會。隊伍 {A, B, C} 和隊伍 {C, B, A} 是同一個隊伍。

總結：排列關心“誰在什么位置”；組合只關心“誰在里面”。

組合的個數用C(n, m)表示，

計算公式為：$$ C(n, m) = \frac{ n! } {(m! * (n-m)!)} $$

能區分一個問題是分類、分步、排列數、組合數，并且會套用相關公式計算出結果，已經算是入門了，屬于一個合格的工具應用者了。

如果用編程算法來理解組合數，可以用回溯算法來生成 {a, b, c, d} 中所有 2 元素組合，如下是大致的每一步。

元素：{a,b,c,d}，取所有2個元素組合。

第一次：a
	將ab,ac,ad存儲；
第二次：b
	將bc,bd存儲；
第三次：c
	將cd存儲；
第四次：d
	無法形成長度為2的組合，退出。

ps:可以讓AI生成一個算法，然后借助調試工具去理解這個過程，因為這個算法涉及到遞歸，純人腦去理解遞歸是困難的，因為用人腦去模擬電腦的多個寄存器的存儲狀態，以及各輪的運算過程的變化，顯然有點超負荷╮(╯▽╰)╭。

---

如何從模型推理出公式？

假設我們并沒有排列P(n,m)、C(n,m）公式，那么我們怎么能根據已知的規律和模型，自己推導出一個普遍性公式呢？
todo

---

利用二項式定理求未知

到這里，你不光能計數，你還能預測數！

作用：

• 展開多次多項式
  二項式定理描述了$ (x+y)^n $ 的展開式；

• 楊輝三角里系數和組合數的關系？
  
  

總結：不管是求組合數公式C(n, m)，還是楊輝三角的系數規律，都只能求出一個總數，但是并不能具體給出你組合的數列。

要生成所有具體的、明確的組合，我們需要自己編程或者調用別人的算法去實現（如上述的編程算法）。

---

我用自己的語言描述了分類加法計數概念、分類乘法計數概念。

組合數和排列數概念，以及他們兩個的區別。

二項式公式的作用。