组合数学

来自维基百科
蹦到: 导航搜寻

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

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

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

组合数学中个著名问题[编辑]

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

排列[编辑]

隻元素中取出隻元素,隻元素个排列數量爲:

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

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

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

個元素中取出個元素,個元素可以重复出现,昰排列數量爲:

[1]

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

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

组合[编辑]

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

隻元素中取出隻元素,隻元素个组合數量为:

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

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

隻元素中取出隻元素,隻元素可以重複出現,隻组合數量为:

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

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

另外也可以記爲[2]

总结[编辑]

中取 直線排列

(考慮順序)

环状排列 组合

(弗考慮順序)

弗重复出现

(弗擺回去)




可重复出现

(再擺回去)




参见[编辑]

參攷文獻[编辑]

  1. 組合數學 ─算法與分析─.九章出版社,29.  OCLC:44527392
  2. 組合數學 ─算法與分析─.九章出版社,33.  OCLC:44527392

外部連結[编辑]