조합론 문서 원본 보기

{{위키데이터 속성 추적}}
'''조합론'''(組合論, {{llang|en|combinatorics}}) 또는 '''조합수학'''(組合數學)은 유한하거나 [[가산 집합|가산적]]인 구조들에 대하여, 어떤 주어진 성질을 만족시키는 것들의 가짓수나 어떤 주어진 성질을 극대화하는 것을 연구하는 [[수학]] 분야이다.

== 분류 ==
조합론에서는 다양한 종류의 조합론적 구조들을 다루며, 이들은 다음을 들 수 있다.
* '''[[순열]]'''과 '''[[조합]]'''. 이들을 세는 문제는 [[12정도]]라는 이름으로 체계화되어 있다.
* '''[[집합의 분할]]''', 특히 [[자연수의 분할]]
* '''문자열'''({{llang|en|word}})
* '''[[부분 순서 집합]]'''은 순서로 생각할 수 있는 관계를 부여한 집합이며, 특수한 경우로 [[전순서 집합]]이나 [[격자 (순서론)|격자]] 등이 있다. 이들을 연구하는 분야를 [[순서론]]이라고 한다.
* '''[[그래프]]'''는 일련의 꼭짓점들과 이들 사이를 잇는 변들로 구성된 조합론적 구조이다. 이들을 다루는 분야를 [[그래프 이론]]이라고 한다.
* '''[[매트로이드]]'''는 그래프를 일반화한 개념이다.
* '''유한 기하'''({{llang|en|finite geometry}})는 유한한 수의 점과 선 등으로 구성된 기하학적 공간이다. 이에 대하여 다양한 열거 문제를 고려할 수 있다.
* '''계획'''({{llang|en|design}})은 원래 통계학의 [[실험계획법]]에서 유래한 개념이다. [[라틴 방진]]이 이의 특수한 경우이다. 계획 이론은 유한 기하학과 [[코드 이론]]({{llang|en|coding theory}})과 밀접하게 연관되어 있다.

조합론은 다루는 대상 대신 사용하는 기법 또는 목표로서 분류할 수도 있다.
* '''계수적 조합론'''({{llang|en|enumerative combinatorics}})은 주어진 조건을 만족하는 대상의 수를 세는 것을 목표로 한다.
* '''해석적 조합론'''({{llang|en|analytic combinatorics}})은 [[해석학 (수학)|해석학적]] 기법을 조합론에 응용하며, 보통 주어진 대상의 정확한 수보다는 이들의 수의 점근적 공식({{llang|en|asymptotic formula}})을 목표로 한다. [[계승 (수학)|계승]]의 [[스털링 공식]]이 대표적인 예이다.
* '''극대 조합론'''({{llang|en|extremal combinatorics}})은 주어진 조건을 만족시키는 대상 가운데 "가장 큰" 또는 "가장 작은" 것 따위의 문제를 다룬다. 극대 그래프 이론은 그래프 이론에서 중요한 연구 분야의 하나이다. 다른 방향으로, [[램지 이론]]도 이에 속한다.
* '''위상수학적 조합론'''({{llang|en|topological combinatorics}})은 [[그래프]] 따위의 조합론적 구조에 [[위상 공간 (수학)|위상]]을 주어, [[보르수크-울람 정리]]나 [[호몰로지 대수학]]을 조합론적 문제에 응용한다. [[로바스 라슬로]]는 [[보르수크-울람 정리]]를 사용하여 [[크네저 그래프]]({{llang|en|Kneser graph}})에 대한 크네저 추측을 증명하였다.

=== 관련 분야 ===
조합론은 [[대수학]], [[확률론]], [[에르고딕 이론]], [[기하학]] 등 [[수학]]의 여러 분야와 관련되어 있다. 또한, [[전산학]], [[통계 물리학]] 같은 분야와도 관계가 있다.

== 역사 ==
=== 고대 ===
[[파일:Diagram_of_I_Ching_hexagrams_owned_by_Gottfried_Wilhelm_Leibniz,_1701.jpg|섬네일|right|《[[역경]]》에 등장하는 64괘]]
조합론의 기초 개념은 고대 수학에서부터 시작하였다. 기원전 10세기~기원전 4세기 [[주나라]]에서 집필된 《[[역경]]》은 양(⚊) 또는 음(⚋)의 값을 가질 수 있는 6개의 효(爻)로부터 64 = 2<sup>6</sup>개의 괘(卦)를 구성하였다. 기원전 6세기에 인도의 외과의사 수슈루타({{llang|sa|सुश्रुत}})는 의학서 《수슈루타상히타》({{llang|sa|सुश्रुतसंहिता}})에서, 6개의 기본 맛(단맛, 신맛, 짠맛, 쓴맛, 매운 맛, 떫은 맛)을 63 = 2<sup>6</sup> &minus; 1가지로 조합할 수 있다고 서술하였다. 이는 6개의 원소로 만들 수 있는 집합 가운데 [[공집합]]을 제외한 것들의 가짓수이다.

기원후 1세기 [[고대 그리스]]에서, [[플루타르코스]](46~120)는 에세이집 《윤리학》({{llang|grc|Ἠθικά|에티카}})의 49번째 에세이 〈잡담〉({{llang|grc|Συμποσιακά|심포시아카}}) 8권에서 다음과 같이 적었다.
{{인용문2|
[[크리시포스]]는 10개의 기초 명제로부터 만들 수 있는 합성 명제는 100만 개를 넘는다고 하였다. [[히파르코스]]는 물론 이는 거짓임을 보였으며, 긍정적 합성 명제는 10만3049개, 부정적 합성 명제는 31만952개임을 보였다.
<br>{{lang|grc|Καὶ Χρύσιππος τὰς ἐκ δέκα μόνων ἀξιωμάτων συμπλοκὰς πλήθει φησὶν ἑκατὸν μυριάδας ὑπερβάλλειν· ἀλλὰ τοῦτο μὲν ἤλεγξεν Ἵππαρχος, ἀποδείξας ὅτι τὸ μὲν καταφατικὸν περιέχει συμπεπλεγμένων μυριάδας δέκα καὶ πρὸς ταύταις τρισχίλια1 τεσσαράκοντ᾿ ἐννέα, τὸ δ᾿ ἀποφατικὸν αὐτοῦ μυριάδας τριάκοντα μίαν καὶ πρὸς ταύταις ἐνακόσια πεντήκοντα δύο·}}|<ref>{{서적 인용|저자=Πλούταρχος|저자링크=플루타르코스|제목=Ἠθικά|장=Συμποσιακά|쪽=VIII.9.732|장url=http://www.loebclassics.com/view/plutarch-moralia_table_talk/1961/pb_LCL425.195.xml|언어=el|}}</ref>}}
여기서 "긍정적 합성 명제"의 수
:<math>103\,049=s_{10}</math>
는 10번째 슈뢰더 수({{llang|en|Schröder number}}) <math>s_{10}</math>이며, 10개의 글자로 구성된 문자열에 괄호를 삽입할 수 있는 가짓수이다.<ref>{{저널 인용|성=Stanley|이름=R. P.|제목=Hipparchus, Plutarch, Schröder, and Hough|저널=American Mathematical Monthly|권=104|쪽=344–350|날짜=1997|url=http://www-math.mit.edu/~rstan/papers/hip.pdf}}</ref> "부정적 합성 명제"의 수
:<math>310\,952=(s_{10}+s_{11})/2</math>
는 10번째와 11번째 슈뢰더 수의 평균이다.<ref>{{저널 인용|성1=Habsieger|이름1=L.|성2=Kazarian, M.|성3=Lando, S.|제목=On the Second Number of Plutarch|url=https://archive.org/details/sim_american-mathematical-monthly_1998-05_105_5/page/n47|저널=American Mathematical Monthly|권=105|쪽=446|날짜=1998|언어=en}}</ref>

=== 중세 ===
[[파일:Yanghui triangle.gif|섬네일|right|양휘가 지은 《상해구장산법》(詳解九章算法)에 수록된 [[파스칼 삼각형]]]]
850년 경에 인도의 수학자 마하비라({{llang|sa|महावीर}})는 《산법 요론(要論)》({{llang|sa|गणितसारसंग्रह|가니타사라상그라하}})에서 [[순열]]과 [[조합]]의 수에 대한 공식을 제시하였다.

아랍 세계에서는 중세 스페인의 [[랍비]] 아브라함 이븐 에즈라({{llang|he|אברהם אבן עזרא}}, {{llang|la|Abenezra|아베네즈라}}, 1089~1167)는 [[이항 계수]]의 대칭성
:<math>\binom{n+k}n=\binom{n+k}k</math>
을 증명하였다. 1321년에 [[랍비]] 레비 벤 게르숀({{llang|he|לוי בן גרשום‏}}, {{llang|la|Gersonides|게르소니데스}}, 1288~1344)은 순열과 조합의 수에 대한 공식을 제시하였다.

[[송나라]]의 [[양휘]]는 《[[구장산술]]》에 대한 주석인 《상해구장산법》(詳解九章算法)에서 [[파스칼 삼각형]]을 제시하였다. 이는 전대의 수학자인 [[가헌]]의 업적을 바탕으로 한 것으로 보이나, 가헌의 저서들은 현존하지 않는다.

인도와 아랍 수학은 13세기에 유럽에 소개되었다. 이탈리아의 수학자 요르다누스 데 네모레({{llang|la|Jordanus de Nemore}}, {{llang|it|Giordano di Nemi|조르다노 디 네미}}, 13세기 경)는 《산술》({{llang|la|De elementis arithmetice artis|데 엘레멘티스 아리트메티케 아르티스}}) 명제 70번에서 [[이항 계수]]를 삼각형으로 배열하였는데, 이는 훗날 [[파스칼 삼각형]]으로 불리게 되었다.

중세 [[일본]]에는 [[벨 수]]가 최초로 등장하였다. 《[[겐지모노가타리]]》에서의 한 일화로부터 겐지코({{llang|ja|源氏香}})라는 놀이가 등장했는데,<ref name="Gardner">{{저널 인용
 | last = Gardner | first = Martin
 | doi = 10.1038/scientificamerican0578-24
 | journal = Scientific American
 | pages = 24–30
 | title = The Bells: versatile numbers that can count partitions of a set, primes and even rhymes
 | url = https://archive.org/details/sim_scientific-american_1978-05_238_5/page/n31 | volume = 238
 | year = 1978|언어=en}}</ref> 이 놀이에서는 5개의 향 가운데 어떤 것들이 같은 냄새의 향인지 구별하는 것이 목표이다. 가능한 해의 수는 5차 [[벨 수]] <math>B_5=52</math>가지다. 이 52가지의 [[집합의 분할]]은 겐지몬({{llang|ja|源氏紋}})이라는 문양으로 나타내어져, [[겐지모노가타리]]의 54개의 장의 각 표지에 표시되었다. (이 가운데 2개의 겐지몬은 벨 수와 관계없다.)

=== 근세 ===
[[블레즈 파스칼]](1623~1662)과 [[아이작 뉴턴]](1643~1727), [[야코프 베르누이]](1655~1705) 등은 조합론을 포함한 수학에 다방면으로 기여하였다. 파스칼은 1665년 사후에 출판된 저서 《산술 삼각형에 대하여》({{llang|fr|Traité du triangle arithmétique}})<ref>{{서적 인용|이름=Blaise|성=Pascal|저자링크=블레즈 파스칼|제목=Traite dv triangle arithmetiqve, avec qvelqves avtres petits traitez svr la mesme matiere|url=http://gallica.bnf.fr/ark:/12148/btv1b86262012|위치=[[파리 (프랑스)|파리]]|출판사= Chez Guillavme Desprez|언어=fr}}</ref>에서 (이미 중세부터 알려져 있던) [[파스칼 삼각형]]을 연구하였다. 1666년에 [[고트프리트 라이프니츠]]는 박사 학위 논문 《조합술에 대하여》({{llang|la|Dissertatio de arte combinatoria}})를 출판하였다.<ref>{{서적 인용|이름=Gottfredus Guilielmus |성=Leibnüzius|저자링크=고트프리트 라이프니츠|제목=Dissertatio de Arte Combinatoria, ''In qua'' Ex Arithmeticæ fundamentis ''Complicationum'' ac ''Tranſpoſitionum'' Doctrina novis præceptis exſtruitur, & uſus ambarum per univerſum ſcientiarum orbem oſtenditur; nova etiam Artis Meditandi, ''Seu'' Logicæ Inventionis ſemina ſparguntur. ''Præfixa est Synopſis totius Tractatus, & additamenti loco'' Demoſtratio Existentiæ Dei, ad Mathematicam certitudinem exacta|url=http://www.labirintoermetico.com/12ArsCombinatoria/Leibniz_G_W_Dissertatio_de_Arte_combinatoria.pdf|위치=[[라이프치히]]|출판사=
Apud Joh. Simon, Fickium et Joh. Polycarp. Seuboldum ''in Platea Nicolaea'', Literis Spörelianis|언어=la}}</ref>  이 책에서 라이프니츠는 "조합술"({{llang|la|ars combinatoria}})이라는 용어를 최초로 사용하였다. 라이프니츠는 이 책에서 다음과 같은 용어를 사용하였다.
:[[순열]]: {{llang|la|variātiō ōrdinis|바리아티오 오르디니스}} ("순서의 차이·변화")
:두 개의 원소로 구성된 [[조합]]: {{llang|la|combīnātiō|콤비나티오}} (이음)
:세 개의 원소로 구성된 [[조합]]: {{llang|la|conternātiō|콘테르나티오}} (세 개로 구성된 것, {{llang|la|con-}} + {{llang|la|ternī}} + {{llang|la|-ātiō}})
:(일반적인) [[조합]]: {{llang|la|complexiō|콤플렉시오}} (연결·연합·복합)

[[레온하르트 오일러]](1707~1783)는 [[오일러 수 (조합론)|오일러 수]]를 연구하였고, [[쾨니히스베르크의 다리 문제]]를 풀어 [[그래프 이론]]을 창시하였다.

19세기 말~20세기 초에 [[제임스 조지프 실베스터]]와 [[퍼시 알렉산더 맥메이헌]]은 대수적 조합론을 창시하였고, 이 시기에 [[그래프 이론]] 역시 급속히 발달하였다. 20세기 후반에 기하학적·위상수학적 기법들이 조합론에 사용되기 시작하였다.

== 같이 보기 ==
* [[조합론적 게임 이론]]
* [[이산수학]]
* [[계통학]]

== 각주 ==
{{각주}}
* {{서적 인용|저자=윤영진|제목=새로운 조합수학|출판사=교우사|날짜=2007|isbn=978-89-8172-379-8|url=http://www.kyowoo.co.kr/02_sub/view.php?p_idx=334|언어=ko}}
* {{서적 인용|저자=최설희|제목=알기 쉬운 조합수학|출판사=경문사|날짜=2004|isbn=978-89-7282-681-1|url=http://www.kyungmoon.com/shop_product/shop_pdt_view.php?p_idx=3537|언어=ko|access-date=2014-11-28|archive-date=2014-12-05|archive-url=https://web.archive.org/web/20141205074914/http://www.kyungmoon.com/shop_product/shop_pdt_view.php?p_idx=3537|url-status=}}
* {{서적 인용|저자=조성진|공저자=김한두|제목=조합론과 그래프이론|url=http://www.kyungmoon.com/shop_product/shop_pdt_view.php?p_idx=7260|출판사=경문사|날짜=2011|isbn=978-89-6105-432-4|언어=ko|access-date=2014-11-28|archive-date=2014-12-05|archive-url=https://web.archive.org/web/20141205074712/http://www.kyungmoon.com/shop_product/shop_pdt_view.php?p_idx=7260|url-status=}}
* {{서적 인용|이름=Louis|성=Comtet|제목=Advanced combinatorics: The art of finite and infinite expansions|출판사=Reidel Publishing Company|위치=Dordrecht|날짜=1974|zbl= 0283.05001|언어=en}}
* {{서적 인용 | last=Graham | first=Ronald L. | 공저자=[[도널드 커누스|Donald E. Knuth]], Oren Patashnik |title= Concrete mathematics: a foundation for computer science | 판=2판 | publisher=Addison-Wesley Professional| 날짜=1994 | isbn=0-201-55802-5 | mr=1397498|zbl=0836.00001|언어=en }}

== 외부 링크 ==
{{위키공용분류}}
* {{eom|title=Combinatorial analysis|first= V.N.|last=Sachkov}}
* {{매스월드|id=Combinatorics|title=Combinatorics}}
* {{매스월드|id=AlgebraicCombinatorics|title=Algebraic combinatorics}}
* {{수학노트|title=조합수학}}
* {{웹 인용|url=https://mathsci.kaist.ac.kr/~sangil/ko/2015/kmo-%EC%97%AC%EB%A6%84%ED%95%99%EA%B5%90%EA%B2%A8%EC%9A%B8%ED%95%99%EA%B5%90-%EA%B0%95%EC%9D%98%EB%85%B8%ED%8A%B8/|저자=엄상일|제목=KMO 여름학교/겨울학교 강의노트|날짜=2015-01-16|언어=ko}}

{{수학 분야}}

{{전거 통제}}

[[분류:이산수학]]
[[분류:조합론| ]]