콤비네이터의 역사

수학적 결합학 분야는 수많은 고대 사회에서 다양한 정도로 연구되었다. 유럽에서의 연구는 AD 13세기 레오나르도 피보나찌의 작품으로, 아프리카와 인도 사상을 유럽에 소개한 것이다. 현대에도 계속 연구되어 왔다.

가장 이른 기록

결합기법의 가장 초기 기록적인 사용은 기원전 16세기까지 거슬러 올라가는 린드 파피루스의 79번 문제에서 비롯되었다. 이 문제는 특정한 기하학적 시리즈와 관련이 있으며, 피보나찌가 주어진 총합에 해당하는 1초와 2초의 구성 수를 세는 문제와 유사하다.^[1]

그리스에서, 플루타르크는 찰케돈의 제노크라테스 (기원전 396년–314년)가 그리스어로 가능한 다양한 음절의 수를 발견했다고 썼다. 이것은 순열과 조합에서 어려운 문제를 해결하기 위한 최초의 기록적인 시도였을 것이다.^[2] 그러나 이 주장은 설득력이 없다. 이것은 그리스에서 몇 안 되는 조합의 언급 중 하나이며, 그들이 발견한 숫자 1.002 × 10은 ¹² 추측 이상일 정도로 너무 둥글어 보인다.^[3][4]

나중에 슈뢰더-히파르쿠스 숫자와 관련이 있는 것으로 드러난 다소 미묘한 열거형 문제에 대한 크리시푸스(기원전 3세기)와 히파르쿠스(기원전 2세기)의 주장이 거론된다.^[5][6] 오스토마치온에서 아르키메데스(기원전 3세기)가 타일링 퍼즐의 구성을 고려했다는 증거도 있는 반면, 아폴로니우스의 잃어버린 작품에는 일부 조합적 이해관계가 존재했을 수도 있다.^[7][8][9]

인도에서 바가바티 수트라는 콤비네이터 문제에 대해 처음 언급했는데, 문제는 여섯 가지 다른 맛(단맛, 톡 쏘는 맛, 신맛, 소금맛, 쓴맛) 중에서 한 가지 맛, 두 가지 맛, 세 가지 맛 등 중에서 몇 가지 가능한 조합이 가능한지를 물었다. Bhagavati는 선택 함수를 언급한 첫 번째 텍스트이기도 하다.^[10] 기원전 2세기에 핑갈라는 찬다 수트라(또한 찬다수트라)에 열거 문제를 포함시켰는데, 이 문제는 6음절 계량기가 짧고 긴 음표로 얼마나 많은 방법으로 만들어질 수 있는지를 물었다.^[11][12] 핑갈라는 $n{\displaystyle }$ ${\displaystyle n}$개의$$ 긴 음과 k ${\displaystyle k}$의 짧은 음이 포함된 미터 수를 찾았는데, 이는 이항계수를 찾는 것과 같다.

바가바티의 사상은 서기 850년에 인도의 수학자 마하비라에 의해 일반화되었고, 핑갈라의 프로소디에 관한 작업은 서기 1100년에 바스카라 2세와^[10][13] 헤마칸드라에 의해 확대되었다. 브라카굽타가 더 일찍 알았을지는 몰라도 바르샤라는 일반화된 선택 기능을 발견한 최초의 인물로 알려져 있었다.^[1] 헤마칸드라는 긴 음표가 짧은 음표보다 두 배나 길다고 생각될 경우 일정한 길이의 몇 미터가 존재하는지 물었는데, 이는 피보나치 숫자를 찾는 것과 맞먹는다.^[11]

고대 중국의 점괘 I 칭( hex)은 각 선들이 고체 또는 점선 두 상태 중 하나가 될 수 있는 6개의 선들이 반복되는 순열로 육각형을 묘사하고 있다. 이러한 방식으로 16진법을 설명할 때 그들은 2 ${\displaystyle {6\mathrm{}}^{}}$= ${\displaystyle 64}$ ${\displaystyle$ 2$^{6}=64}$의 가능한$$ 16진법이 있다고 판단한다. 중국의 승려도 AD 700년 경 바둑과 비슷한 게임에 구성의 수를 세었을 것이다.^[3] 중국은 열거형 콤비네이터의 발전이 비교적 적었지만 AD 100년경 그들은 순서 3의 정상적인 매직 스퀘어의 콤비네이터 디자인 문제인 로슈 스퀘어를 해결했다.^[1][14] 마법의 광장은 중국의 관심사로 남아 있었고, AD 900년에서 1300년 사이에 원래의 $3{\displaystyle \mathrm{}}$ ${\displaystyle \times }$ $[\displaystyle 3\time$ 3$} 제곱$을 일반화하기 시작했다. 중국은 13세기에 이 문제에 대해 중동과 대응했다.^[1] 중동도 인도 작품에서 이항계수에 대해 배웠고 다항식 팽창과의 연관성을 발견했다.^[15] 힌두교인들의 작품은 알-칼릴 이븐 아흐마드의 작품에서 볼 수 있듯이 아랍인들에게 영향을 끼쳤다. 그는 음절을 형성하기 위한 문자의 배열 가능성을 고려했다. 그의 계산은 순열과 조합에 대한 이해를 보여준다. 아랍의 수학자 우마르 알 카야미의 작품에서 1100년 경에 이르는 한 구절에서 힌두교도들이 이항계수에 대한 지식을 갖고 있었음은 물론 그들의 방법이 중동에도 이르렀음을 확증한다.

아부 바크르 이븐 무아마드 이븐 알 우사인 알 카라지(c.953-1029)는 이항 정리 및 파스칼의 삼각형에 대해 썼다. 알-사마우알의 후속 인용으로만 알려진 지금 잃어버린 작품에서 알-카라지는 수학 유도에 의한 논쟁의 개념을 소개했다.

철학자 겸 천문학자 랍비 아브라함 이븐 에즈라(c. 1140)는 신명을 발성할 때 반복적으로 순열을 세었다.^[16] 그는 또한 이항계수의 대칭성을 확립한 반면, 닫힌 공식은 1321년 탈무디스트와 수학자 레비 벤 거슨(게르소니데스라고 더 잘 알려진)에 의해 얻어졌다.^[17] 산술적 삼각형, 즉 이항계수들 사이의 관계를 보여주는 그래픽 다이어그램은 수학자들에 의해 10세기까지 거슬러 올라가는 논문에서 제시되었고, 결국 파스칼의 삼각형으로 알려지게 되었다. 후에 중세 영국에서, 캠파놀로지에서는 현재 해밀턴 사이클이라고 알려진 것을 순열 그래프에 보여주는 예시를 제공했다.^[18]

서양의 콤비네이터틱스

콤비네토릭스는 13세기에 수학자 레오나르도 피보나찌와 요르단우스 드 네모어를 통해 유럽으로 건너왔다. 피보나찌의 리베르 아바시는 피보나찌 숫자를 포함한 많은 아라비아와 인도 사상을 유럽에 소개했다.^[19][20] 요르단우스는 드 산티아카 제70호에서처럼 이항계수를 삼각형으로 배열한 최초의 인물이었다. 이는 1265년 중동, 1300년경 중국에서도 이루어졌다.^[1] 오늘날 이 삼각형은 파스칼의 삼각형으로 알려져 있다.

파스칼이 자신의 이름이 새겨진 삼각형에 기여한 것은 그것에 대한 형식적인 증거에 대한 그의 연구와 파스칼의 삼각형과 확률 사이에서 그가 만든 연결고리에서 비롯된다.^[1] 라이프니즈가 다니엘 베르누이에게 보낸 편지에서 우리는 라이프니즈가 비록 공식적인 저작은 발표되지 않았지만 17세기에 공식적으로 칸막이의 수학 이론을 연구하고 있었다는 것을 알게 된다. 라이프니즈와 함께 파스칼은 1666년에 데 아르테 콤비나토리아를 출판했고, 이후 다시 인쇄되었다.^[21] 파스칼과 라이프니즈는 현대 콤비네이터학의 창시자로 여겨진다.^[22]

파스칼과 라이프니즈 모두 이항 팽창이 선택 함수와 동등하다는 것을 이해했다. 대수학과 콤비네이터가 대응한다는 개념은 다항체의 확장을 발견한 드 모이브르에 의해 확대되었다.^[23] 드 모이브레는 또한 이전에 그것을 발견했던 니콜라우스 베르누이와는 다른 방법인 포함-배제 원칙의 원리를 이용한 변칙의 공식을 발견했다.^[1] De Moivre는 또한 이항계수와 요인을 근사하게 하는데 성공했으며, 생성함수를 발명하여 피보나치 수치에 대한 폐쇄형 형태를 찾아냈다.^[24][25]

18세기에 오일러는 콤비네이터의 문제와 콤비네이터릭과 연계된 확률의 여러 문제를 연구했다. 오일러가 작업한 문제로는 나이트 투어, 그라코-라틴 광장, 오일러 숫자 등이 있다. 쾨니히스베르크의 일곱 다리 문제를 해결하기 위해 그는 그래프 이론을 발명했고, 이 이론은 또한 위상 형성을 이끌었다. 마침내, 그는 생성 기능을 이용하여 칸막이로 땅을 팠다.^[26]

컨템포러리 콤비네이터틱스

19세기에 부분적으로 순서가 정해진 세트와 격자 이론의 주제는 드데킨드, 페어체, 슈뢰더의 작품에서 비롯되었다. 그러나 1967년에 출간된 그의 저서 래티스 이론에서 개럿 비르코프의 정석적인 작품과,^[27] 주제를 진정으로 정립한 것은 존 폰 노이만의 작품이었다.^[28] 1930년대에 홀(1936년)과 위스너(1935년)는 독립적으로 일반적인 뫼비우스 반전 공식을 명기했다.^[29] 1964년, 지안 카를로 로타는 결합 이론 1의 기초 위에 있다. 뫼비우스 함수 이론은 콤비네토릭스에 양자리 이론과 격자 이론을 이론으로 도입했다.^[28] 리처드 P. 스탠리는 현대 콤비네이터학에 큰 영향을 끼쳤다. 그의 모태론 연구,^[30] 제타 다항식 소개,^[31] 오일러 포셋을 명시적으로 정의하기 위한 것,^[32] 로타, 피터 두빌렛과 함께 이항 포셋 이론을 개발하는 것 ^[33]등.

메모들

참조

• N.L. Biggs, 콤비네이터학의 뿌리, Historyia Mathematica 6 (1979), 109–136.
• 캣츠, 빅터 J. (1998년). 수학의 역사: 서론 2판. 애디슨 웨슬리 교육 출판사. ISBN 0-321-01618-1.
• 오코너, 존 J, 로버트슨, 에드먼드 F. (1999–2004) MacTutor History of Mathical 아카이브. 세인트 앤드루스 대학교.
• R. R. (1994). 아랍 수학의 발달: 산술과 대수 사이. 런던
• Wilson, R., Watkins, J. (2013). 콤비네이터틱스: 고대 & 모던. 옥스퍼드 대학
• 스탠리, 리처드(2012년). 열거적 결합기(2차 개정판), 2차 개정판. 케임브리지 대학 출판부. ISBN 1107602629.