望“组合数学”个源码

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

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

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

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

== 排列 ==
从<math>n</math>隻元素中取出<math>k</math>隻元素，<math>k</math>隻元素个排列數量爲：
: <math> P_k^n = \frac{n!}{(n-k)!}</math>
以[[賽馬]]爲例，有8匹马参加比赛，玩家需要在彩票上填入前三胜出个马匹个号码，從8匹馬中取出3匹馬來排前3名，排列數量爲：
: <math> P_3^8 =\frac{8!}{(8-3)!}=8\times7\times6=336</math>
因为一共存在336种可能性，因此玩家在一次填入中中奖个概率应该是：
: <math> P = \frac{1}{336}= 0.00298</math>

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

從<math>n</math>個元素中取出<math>k</math>個元素，<math>k</math>個元素可以重复出现，昰排列數量爲：
: <math> U_k^n = n^k</math><ref name="組合數學">{{cite book|title=組合數學 ─算法與分析─|publisher=九章出版社|pages=29}} OCLC:44527392 </ref>
以[[中華民國公益彩券|四星彩]]爲例，10個數字取4個數字，因可能重複所以排列數量爲：

昰歇个一次性添入中奖个概率就应该是：
: <math>P=\frac{1}{10000}=0.0001</math>

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

从<math>n</math>隻元素中取出<math>k</math>隻元素，<math>k</math>隻元素个组合數量为：
: <math>C_k^n ={n \choose k} = \frac{P_k^n}{k!} = \frac{n!}{k!(n-k)!}</math>
以[[六合彩]]爲例。在六合彩中从49顆球裏向取出6顆球个组合數量为：
: <math>C_{6}^{49}  = {49 \choose 6} = \frac{49!}{6!43!} = 13983816</math>
如同排列，上面个例子是建立在取出元素弗重複出現狀況。

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

以取色球爲例，每種顏色个球有無限多顆，從8種色球中取出5顆球，昰組合數量爲：
: <math>H_5^8 = C_{5}^{8+5-1} = C_5^{12} = \frac{12!}{5!7!} = 792</math>
因爲組合數量公式特性，重複組合轉換成組合有另一種公式爲：
: <math>H_k^n=C_k^{n+k-1}=\frac{(n+k-1)!}{k!(n-1)!}=C_{n-1}^{n+k-1}</math>
另外<math>H_k^n</math>也可以記爲<math>F_k^n</math><ref name="組合數學P33">{{cite book|title=組合數學 ─算法與分析─|publisher=九章出版社|pages=33}} OCLC:44527392 </ref>
: <math>F_k^n = H_k^n</math>

== 总结 ==
{| class="wikitable" style="margin: 0px auto 10px; text-align: center; width: 50em;"
|<math>n</math>中取<math>k</math>
|直線排列<br>
（考慮順序）
|环状排列
|组合<br>
（弗考慮順序）
|-
| style="background:#CCCCFF;color:black;font-weight:bold;" |弗重复出现<br>
（弗擺回去）
|<math>P^n_k=\frac{n!}{(n-k)!}</math><br>
|<math>\frac{n!}{k \cdot (n-k)!}</math><br>
|<math>C^n_k=\frac{n!}{k! \cdot (n-k)!}</math><br>
|-
| style="background:#CCCCFF;color:black;font-weight:bold;" |可重复出现<br>
（再擺回去）
|<math>U^n_k=n^k</math><br>
|<math>\frac{\sum_{r|k}(r \cdot \varphi(r) \cdot n^{\frac{k}{r}})}{k}</math><br>
|<math>H^n_k=\frac{(n+k-1)!}{k! \cdot (n-1)!}</math><br>
|}

== 参见 ==
* [[排列组合符号]]
* [[阶乘]]
* [[阶乘符号]]
* [[排列]]

== 參攷文獻 ==
{{reflist}}

== 外部連結 ==
* [http://www.combinatorics.net/ The Combinatorics Net] {{Wayback|url=http://www.combinatorics.net/ |date=20210503092755 }}
* [http://www.combinatorics.org/ Electronic Journal of Combinatorics]
* [http://chowkafat.net/Mathtopic.html#Enumeration 点算个奥秘]

[[Category:数学]]