组合数学：修订间差异 - 求闻百科，共笔求闻

（未显示3个用户的6个中间版本）

下文是求闻百科的历史内容，而非最新内容，不代表求闻百科的立场。
若历史内容含有不良信息，请点此报告；参见投诉举报处理方针。

第5行：

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

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

== 歷史 ==

== 历史 ==

[[File:Plain-bob-minor 2.png|150px|右|缩略图|An example of [[change ringing]] (with six bells), one of the earliest nontrivial results in [[graph theory]].]]

最基本的組合數學的思想和枚舉的方法在古老時代就已經出現。西元前6世紀的古[[印度]]外科醫生[[妙闻|妙聞]]已經指出可以由6個相異的味道組合出63種相異的結果（每個味道都可以選擇或不選擇，但不能都不選擇，因此有2<sup>6</sup> − 1=63種組合）；[[羅馬帝國|羅馬時代]]的[[希臘]][[史家]][[普魯塔克]]與[[克律西波斯]]、[[喜帕恰斯]]討論了後來顯示與{{link-en|Schröder–Hipparchus數|Schröder–Hipparchus number}}有關的枚舉問題<ref>[[Richard P. Stanley|Stanley, Richard P.]]; "Hipparchus, Plutarch, Schröder, and Hough", ''American Mathematical Monthly'' '''104''' (1997), no. 4, 344–350.</ref><ref>Habsieger, Laurent; Kazarian, Maxim; and Lando, Sergei; "[http://search.proquest.com/openview/70485cece23ca51b18536b4422cc5586/1?pq-origsite=gscholar&cbl=47349 On the Second Number of Plutarch]", ''American Mathematical Monthly'' '''105''' (1998), no. 5, 446.</ref>；西元前3世紀的[[阿基米德]]在其數學文章''{{link-en|Ostomachion|Ostomachion}}''中考慮了一個拼接拼圖的智力遊戲（tiling puzzle）。

[[中世紀]]時，組合數學持續發展（主要是在[[歐洲]]外的文明）。西元850年的[[印度]]數學家{{link-en|Mahāvīra|Mahāvīra (mathematician)}}提供了關於[[排列]]數與[[組合]]的公式<ref>{{MacTutor|id=Mahavira}}</ref><ref>{{Citation|last=Puttaswamy|first=Tumkur K.|contribution=The Mathematical Accomplishments of Ancient Indian Mathematicians|editor-last=Selin|editor-first=Helaine|title=Mathematics Across Cultures: The History of Non-Western Mathematics|publisher=Kluwer Academic Publishers|location=Netherlands|~~url=https://books.google.com/books?id=2hTyfurOH8AC&printsec=frontcover~~|year=2000|isbn=978-1-4020-0260-1|page=417 }}</ref>，甚至可能早在6世紀印度的數學家就對這些公式熟悉<ref>{{cite journal|title=The Roots of Combinatorics|url=|first1=Norman L.|journal=Historia Mathematica|issue=2|doi=10.1016/0315-0860(79)90074-0|year=1979|volume=6|pages=109–136|last1=Biggs}}</ref>。1140年[[哲學家]]與[[天文學家]][[阿伯拉罕·伊本·埃茲拉]]確認了二項式係數的對稱性，而二項式係數公式則是由[[猶太人]][[數學家]][[Gersonides]]在1321年得到的<ref>{{citation|title=Probability Theory: A Historical Sketch|first=L.E.|last=Maistrov|publisher=Academic Press|year=1974|isbn=978-1-4832-1863-2|~~url=https://books.google.com/books?id=2ZbiBQAAQBAJ&pg=PA35~~|page=35}}. (Translation from 1967 Russian ed.)</ref>。[[楊輝三角形]]最早可追溯至10世紀的數學論文，在[[中国|中國]]則首現於13世紀[[南宋]][[杨辉|楊輝]]的《[[詳解九章算法]]》。在[[英格蘭]]，則出現一些與[[哈密頓圖|哈密頓迴路]]相關的例子<ref>

[[中世紀]]時，組合數學持續發展（主要是在[[歐洲]]外的文明）。西元850年的[[印度]]數学家{{link-en|Mahāvīra|Mahāvīra (mathematician)}}提供了關於[[排列]]數與[[組合]]的公式<ref>{{MacTutor|id=Mahavira}}</ref><ref>{{Citation|last=Puttaswamy|first=Tumkur K.|contribution=The Mathematical Accomplishments of Ancient Indian Mathematicians|editor-last=Selin|editor-first=Helaine|title=Mathematics Across Cultures: The History of Non-Western Mathematics|publisher=Kluwer Academic Publishers|location=Netherlands||year=2000|isbn=978-1-4020-0260-1|page=417 }}</ref>，甚至可能早在6世紀印度的數学家就對這些公式熟悉<ref>{{cite journal|title=The Roots of Combinatorics|url=|first1=Norman L.|journal=Historia Mathematica|issue=2|doi=10.1016/0315-0860(79)90074-0|year=1979|volume=6|pages=109–136|last1=Biggs}}</ref>。1140年[[哲学家]]與[[天文学家]][[阿伯拉罕·伊本·埃茲拉]]確認了二項式係數的對稱性，而二項式係數公式則是由[[猶太人]][[數学家]][[Gersonides]]在1321年得到的<ref>{{citation|title=Probability Theory: A Historical Sketch|first=L.E.|last=Maistrov|publisher=Academic Press|year=1974|isbn=978-1-4832-1863-2||page=35}}. (Translation from 1967 Russian ed.)</ref>。[[楊輝三角形]]最早可追溯至10世紀的數學論文，在[[中国|中國]]則首現於13世紀[[南宋]][[杨辉|楊輝]]的《[[詳解九章算法]]》。在[[英格兰]]，則出現一些與[[哈密頓圖|哈密頓迴路]]相關的例子<ref>

White, Arthur T.; "Ringing the Cosets", ''American Mathematical Monthly'', '''94''' (1987), no. 8, 721–746; White, Arthur T.; "Fabian Stedman: The First Group Theorist?", ''American Mathematical Monthly'', '''103''' (1996), no. 9, 771–778.</ref>。

[[文藝復興時期]]，與其他數學或[[科學]]領域一樣，組合數學再現生機。[[布萊茲·帕斯卡|帕斯卡]]、[[艾薩克·牛頓|牛頓]]、[[雅各布·白努利]]、[[李昂哈德·歐拉|歐拉]]等人的研究為此新興領域打下基礎。在更近代時，[[詹姆斯·約瑟夫·西爾維斯特|西爾維斯特]]和{{link-en|MacMahon|Percy Alexander MacMahon}}也對[[组合计数|組合計數]]和[[代數組合學]]作出貢獻。人們此時也對[[圖論]]有高度的興趣，例如關於[[四色定理|四色問題]]的領域。

[[文藝復興時期]]，與其他數學或[[科学]]領域一樣，組合數學再現生機。[[布萊茲·帕斯卡|帕斯卡]]、[[艾薩克·牛頓|牛頓]]、[[雅各布·白努利]]、[[李昂哈德·歐拉|歐拉]]等人的研究為此新興領域打下基礎。在更近代時，[[詹姆斯·約瑟夫·西爾維斯特|西爾維斯特]]和{{link-en|MacMahon|Percy Alexander MacMahon}}也對[[组合计数|組合計數]]和[[代數組合學]]作出貢獻。人們此時也對[[圖論]]有高度的興趣，例如關於[[四色定理|四色問題]]的領域。

在20世紀下半葉，組合數學成長相當快速，甚至出現數十種新的期刊和會議<ref>See [http://www.math.iit.edu/~kaul/Journals.html#CGT Journals in Combinatorics and Graph Theory]</ref>。在某種程度上，這樣的成長是由對其他領域的連結與應用所帶動，包括[[代數]]、[[機率論]]、[[泛函分析]]和[[數論]]等。

第36行：

:<math> P = \frac{1}{336}= 0.00298</math>

不過，中~~國大陸~~的教科書則是把從n取k的情況記作<math>P^k_n</math>或<math>A^k_n</math>（A代表Arrangement，即排列<ref>{{cite book|title=普通高中课程标准实验教科书数学选修2-3 B版|publisher=人民教育出版社|isbn=9787107187544|pages=10}}</ref>）。

不過，中国的教科書則是把從n取k的情況記作<math>P^k_n</math>或<math>A^k_n</math>（A代表Arrangement，即排列<ref>{{cite book|title=普通高中课程标准实验教科书数学选修2-3 B版|publisher=人民教育出版社|isbn=9787107187544|pages=10}}</ref>）。

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

第43行：

:<math> U_k^n = n^k</math><ref name="組合數學">{{cite book | title=組合數學 ─算法與分析─ | publisher=九章出版社 | pages=29}} OCLC:44527392</ref>

以[[中華民國公益彩券|四星彩]]為例，10個數字取4個數字，因可能重複所以排列數量為：

以[[中华民国公益彩券|四星彩]]為例，10個數字取4個數字，因可能重複所以排列數量為：

:<math>U_4^{10}=10^4=10000</math>

第56行：

:<math>C_k^n ={n \choose k} = \frac{P_k^n}{k!} = \frac{n!}{k!(n-k)!}</math>

不過，中~~國大陸~~的教科書則是把從<math>n</math>取<math>k</math>的情況記作<math>C^k_n</math><ref>{{cite book|title=普通高中课程标准实验教科书数学选修2-3 B版|publisher=人民教育出版社|isbn=9787107187544|pages=16}}</ref>。

不過，中国的教科書則是把從<math>n</math>取<math>k</math>的情況記作<math>C^k_n</math><ref>{{cite book|title=普通高中课程标准实验教科书数学选修2-3 B版|publisher=人民教育出版社|isbn=9787107187544|pages=16}}</ref>。

以[[六合彩]]為例。在六合彩中从49顆球中取出6顆球的组合數量为：

第69行：

:<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>

第102行：

== 參考文獻 ==

== 外部連結 ==

* [http://www.combinatorics.net/ The Combinatorics Net]

@@ 第5行： / 第5行： @@
 狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面的问题。
 组合数学的主要内容有[[组合计数]]、[[组合设计]]、[[组合矩阵]]、[[组合优化]]（[[最佳組合]]）等。
-== 歷史 ==
+== 历史 ==
 [[File:Plain-bob-minor 2.png|150px|右|缩略图|An example of [[change ringing]] (with six bells), one of the earliest nontrivial results in [[graph theory]].]]
 最基本的組合數學的思想和枚舉的方法在古老時代就已經出現。西元前6世紀的古[[印度]]外科醫生[[妙闻|妙聞]]已經指出可以由6個相異的味道組合出63種相異的結果（每個味道都可以選擇或不選擇，但不能都不選擇，因此有2<sup>6</sup>&nbsp;−&nbsp;1=63種組合）；[[羅馬帝國|羅馬時代]]的[[希臘]][[史家]][[普魯塔克]]與[[克律西波斯]]、[[喜帕恰斯]]討論了後來顯示與{{link-en|Schröder–Hipparchus數|Schröder–Hipparchus number}}有關的枚舉問題<ref>[[Richard P. Stanley|Stanley, Richard P.]]; "Hipparchus, Plutarch, Schröder, and Hough", ''American Mathematical Monthly'' '''104''' (1997), no. 4, 344–350.</ref><ref>Habsieger, Laurent; Kazarian, Maxim; and Lando, Sergei; "[http://search.proquest.com/openview/70485cece23ca51b18536b4422cc5586/1?pq-origsite=gscholar&cbl=47349 On the Second Number of Plutarch]", ''American Mathematical Monthly'' '''105''' (1998), no. 5, 446.</ref>；西元前3世紀的[[阿基米德]]在其數學文章''{{link-en|Ostomachion|Ostomachion}}''中考慮了一個拼接拼圖的智力遊戲（tiling puzzle）。
-[[中世紀]]時，組合數學持續發展（主要是在[[歐洲]]外的文明）。西元850年的[[印度]]數學家{{link-en|Mahāvīra|Mahāvīra (mathematician)}}提供了關於[[排列]]數與[[組合]]的公式<ref>{{MacTutor|id=Mahavira}}</ref><ref>{{Citation|last=Puttaswamy|first=Tumkur K.|contribution=The Mathematical Accomplishments of Ancient Indian Mathematicians|editor-last=Selin|editor-first=Helaine|title=Mathematics Across Cultures: The History of Non-Western Mathematics|publisher=Kluwer Academic Publishers|location=Netherlands|url=https://books.google.com/books?id=2hTyfurOH8AC&printsec=frontcover|year=2000|isbn=978-1-4020-0260-1|page=417 <!-- pages 409–422 -->}}</ref>，甚至可能早在6世紀印度的數學家就對這些公式熟悉<ref>{{cite journal|title=The Roots of Combinatorics|url=|first1=Norman L.|journal=Historia Mathematica|issue=2|doi=10.1016/0315-0860(79)90074-0|year=1979|volume=6|pages=109–136|last1=Biggs}}</ref>。1140年[[哲學家]]與[[天文學家]][[阿伯拉罕·伊本·埃茲拉]]確認了二項式係數的對稱性，而二項式係數公式則是由[[猶太人]][[數學家]][[Gersonides]]在1321年得到的<ref>{{citation|title=Probability Theory: A Historical Sketch|first=L.E.|last=Maistrov|publisher=Academic Press|year=1974|isbn=978-1-4832-1863-2|url=https://books.google.com/books?id=2ZbiBQAAQBAJ&pg=PA35|page=35}}. (Translation from 1967 Russian ed.)</ref>。[[楊輝三角形]]最早可追溯至10世紀的數學論文，在[[中国|中國]]則首現於13世紀[[南宋]][[杨辉|楊輝]]的《[[詳解九章算法]]》。在[[英格蘭]]，則出現一些與[[哈密頓圖|哈密頓迴路]]相關的例子<ref>
+[[中世紀]]時，組合數學持續發展（主要是在[[歐洲]]外的文明）。西元850年的[[印度]]數学家{{link-en|Mahāvīra|Mahāvīra (mathematician)}}提供了關於[[排列]]數與[[組合]]的公式<ref>{{MacTutor|id=Mahavira}}</ref><ref>{{Citation|last=Puttaswamy|first=Tumkur K.|contribution=The Mathematical Accomplishments of Ancient Indian Mathematicians|editor-last=Selin|editor-first=Helaine|title=Mathematics Across Cultures: The History of Non-Western Mathematics|publisher=Kluwer Academic Publishers|location=Netherlands||year=2000|isbn=978-1-4020-0260-1|page=417 <!-- pages 409–422 -->}}</ref>，甚至可能早在6世紀印度的數学家就對這些公式熟悉<ref>{{cite journal|title=The Roots of Combinatorics|url=|first1=Norman L.|journal=Historia Mathematica|issue=2|doi=10.1016/0315-0860(79)90074-0|year=1979|volume=6|pages=109–136|last1=Biggs}}</ref>。1140年[[哲学家]]與[[天文学家]][[阿伯拉罕·伊本·埃茲拉]]確認了二項式係數的對稱性，而二項式係數公式則是由[[猶太人]][[數学家]][[Gersonides]]在1321年得到的<ref>{{citation|title=Probability Theory: A Historical Sketch|first=L.E.|last=Maistrov|publisher=Academic Press|year=1974|isbn=978-1-4832-1863-2||page=35}}. (Translation from 1967 Russian ed.)</ref>。[[楊輝三角形]]最早可追溯至10世紀的數學論文，在[[中国|中國]]則首現於13世紀[[南宋]][[杨辉|楊輝]]的《[[詳解九章算法]]》。在[[英格兰]]，則出現一些與[[哈密頓圖|哈密頓迴路]]相關的例子<ref>
 White, Arthur T.; "Ringing the Cosets", ''American Mathematical Monthly'', '''94''' (1987), no. 8, 721–746; White, Arthur T.; "Fabian Stedman: The First Group Theorist?", ''American Mathematical Monthly'', '''103''' (1996), no. 9, 771–778.</ref>。
-[[文藝復興時期]]，與其他數學或[[科學]]領域一樣，組合數學再現生機。[[布萊茲·帕斯卡|帕斯卡]]、[[艾薩克·牛頓|牛頓]]、[[雅各布·白努利]]、[[李昂哈德·歐拉|歐拉]]等人的研究為此新興領域打下基礎。在更近代時，[[詹姆斯·約瑟夫·西爾維斯特|西爾維斯特]]和{{link-en|MacMahon|Percy Alexander MacMahon}}也對[[组合计数|組合計數]]和[[代數組合學]]作出貢獻。人們此時也對[[圖論]]有高度的興趣，例如關於[[四色定理|四色問題]]的領域。
+[[文藝復興時期]]，與其他數學或[[科学]]領域一樣，組合數學再現生機。[[布萊茲·帕斯卡|帕斯卡]]、[[艾薩克·牛頓|牛頓]]、[[雅各布·白努利]]、[[李昂哈德·歐拉|歐拉]]等人的研究為此新興領域打下基礎。在更近代時，[[詹姆斯·約瑟夫·西爾維斯特|西爾維斯特]]和{{link-en|MacMahon|Percy Alexander MacMahon}}也對[[组合计数|組合計數]]和[[代數組合學]]作出貢獻。人們此時也對[[圖論]]有高度的興趣，例如關於[[四色定理|四色問題]]的領域。
 在20世紀下半葉，組合數學成長相當快速，甚至出現數十種新的期刊和會議<ref>See [http://www.math.iit.edu/~kaul/Journals.html#CGT Journals in Combinatorics and Graph Theory]</ref>。 在某種程度上，這樣的成長是由對其他領域的連結與應用所帶動，包括[[代數]]、[[機率論]]、[[泛函分析]]和[[數論]]等。
@@ 第36行： / 第36行： @@
 :<math> P = \frac{1}{336}= 0.00298</math>
-不過，中國大陸的教科書則是把從n取k的情況記作<math>P^k_n</math>或<math>A^k_n</math>（A代表Arrangement，即排列<ref>{{cite book|title=普通高中课程标准实验教科书 数学 选修2-3 B版|publisher=人民教育出版社|isbn=9787107187544|pages=10}}</ref>）。
+不過，中国的教科書則是把從n取k的情況記作<math>P^k_n</math>或<math>A^k_n</math>（A代表Arrangement，即排列<ref>{{cite book|title=普通高中课程标准实验教科书 数学 选修2-3 B版|publisher=人民教育出版社|isbn=9787107187544|pages=10}}</ref>）。
 上面的例子是建立在取出元素不重複出現狀況。
@@ 第43行： / 第43行： @@
 :<math> U_k^n = n^k</math><ref name="組合數學">{{cite book | title=組合數學 ─算法與分析─ | publisher=九章出版社 |  pages=29}} OCLC:44527392</ref>
-以[[中華民國公益彩券|四星彩]]為例，10個數字取4個數字，因可能重複所以排列數量為：
+以[[中华民国公益彩券|四星彩]]為例，10個數字取4個數字，因可能重複所以排列數量為：
 :<math>U_4^{10}=10^4=10000</math>
@@ 第56行： / 第56行： @@
 :<math>C_k^n ={n \choose k} = \frac{P_k^n}{k!} = \frac{n!}{k!(n-k)!}</math>
-不過，中國大陸的教科書則是把從<math>n</math>取<math>k</math>的情況記作<math>C^k_n</math><ref>{{cite book|title=普通高中课程标准实验教科书 数学 选修2-3 B版|publisher=人民教育出版社|isbn=9787107187544|pages=16}}</ref>。
+不過，中国的教科書則是把從<math>n</math>取<math>k</math>的情況記作<math>C^k_n</math><ref>{{cite book|title=普通高中课程标准实验教科书 数学 选修2-3 B版|publisher=人民教育出版社|isbn=9787107187544|pages=16}}</ref>。
 以[[六合彩]]為例。在六合彩中从49顆球中取出6顆球的组合數量为：
@@ 第69行： / 第69行： @@
 :<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>
@@ 第102行： / 第102行： @@
 == 參考文獻 ==
 {{reflist}}
 == 外部連結 ==
 * [http://www.combinatorics.net/ The Combinatorics Net]