组合数学

广义个组合数学（英语：Combinatorics）就是离散数学，狭义个组合数学是组合计数、图论、代数结构、数理逻辑等个总称。但昰些衹畢過弗同学者在叫法上个区别。总之，组合数学是一门研究可數或离散对象个科学。随著计算机科学个日益发展，组合数学个重要性也日渐凸显，因为计算机科学个核心内容是使用算法处理离散数据。

狭义个组合数学主要研究满足一定条件个组态（也称组合模型）个存在、计数以及构造等方面个问题。

组合数学个主要内容有得组合计数、组合设计、组合矩阵、组合优化（最佳組合）等。

组合数学中个著名问题

計算一眼物品在特定條件下分組个方法數目。昰些是關於排列、組合搭整數分拆个。
地图着色问题：对世界地图着色，每一個国家使用一种颜色。如果要求相邻国家个颜色相异，是否总共衹需四种颜色？昰個是圖論个問題。
船夫过河问题：船夫要擔一匹狼、一只羊搭一棵白菜运过河。衹要船夫弗在场，羊就会得吃白菜、狼就会得吃羊。船夫个船每趟衹能运送一种物事。如然擔所有物事儕运过河？昰個是線性規劃个問題。
中国邮差问题：由中国组合数学家管梅谷教授提出來。邮递员要穿过城市个每一条路至少一趟，如然樣子走嚜走过个路程頂短？昰個弗是一個NP完全问题，存在多项式复杂度算法：先求出度为奇数个点，用匹配算法算出昰些点间个连接方式，然后再用欧拉路径算法求解。昰個也是圖論个問題。
任务分配问题（也称分配问题）：有一些员工要完成一些任务。各個员工完成弗同任务所花费个时间儕弗同。每個员工衹分配一项任务。每项任务衹畀分配给一個员工。如然分配员工与任务以使所花费个时间頂頂少？昰個是線性規劃个問題。
如何構造幻方。幻方爲一方陣，填入弗重複个自然數，並使其中每一縱列、橫列、對角線內數字之總和儕相同。

排列

从 $n$ 隻元素中取出 $k$ 隻元素， $k$ 隻元素个排列數量爲：

P_{k}^{n}={\frac {n!}{(n-k)!}}

以賽馬爲例，有8匹马参加比赛，玩家需要在彩票上填入前三胜出个马匹个号码，從8匹馬中取出3匹馬來排前3名，排列數量爲：

P_{3}^{8}={\frac {8!}{(8-3)!}}=8\times 7\times 6=336

因为一共存在336种可能性，因此玩家在一次填入中中奖个概率应该是：

P={\frac {1}{336}}=0.00298

上面个例子是建立在取出元素弗重複出現狀況。

從 $n$ 個元素中取出 $k$ 個元素， $k$ 個元素可以重复出现，昰排列數量爲：

U_{k}^{n}=n^{k}

^[1]

以四星彩爲例，10個數字取4個數字，因可能重複所以排列數量爲：

昰歇个一次性添入中奖个概率就应该是：

P={\frac {1}{10000}}=0.0001

组合

搭排列弗同个是，组合取出元素个顺序弗考虑。

从 $n$ 隻元素中取出 $k$ 隻元素， $k$ 隻元素个组合數量为：

C_{k}^{n}={n \choose k}={\frac {P_{k}^{n}}{k!}}={\frac {n!}{k!(n-k)!}}

以六合彩爲例。在六合彩中从49顆球裏向取出6顆球个组合數量为：

C_{6}^{49}={49 \choose 6}={\frac {49!}{6!43!}}=13983816

如同排列，上面个例子是建立在取出元素弗重複出現狀況。

从 $n$ 隻元素中取出 $k$ 隻元素， $k$ 隻元素可以重複出現，隻组合數量为：

以取色球爲例，每種顏色个球有無限多顆，從8種色球中取出5顆球，昰組合數量爲：

H_{5}^{8}=C_{5}^{8+5-1}=C_{5}^{12}={\frac {12!}{5!7!}}=792

因爲組合數量公式特性，重複組合轉換成組合有另一種公式爲：

H_{k}^{n}=C_{k}^{n+k-1}={\frac {(n+k-1)!}{k!(n-1)!}}=C_{n-1}^{n+k-1}

另外 $H_{k}^{n}$ 也可以記爲 $F_{k}^{n}$ ^[2]

F_{k}^{n}=H_{k}^{n}

总结

$n$ 中取 $k$	直線排列（考慮順序）	环状排列	组合（弗考慮順序）
弗重复出现（弗擺回去）	$P_{k}^{n}={\frac {n!}{(n-k)!}}$	${\frac {n!}{k\cdot (n-k)!}}$	$C_{k}^{n}={\frac {n!}{k!\cdot (n-k)!}}$
可重复出现（再擺回去）	$U_{k}^{n}=n^{k}$	${\frac {\sum _{r\|k}(r\cdot \varphi (r)\cdot n^{\frac {k}{r}})}{k}}$	$H_{k}^{n}={\frac {(n+k-1)!}{k!\cdot (n-1)!}}$