Loading AI tools
来自维基百科,自由的百科全书
广义的组合数学(英語:Combinatorics)相当于离散数学,狭义的组合数学是组合计数、图论、代数结构、数理逻辑等的总称。但这只是不同学者在叫法上的区别。总之,组合数学是一门研究可數或离散对象的科学。随着计算机科学日益发展,组合数学的重要性也日渐凸显,因为计算机科学的核心内容是使用算法处理离散数据。
![]() |
![]() | 此條目需要精通或熟悉数学的编者参与及协助编辑。 |
狭义的组合数学主要研究满足一定条件的组态(也称组合模型)的存在、计数以及构造等方面的问题。组合数学的主要内容有组合计数、组合设计(Combinatorial design)、组合矩阵(Combinatorial matrix theory)、组合最佳化(最佳組合)等。
最基本的組合數學的思想和枚舉的方法在古老時代就已經出現。西元前6世紀的古印度外科醫生妙聞指出可以由6種相異味道組合出63種相異結果(每種味道都可以選擇或不選擇,但不能都不選擇,因此有26−1=63種組合);羅馬時代的希臘史家普魯塔克與克律西波斯、喜帕恰斯討論了後來顯示與Schröder–Hipparchus數有關的枚舉問題[1][2];西元前3世紀的阿基米德在其數學文章Ostomachion中講述拼接拼圖的智力遊戲(tiling puzzle)。
中世紀時,組合數學持續發展(主要是歐洲外的文明)。西元850年的印度數學家Mahāvīra提供了關於排列數與組合的公式[3][4],甚至可能早在6世紀的印度數學家就對這些公式熟悉[5] 。西元1140年哲學家與天文學家阿伯拉罕·伊本·埃茲拉確認了二項式係數的對稱性,而二項式係數公式則是由猶太人數學家吉尔松尼德在西元1321年得到[6]。楊輝三角形最早可追溯至10世紀的數學論文,在中國則首現於13世紀南宋楊輝《詳解九章算法》。在英格蘭則出現與哈密頓迴路相關的例子[7]。
文藝復興時期,與其他數學或科學領域一樣,組合數學再現生機。帕斯卡、牛頓、雅各布·白努利、歐拉等人的研究為此新興領域打下基礎。在更近代,西爾維斯特和MacMahon也在組合計數和代數組合學有貢獻。人們此時也對圖論有極大興趣,例如關於四色問題的領域。
在20世紀下半葉,組合數學成長相當快速,甚至出現數十種新的期刊和會議[8],這樣的成長某程度上是由對其他領域的連結與應用所帶動,如代數、機率論、泛函分析和數論。
从个元素取出个元素,个元素的排列數量為:
以賽馬為例,有8匹马参赛,玩家需在彩票上填入前三匹胜出的马匹号码,從8匹馬取出3匹來排前3名,排列數量為:
因为有336种排列,因此玩家在一次填入中中奖的概率是:
不過,中國大陸的教科書則是把從n取k的情況記作或(A代表Arrangement,即排列[9])。
上例是在取出元素不重複出現的狀況建立。
從个元素取出个元素,个元素可以重复出现,這排列數量為:
以四星彩為例,10個數取4個,因可能重複所以排列數量為:
这时的一次性添入中奖的概率就是:
和排列不同的是,组合不考虑取出元素的顺序。
从个元素取出个,个元素的组合數量为:
中國大陸的教科書則是把從取的情況記作[11]。
以香港六合彩為例,六合彩49顆球選6顆的组合數量为:
如同排列,上面的例子是建立在取出元素不重複出現狀況。
从个元素取出个元素,個元素可以重複出現,组合數量为:
以取色球為例,每種顏色的球有無限多顆,從8種色球取出5顆球,這組合數量為:
因為組合數量公式特性,重複組合轉換成組合有另一種公式為:
另外也可以記為[12]
中取 | 直線排列 (考慮順序) |
环状排列 | 组合 (不考慮順序) |
不重复出现 (不放回去) |
(OEIS數列A008279) |
(OEIS數列A111492) |
(OEIS數列A007318) |
可重复出现 (再放回去) |
(OEIS數列A004248) |
(OEIS數列A075195) |
(OEIS數列A097805) |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.