Jump to content

History of combinatorics

This is a fully translated article. Click here for more information.
From DawoumWiki, the free Mathematics self-learning
Original article: w:History of combinatorics

조합론(combinatorics)의 수학 분야는 수많은 고대 사회에서 다양한 각도로 연구되었습니다. 유럽에서 그것의 연구는 기원후 13세기에서 레오나르도 피보나치(Leonardo Fibonacci)의 연구로 시작되었으며, 이것은 아라비아와 인도의 아이디어를 대륙에 소개했습니다. 그것은 현대 시대에서 계속해서 연구되어 왔습니다.

Earliest records

A portion of the Rhind papyrus.

조합론적 기법의 가장 초기의 기록된 사용은, 기원전 16세기까지 거슬러 올라가는, 린드 파피루스(Rhind Papyrus)의 문제 79에서 비롯됩니다. 그 문제는 특정 기하 급수에 관련이 있고, 주어진 전체에 대한 합이 되는 1과 2의 합성(compositions)의 숫자를 세는 피보나치의 문제와 닮음을 가집니다.[1]

그리스에서, 플루타르코스(Plutarch)는 칼케돈(Chalcedon)의 저나크러티즈(Xenocrates) (기원전 396–314)가 그리스 언어에서 가능한 다른 음절의 숫자를 발견했다고 썼습니다. 이것은 순열과 조합(permutations and combinations)에서 어려운 문제를 풀기 위한 기록의 최초의 시도였을 것입니다.[2] 그 주장은, 어쨌든, 믿어지지 않습니다: 이것은 그리스에서 조합론의 몇 안되는 언급 중 하나이고, 그들이 발견한 숫자, 1.002 × 10 12는 추측 이상의 너무 큰 반올림 오차가 있는 것으로 보입니다.[3][4]

바가버티 수트라(Bhagavati Sutra)는 조합론 문제의 첫 번째 언급을 가졌습니다; 그 문제는 맛의 가능한 조합이 6가지 다른 맛 (단맛, 매운맛, 떫은맛, 신맛, 짠맛 및 쓴맛)의 선택으로부터 하나, 둘, 셋, 등에서 맛을 선택하는 것으로부터 얼마나 많은지를 물었습니다. 바가버티는 역시 선택 함수(choose function)를 언급하는 첫 번째 텍스트입니다.[5] 기원전 2세기에서, 핀갈라(Pingala)는 찬다 수트라(Chanda Sutra) (또한 Chandahsutra)에 열거 문제를 포함했으며, 그것은 육-음절 박자는 짧은 음과 긴 음으로부터 얼마나 많은 방법으로 만들 수 있는지를 물었습니다.[6][7] 핀갈라는 긴 음과 짧은 음을 가지는 박자의 숫자를 발견했습니다; 이것은 이항 계수(binomial coefficients)를 찾는 것과 동등합니다.

바가버티의 아이디어는 기원후 850년에서 인도의 수학자 마하비라(Mahavira)에 의해 일반화되었었고, 운율(prosody)에 관한 핀갈라의 연구는 기원후 1100년에서 바스카라 2세(Bhāskara II)와[5][8] 헤마찬드라(Hemacandra)에 의해 확장되었습니다. 바스카라는, 비록 브라마굽타(Brahmagupta)가 이전에 알고 있었을지라도, 일반화된 선택 함수를 찾기 위한 최초의 알려진 사람이었습니다.[1] 헤마칸드라는, 만약 긴 음이 짧은 음의 두 배 긴 것으로 고려되면, 특정 길이의 박자가 얼마나 많이 존재하는지를 물었는데, 이것은 피보나치 숫자(Fibonacci numbers)를 찾는 것과 동등합니다.[6]

A hexagram

예언의 고대 중국의 책 역경(I Ching)은 헥사그램을 여섯 줄의 반복을 갖는 순열로 설명하며, 여기서 각 줄은 두 상태: 실선 또는 점선 중 하나가 될 수 있습니다. 이 방식으로 헥사그램을 설명하는 것에서, 그것들은 가능한 헥사그램이 있음을 결정합니다. 중국 수도사는 기원후 700년경 바둑(Go)과 비슷한 게임에 대한 구성의 숫자를 역시 계산했을 수 있습니다.[3] 비록 중국이 열거적 조합론에서 상대적으로 발전이 거의 없었지만, 기원후 100년경 그들은 차수 삼의 보통 마법의 정사각형(magic square)의 조합론적 디자인(combinatorial design) 문제인, 낙서 정사각형(Lo Shu Square)을 해결했습니다.[1][9] 마법의 정사각형은 중국의 관심사로 남았었고, 그들은 기원후 900과 1300년 사이에 그들의 원래 정사각형을 일반화하기 시작했습니다. 중국은 13세기에서 이 문제에 대해 중동과 일치했습니다.[1] 중동은 역시 인도 연구에서 이항 계수에 대해 배웠었고 다항식 전개에 대한 연결을 발견했습니다.[10] 힌두교의 연구는 음절을 형성하기 위한 문자의 가능한 배열을 고려한 알-칼릴 이븐 아흐메드(Al-Khalil ibn Ahmad)의 연구에서 알 수 있듯이 아랍인에게 영향을 미쳤습니다. 그의 계산은 순열과 조합의 이해를 보여줍니다. 1100년경에 시작되는 아랍 수학자 우마르 알-카이야미(Umar al-Khayyami)의 연구로부터의 한 구절에서, 힌두교들은 이항 계수의 지식을 가졌었지만, 역시 그들의 방법은 중동에 도달했음을 확증했습니다.

그리스에서, 플루타르코스(Plutarch)는 저나크러티즈(Xenocrates)가 그리스 언어에서 가능한 다른 음절의 숫자를 발견했다고 썼습니다. 반면에 있을 것 같지 않지만, 이것은 그리스에서 조합론의 몇 안되는 언급 중 하나입니다. 그들이 발견한 숫자, 1.002 × 10 12는 역시 추측 이상의 너무 큰 반올림 오차가 있는 것으로 보입니다.[3][4]

알-카라지(Al-Karaji) (c.953–1029)는 이항 정리와 파스칼의 삼각형에 대해 썼습니다. 알-사마월(Al-Samawal)에 의한 후속 인용으로 오직 알려진 지금 잃어버린 연구에서, 알-카라지(Al-Karaji)는 수학적 귀납법에 의한 논증의 아이디어를 소개했습니다.

철학자(philosopher)이자 천문학자(astronomer) 롸바이 아브라함 이븐 에즈라(Abraham ibn Ezra) (c. 1140)는 신성한 이름의 발성에서 반복을 갖는 순열을 계산했습니다.[11] 그는 이항 계수(binomial coefficient)의 대칭성을 역시 확립했지만, 닫힌 공식은 1321년에서 탈무드주의자(talmudist)이자 수학자(mathematician) (게르소니데스(Gersonides)로 더 잘 알려진) 레비 벤 게르손(Levi ben Gerson)에 의해 나중에 얻어졌습니다.[12] 산술적 삼각형–이항 계수(binomial coefficient) 사이의 관계를 보여주는 그래픽 다이어그램–은 10세기에 거슬러 올라가는 논문에서 수학자들에 의해 발표되었고, 결국에는 파스칼의 삼각형(Pascal's triangle)으로 알려지게 될 것입니다. 나중에, 중세 잉글랜드(Medieval England)에서, 캠퍼날러지(campanology)는 순열에 대한 특정 케일리 그래프(Cayley graph)에서 해밀턴 순환(Hamiltonian cycle)으로 지금 알려진 사례를 제공했습니다.[13]

Combinatorics in the West

조합론은 수학자 레오나르도 피보나치(Leonardo Fibonacci)와 요르다누스 데 네모레(Jordanus de Nemore)를 통해 13세기에 유럽에 왔습니다. 피보나치의 리버 아바치(Liber Abaci)는 피보나치 숫자를 포함하여 아라비아인과 인도인의 많은 아이디어를 유럽에 소개했습니다.[14][15] 요르다누스는, 그가 De Arithmetica의 전제 70에서 했던 것처럼, 삼각형에서 이항 계수를 배열한 최초의 사람이었습니다. 이것은 역시 1265년에 중동과 1300년경 중국에서 행해졌습니다.[1] 오늘날, 이 삼각형은 파스칼의 삼각형(Pascal's triangle)으로 알려져 있습니다.

그의 이름을 가진 삼각형에 대한 파스칼(Pascal)의 기여는 그것에 대한 공식적인 증명에 대한 그의 연구와 파스칼의 삼각형과 확률 사이의 연결을 만든 것에 기인합니다.[1] 라이프니츠(Leibniz)가 다니엘 베르누이(Daniel Bernoulli)에게 보낸 편지에서, 우리는, 비록 공식적인 연구가 발표되지는 않았을지라도, 라이프니츠가 17세기에서 분할(partitions)의 수학적 이론을 공식적으로 연구했었음을 압니다. 라이프니츠와 함께, 파스칼은 나중에 재출판된 1666년에 De Arte Combinatoria를 출판했습니다.[16] 파스칼과 라이프니츠는 현대 조합론의 창시자로 여겨집니다.[17]

파스칼과 라이프니츠 둘 다는 이항 전개(binomial expansion)가 선택 함수(choice function)와 동등하다는 것을 이해했습니다. 대수학과 조합론이 대응되었던 그 개념은 드 무아브르(De Moivre)에 의해 확장되었으며, 그는 다항(multinomial)의 전개를 발견했습니다.[18] 드 무아브르는, 이전에 그것을 발견했었던, 니콜라우스 베르누이(Nikolaus Bernoulli)와는 다른 방법, 포함-제외의 원리(principle of inclusion-exclusion)를 사용하여 교란에 대한 공식을 역시 발견했습니다.[1] 드 무아브르는 이항 계수(binomial coefficient)와 팩토리얼(factorial)을 근사화하는 데 역시 성공했었고, 생성 함수(generating functions)를 발명함으로써 피보나치 숫자에 대해 닫힌 형식을 발견했습니다.[19][20]

18세기에서, 오일러(Euler)는 조합론의 문제와 조합론과 연결된 확률의 여러 문제를 연구했습니다. 오일러가 연구했던 문제는 기사 이동(Knights tour), 그레코-라틴 정사각형(Graeco-Latin square), 오일러 숫자(Eulerian numbers), 및 다른 것을 포함합니다. 쾨니히스베르크의 일곱 다리(Seven Bridges of Königsberg) 문제를 해결하기 위해, 그는 그래프 이론을 발명했는데, 그것은 토폴로지(topology)의 형성으로 역시 이어졌습니다. 마지막으로, 그는 생성 함수(generating functions)의 사용에 의해 분할(partitions)과 지평을 열었습니다.[21]

Contemporary combinatorics

19세기에서, 부분적으로 순서화 집합(partially ordered set)과 격자 이론(lattice theory)의 주제가 데데킨트(Dedekind), 퍼스(Peirce) 및 슈뢰더(Schröder)의 연구에서 시작되었습니다. 어쨌든, 그것은 1967년에 출판된 그의 책 Lattice Theory에서 개릿 버코프(Garrett Birkhoff)의 발생의 연구와[22] 주제를 실제로 확립한 존 폰 노이만(John von Neumann)의 연구였습니다.[23] 1930년대에서, 홀(Hall) (1936)과 와이즈너(Weisner) (1935)는 일반적인 뫼비우스 반전 공식을 독립적으로 설명했습니다.[24] 1964년에서, 지안-카를로 로타(Gian-Carlo Rota)의 On the Foundations of Combinatorial Theory I. Theory of Miibius Functions 은 조합론에서 이론으로 부분적으로 순서화 집합(poset)과 격자 이론을 도입했습니다.[23] 리처드 스탠리(Richard P. Stanley)는 매트로이드 이론에서 그의 연구,[25] 제타 다항식을 도입하는 것,[26] 오일러 포셋을 명시적으로 정의하는 것,[27] 로타와 피터 더우블렛(Peter Doubilet)과 함께 이항 포셋의 이론을 개발하는 것,[28] 및 더 많은 것에 대해 현대 조합론에 큰 영향을 끼쳐 왔습니다.

Notes

  1. ^ a b c d e f g Biggs, Norman; Keith Lloyd; Robin Wilson (1995). "44". In Ronald Graham; Martin Grötschel; László Lovász (eds.). Handbook of Combinatorics (Google book). MIT Press. pp. 2163–2188. ISBN 0-262-57172-2. Retrieved 2008-03-08.
  2. ^ Heath, Sir Thomas (1981). A history of Greek mathematics (Reprod. en fac-sim. ed.). New York: Dover. ISBN 0486240738.
  3. ^ a b c Dieudonné, J. "The Rhind/Ahmes Papyrus - Mathematics and the Liberal Arts". Historia Math. Truman State University. Archived from the original on 2012-12-12. Retrieved 2008-03-06.
  4. ^ a b Gow, James (1968). A Short History of Greek Mathematics. AMS Bookstore. p. 71. ISBN 0-8284-0218-3.
  5. ^ a b "India". Archived from the original on 2007-11-14. Retrieved 2008-03-05.
  6. ^ a b Hall, Rachel (2005-02-16). "Math for Poets and Drummers-The Mathematics of Meter" (PDF). Retrieved 2008-03-05. {{cite journal}}: Cite journal requires |journal= (help)
  7. ^ Kulkarni, Amba (2007). "Recursion and Combinatorial Mathematics in Chandashāstra". arXiv:math/0703658. Bibcode:2007math......3658K. {{cite journal}}: Cite journal requires |journal= (help)
  8. ^ Bhaskara. "The Lilavati of Bhaskara". Brown University. Archived from the original on 2008-03-25. Retrieved 2008-03-06.
  9. ^ Swaney, Mark. "Mark Swaney on the History of Magic Squares". Archived from the original on 2004-08-07.
  10. ^ "Middle East". Archived from the original on 2007-11-14. Retrieved 2008-03-08.
  11. ^ The short commentary on Exodus 3:13
  12. ^ History of Combinatorics, chapter in a textbook.
  13. ^ Arthur T. White, ”Ringing the Cosets,” Amer. Math. Monthly 94 (1987), no. 8, 721-746; Arthur T. White, ”Fabian Stedman: The First Group Theorist?,” Amer. Math. Monthly 103 (1996), no. 9, 771-778.
  14. ^ Devlin, Keith (October 2002). "The 800th birthday of the book that brought numbers to the west". Devlin's Angle. Retrieved 2008-03-08.
  15. ^ "Fibonacci Sequence- History". Net Industries. 2008. Retrieved 2008-03-08.
  16. ^ Leibniz's habilitation thesis De Arte Combinatoria was published as a book in 1666 and reprinted later
  17. ^ Dickson, Leonard (2005) [1919]. "Chapter III". Diophantine Analysis. History of the Theory of Numbers. Mineola, New York: Dover Publications, Inc. p. 101. ISBN 0-486-44233-0.
  18. ^ Hodgson, James; William Derham; Richard Mead (1708). Miscellanea Curiosa (Google book). Volume II. pp. 183–191. Retrieved 2008-03-08.
  19. ^ O'Connor, John; Edmund Robertson (June 2004). "Abraham de Moivre". The MacTutor History of Mathematics archive. Retrieved 2008-03-09.
  20. ^ Pang, Jong-Shi; Olvi Mangasarian (1999). "10.6 Generating Function". In Jong-Shi Pang (ed.). Computational Optimisation (Google book). Volume 1. Netherlands: Kluwer Academic Publishers. pp. 182–183. ISBN 0-7923-8480-6. Retrieved 2008-03-09.
  21. ^ "Combinatorics and probability". Retrieved 2008-03-08.
  22. ^ Birkhoff, Garrett (1984). Lattice theory (3d ed., reprinted with corrections. ed.). Providence, R.I.: American Mathematical Society. ISBN 978-0821810255.
  23. ^ a b Stanley, Richard P. (2012). Enumerative combinatorics (2nd. ed.). Cambridge: Cambridge University Press. pp. 391–393. ISBN 978-1107602625.
  24. ^ Bender, Edward A.; Goldman, J. R. (1975). "On the applications of Möbius inversion in combinatorial analysis". Amer. Math. Monthly. 82 (8): 789–803. doi:10.2307/2319793. JSTOR 2319793.
  25. ^ Stanley, Richard (2007). "An introduction to hyperplane arrangements". Geometric Combinatorics. IAS/Park City Mathematics Series. 13 (IAS/Park City Mathematics Series): 389–496. doi:10.1090/pcms/013/08. ISBN 9780821837368.
  26. ^ Stanley, Richard (1974). "Combinatorial reciprocity theorems". Advances in Mathematics. 14 (2): 194–253. doi:10.1016/0001-8708(74)90030-9.
  27. ^ Stanley, Richard (1982). "Some aspects of groups acting on finite posets". Journal of Combinatorial Theory. Ser. A 32 (2): 132–161. doi:10.1016/0097-3165(82)90017-6.
  28. ^ Stanley, Richard (1976). "Binomial posets, M¨obius inversion, and permutation enumeration". Journal of Combinatorial Theory. Ser. A 20 (3): 336–356. doi:10.1016/0097-3165(76)90028-5.

References

  • N.L. Biggs, The roots of combinatorics, Historia Mathematica 6 (1979), 109–136.
  • Katz, Victor J. (1998). A History of Mathematics: An Introduction, 2nd Edition. Addison-Wesley Education Publishers. ISBN 0-321-01618-1.
  • O'Connor, John J. and Robertson, Edmund F. (1999–2004). MacTutor History of Mathematics archive. St Andrews University.
  • Rashed, R. (1994). The development of Arabic mathematics: between arithmetic and algebra. London.
  • Wilson, R. and Watkins, J. (2013). Combinatorics: Ancient & Modern. Oxford.
  • Stanley, Richard (2012). Enumerative combinatorics (2nd ed. ed.), 2nd Edition. Cambridge University Press. ISBN 1107602629.

Retrieved from "https://dawoum.duckdns.org/w/index.php?title=History_of_combinatorics&oldid=81319"