조합

Combinatorics
조합성과 혼동하지 마십시오.
"Combinatory"는 여기서 리다이렉트됩니다.컴퓨터 과학의 조합 논리에 대해서는 조합 논리를 참조하십시오.

조합론은 주로 계산과 관련된 수학 분야로, 결과를 얻기 위한 수단과 목적, 그리고 유한 구조의 특정한 특성들을 모두 얻습니다.그것은 수학의 많은 다른 분야와 밀접하게 관련되어 있고 논리학에서 통계 물리학, 진화 생물학에서 컴퓨터 과학에 이르기까지 많은 응용 분야를 가지고 있다.

조합론의 전체 범위는 보편적으로 [1]합의되지 않았다.H.J. 라이저에 따르면, 그 주제의 정의는 너무 많은 수학적인 [2]부분들을 가로지르기 때문에 어렵다.영역이 대처하는 문제의 유형으로 설명될 수 있는 한 조합론은 다음과 같습니다.

  • 유한 시스템과 관련된 매우 일반적인 의미에서 배열 또는 구성이라고도 하는 특정 구조물의 열거(개요)
  • 특정 기준을 충족하는 구조의 존재,
  • 이러한 구조물의 건설, 아마도 여러 가지 면에서, 그리고
  • 최적화: "최대", "최고", "최고"의 구조 또는 솔루션을 찾거나 다른 최적성 기준을 충족합니다.

레온 미르스키는 다음과 같이 말했다: "공통학은 공통점을 가지고 있지만 그들의 목적, 방법, 그리고 그들이 [3]도달한 일관성의 정도에 있어 광범위하게 다른 일련의 연계된 연구들이다."조합론을 정의하는 한 가지 방법은 아마도 그것의 세분화를 그들의 문제와 기술로 기술하는 것입니다.이것은 아래에 사용되는 접근법입니다.그러나 조합론 [4]산하에 일부 주제를 포함하거나 포함하지 않는 데에는 순전히 역사적 이유도 있다.주로 유한 시스템과 관련이 있지만, 일부 조합 질문과 기법은 무한(구체적으로 셀 수 있는) 그러나 이산적인 설정으로 확장될 수 있습니다.

조합론은 다양한 문제를 다루는 것으로 잘 알려져 있습니다.조합 문제는 순수 수학의 많은 영역, 특히 대수학, 확률론, 위상학,[5] 기하학 그리고 그것의 많은 응용 영역에서 발생한다.많은 조합 질문은 역사적으로 고립되어 검토되어 왔으며, 일부 수학적 맥락에서 발생하는 문제에 대한 임시 해결책을 제시하였다.그러나 20세기 후반에 강력하고 일반적인 이론적 방법들이 개발되어 조합론을 수학의 독립적인 한 분야로 만들었다.[6]조합론의 가장 오래되고 가장 접근하기 쉬운 부분 중 하나는 그래프 이론이며, 그래프 이론은 그 자체로 다른 영역과 수많은 자연적 연관성을 가지고 있다.콤비네이터론은 알고리즘 분석에서 공식과 추정치를 얻기 위해 컴퓨터 과학에서 자주 사용됩니다.

조합론을 연구하는 수학자는 A라고 불립니다.

역사

그래프 이론에서 가장 초기의 중요하지 않은 결과 중 하나인 변화 호출음(6개의 벨 포함)의 예입니다.
주요 기사:조합론의 역사

기본적인 조합 개념과 열거적 결과는 고대 세계 곳곳에서 나타났다.기원전 6세기 인도의 고대 의사인 스슈루타는 스슈루타 삼히타에서 6가지 맛으로 63가지 조합이 만들어지고, 한 번에 두 가지 맛 등으로 모든 가능성을6 계산한다고 주장한다.그리스의 역사학자 플루타르코스는 크리시포스(기원전 3세기)와 히파르코스(기원전 2세기) 사이의 다소 미묘한 열거적 문제에 대한 논쟁을 논의하는데, 이것은 나중에 슈뢰더-히파르코스 [7][8][9]숫자와 관련이 있는 것으로 나타났다.일찍이, 오스트마치온에서 아르키메데스(기원전 [10]3세기)는 타일링 퍼즐의 구성 수를 고려했을지도 모르지만, 조합의 관심은 아폴로니우스의 [11][12]잃어버린 작품에서 존재했을지도 모른다.

중세 시대에는 조합론이 주로 유럽 문명 밖에서 계속 연구되었다.인도의 수학자 마하보라(Mahavcra, 850년경)는 순열과 [13][14]조합의 수에 대한 공식을 제공했고, 이러한 공식은 서기 [15]6세기부터 인도 수학자들에게 친숙했을지도 모른다.철학자이자 천문학자인 랍비 아브라함 이븐 에즈라는 이항 계수의 대칭성을 확립했고, 반면 닫힌 공식은 나중에 [16]1321년에 탈무디스트이자 수학자인 레비 벤 거슨에 의해 얻어졌습니다.이항 계수들 사이의 관계를 보여주는 그래픽 도표인 산술 삼각형은 10세기까지 거슬러 올라가는 수학자들에 의해 제시되었고, 결국 파스칼의 삼각형으로 알려지게 되었다.나중에 중세 영국에서, 캄파놀로지는 [17][18]순열에 대한 특정 케일리 그래프에서 현재 해밀턴 순환으로 알려진 것의 예를 제공했습니다.

르네상스 기간 동안, 수학과 과학의 나머지 부분과 함께, 조합론은 재탄생을 누렸다.파스칼, 뉴턴, 야콥 베르누이, 오일러의 작품은 신흥 분야의 기초가 되었다.현대에는 J.J. 실베스터와 퍼시 맥마흔의 작품들이 열거적, 대수적 조합론의 토대를 마련하는데 도움을 주었다.그래프 이론은 특히 4가지 색상의 문제와 관련하여 동시에 관심이 증가했다.

20세기 후반, 조합학은 빠른 성장을 누렸고, 이것은 [19]그 주제에 대한 수십 개의 새로운 저널과 컨퍼런스를 설립하게 되었다.부분적으로, 성장은 대수학에서 확률, 함수 분석에서 숫자 이론 등에 이르는 다른 분야로의 새로운 연결과 응용에 의해 촉진되었다.이러한 연결은 수학과 이론 컴퓨터 과학의 일부와 조합론 사이의 경계를 허물었지만, 동시에 부분적인 분야 분열을 초래했다.

조합론의 접근법 및 하위 필드

열거 조합학

3개의 꼭지점에 5개의 이진 트리, 카탈로니아 숫자의 예입니다.
주요 기사:열거 조합학

열거형 조합론은 조합론의 가장 고전적인 영역이며 특정 조합 객체의 수를 세는 데 집중한다.집합의 요소 수를 세는 것은 다소 광범위한 수학 문제이지만, 응용 프로그램에서 발생하는 문제의 대부분은 비교적 단순한 조합 기술을 가지고 있습니다.피보나치 숫자는 열거형 조합학 문제의 기본적인 예입니다.12배 방법은 순열, 조합 및 파티션을 계산하기 위한 통합 프레임워크를 제공합니다.

분석 조합론

주요 기사:분석 조합론

분석 조합론은 복잡한 분석과 확률 이론의 도구를 사용한 조합 구조의 열거와 관련이 있습니다.결과를 설명하기 위해 명시적 조합 공식을 사용하고 함수를 생성하는 열거형 조합론과 대조적으로, 분석 조합학은 점근 공식을 얻는 것을 목표로 한다.

분할 이론

평면 파티션
주요 기사: 파티션 이론

분할 이론은 정수 분할과 관련된 다양한 열거 및 점근 문제를 연구하며, q-계열, 특수 함수 및 직교 다항식과 밀접하게 관련되어 있습니다.원래 수 이론과 분석의 일부였지만, 지금은 조합론이나 독립 분야로 간주됩니다.그것은 분석 및 분석 수 이론에서 생물적 접근법과 다양한 도구를 통합하고 통계 역학과의 연관성을 가지고 있다.

그래프 이론

피터슨 그래프
주요 기사 : 그래프 이론

그래프는 조합론의 기본 객체입니다.그래프 이론의 고려사항은 열거(예: k개의 모서리를 가진 n개의 정점에 대한 그래프 수)에서 기존 구조(예: 해밀턴 주기)와 대수적 표현(예: 그래프 G와 두 개의 숫자 x와 y가 주어졌을 때, 투테 다항식G T(x,y)는 조합 해석을 가지고 있는가)까지 다양하다.그래프 이론과 조합론 사이에는 매우 강한 연관성이 있지만, 그것들은 때때로 별개의 [20]과목으로 생각됩니다.조합 방법은 많은 그래프 이론 문제에 적용되지만, 두 가지 원칙은 일반적으로 다른 유형의 문제에 대한 해결책을 찾는 데 사용됩니다.

디자인 이론

주요 기사:조합 설계

디자인 이론은 특정 교차 특성을 가진 하위 집합 집합의 집합인 조합 설계에 대한 연구입니다.블록 설계는 특수 유형의 조합 설계입니다.이 영역은 1850년에 제안된 커크만의 여학생 문제처럼 조합론의 가장 오래된 부분 중 하나입니다.이 문제의 해결책은 Steiner 시스템의 특수한 경우로, 시스템은 유한 단순 그룹의 분류에 중요한 역할을 한다.그 영역은 부호화 이론과 기하학적 조합론과 더 많은 연관성을 가지고 있다.

유한 기하학

주요 기사:유한 기하학

유한 기하학은 한정된 수의 점만을 가진 기하학적 시스템을 연구하는 학문이다.연속 기하학(유클리드 평면, 실제 투영 공간 등)에서 발견되는 것과 유사하지만 조합적으로 정의된 구조가 주요 연구 항목이다.이 영역은 디자인 이론의 풍부한 예시를 제공합니다.이산 지오메트리(콤비노토리얼 지오메트리)와 혼동해서는 안 됩니다.

순서론

포함순으로 정렬된 {x,y,z}의 파워셋에 대한 Hasse 다이어그램입니다.
주요 기사:순서론

순서론은 유한 집합과 무한 집합을 모두 연구하는 학문이다.부분 차수의 다양한 예는 대수학, 기하학, 수 이론 그리고 조합론과 그래프 이론 전반에 걸쳐 나타난다.주목할 만한 등급과 부분 순서의 예로는 격자와 부울 대수가 있다.

매트로이드 이론

주요 기사 : 매트로이드 이론

매트로이드 이론은 기하학의 일부를 추상화한다.선형 의존 관계에서 특정 계수에 의존하지 않는 벡터 공간의 벡터 집합(일반적으로 유한 집합)의 특성을 연구합니다.구조뿐만 아니라 열거적 특성도 매트로이드 이론에 속합니다.매트로이드 이론은 하슬러 휘트니에 의해 도입되었고 질서 이론의 일부로 연구되었다.그것은 이제 조합론의 다른 부분들과 많은 연관성을 가진 독립적인 연구 분야이다.

극단적 조합론

주요 기사: Extremal combinatorics

극단적 조합론은 집합 시스템에 대한 극단적 질문을 연구합니다.이 경우에 다루는 질문의 유형은 특정 속성을 만족시키는 가능한 가장 큰 그래프에 관한 것입니다.예를 들어, 2n개의 꼭지점에서 삼각형이 없는 가장 큰 그래프는 완전한 이분 그래프n,n K입니다.종종 극단적 답변 f(n)를 정확히 찾는 것조차 너무 어려우며 점근적 추정치만 제시할 수 있다.

램지 이론은 극단적 조합론의 또 다른 부분이다.충분히 큰 설정에는 어떤 종류의 순서가 포함되어 있다고 기술되어 있습니다.그것은 비둘기 구멍 원리의 발전된 일반화이다.

확률론적 조합론

정사각형 그리드 그래프에서의 자기 회피 보행.
주요 기사 : 확률론적 방법

확률론적 조합론에서 질문은 다음과 같은 유형이다: 랜덤 그래프와 같은 랜덤 이산 객체에 대한 특정 특성의 확률은?예를 들어, 랜덤 그래프에서 삼각형의 평균 수는 얼마입니까?확률론적 방법은 단순히 그러한 속성을 가진 개체를 무작위로 선택할 확률이 0보다 크다는 것을 관찰함으로써 특정한 규정된 속성을 가진 조합 객체의 존재를 결정하기 위해 사용된다(명시적인 예는 찾기 어려울 수 있음).이 접근법(흔히 확률론적 방법이라고 함)은 극단적 조합론과 그래프 이론의 적용에서 매우 효과적이었다.밀접하게 관련된 영역은 유한 마르코프 사슬, 특히 조합 객체에 대한 연구이다.여기서도 확률론적 도구를 사용하여 혼합 시간을 추정한다.

종종 이 주제에 대한 선구적인 연구를 한 Paul Erdos와 관련이 있는 확률론적 조합론은 전통적으로 조합론의 다른 부분에서 문제를 연구하기 위한 도구 세트로 여겨졌다.그러나 고전 확률, 가산수 이론, 확률론적 수 이론뿐만 아니라 컴퓨터 과학에서 알고리즘을 분석하는 애플리케이션의 성장과 함께, 이 영역은 최근에 조합론의 독립적인 분야로 성장했습니다.

대수적 조합론

파티션의 젊은 다이어그램(5, 4, 1)
주요 기사:대수적 조합론

대수적 조합론은 추상대수의 방법, 특히 군 이론과 표현 이론을 다양한 조합 맥락에서 사용하는 수학의 한 분야이며, 반대로, 대수의 문제에 조합 기술을 적용한다.대수적 조합론은 주제와 기술 모두에서 그 범위를 지속적으로 확장하고 있으며, 조합과 대수적 방법의 상호작용이 특히 강하고 중요한 수학 분야로 볼 수 있다.

단어 조합

Thue-Morse 무한 단어 구성.
주요 기사:단어 조합

단어 조합학은 형식적인 언어를 다룬다.그것은 수학의 여러 분야 안에서 독립적으로 발생했는데, 여기에는 수 이론, 군 이론, 확률 등이 포함된다.열거 조합론, 프랙탈 분석, 이론 컴퓨터 과학, 오토마타 이론, 언어학 등에 응용된다.많은 응용 프로그램이 새로워졌지만, 형식 문법 클래스의 고전적인 촘스키-슈첸베르거 계층은 아마도 이 분야에서 가장 잘 알려진 결과일 것이다.

기하학적 조합론

20면체.
주요 기사:기하학적 조합론

기하학적 조합론은 볼록 및 이산 기하학, 특히 다면체 조합론과 관련이 있다.예를 들어 볼록 폴리토프가 각 차원의 몇 개의 면을 가질 수 있는지 물어봅니다.예를 들어 볼록 폴리톱의 강성에 대한 코시 정리처럼 폴리톱의 미터법 특성도 중요한 역할을 한다.퍼무토헤드라, 동심체 및 비르호프 폴리토피와 같은 특수한 폴리토피도 고려된다.조합 기하학은 이산 기하학의 과거 이름입니다.

위상 조합론

목걸이를 두 컷으로 쪼개다.
주요 기사:위상 조합론

위상학에서의 개념과 방법의 조합적 유추는 그래프 색칠, 균등분할, 분할, 부분 순서 집합, 결정 나무, 목걸이 문제 및 이산 모스 이론을 연구하는데 사용된다.대수위상의 오래된 명칭인 조합위상과 혼동해서는 안 된다.

산술적 조합론

주요 기사:산술적 조합론

산술적 조합론은 수 이론, 조합론, 에르고드 이론, 그리고 조화 해석 사이의 상호작용에서 생겨났다.산술 연산(더하기, 빼기, 곱하기 및 나눗셈)과 관련된 조합 추정치에 대한 것입니다.가법수론(가법 조합론이라고도 함)은 덧셈과 뺄셈의 연산만 수반하는 특수한 경우를 말합니다.산술 조합학에서 중요한 기술 중 하나는 동적 시스템의 에르고드 이론이다.

부정 조합론

주요 기사:부정 조합론

무한 조합론 또는 조합 집합론은 조합론에서 아이디어를 무한 집합으로 확장한 것입니다.그것은 집합론의 일부이며, 수학 논리의 영역이지만 집합론과 극단적 조합론 양쪽에서 나온 도구와 아이디어를 사용한다.

Gian-Carlo Rota는 계수와 측정 사이에 많은 유사점이[21] 있기 때문에 기하학적 확률을 설명하기 위해 연속 결합학이라는 이름을 사용했다.

관련 필드

키스구는 부호화 이론과 이산 기하학 양쪽에 연결되어 있다.

조합 최적화

조합 최적화는 이산 및 조합 객체에 대한 최적화에 대한 연구입니다.그것은 조합론과 그래프 이론의 일부로 시작되었지만, 지금은 연산 연구, 알고리즘 이론, 계산 복잡도 이론과 관련된 응용 수학과 컴퓨터 과학의 한 분야로 여겨진다.

부호화 이론

코딩 이론은 오류 수정 코드의 초기 조합 구성과 함께 디자인 이론의 일부로 시작되었습니다.주제의 주요 아이디어는 효율적이고 신뢰할 수 있는 데이터 전송 방법을 설계하는 것입니다.그것은 이제 정보 이론의 일부인 거대한 연구 분야이다.

이산 및 계산 지오메트리

이산 기하학(조합 기하학이라고도 함)은 또한 볼록 폴리토프와 키스 숫자에 대한 초기 결과와 함께 조합론의 일부로 시작되었다.이산기하학이 계산기하학에 적용되면서, 이 두 분야는 부분적으로 병합되어 별도의 연구 분야가 되었다.기하학적 및 위상학적 조합론에는 많은 연관성이 남아 있으며, 그 자체는 초기 이산 기하학의 성장에서 벗어난 것으로 볼 수 있습니다.

조합 및 동적 시스템

동적 시스템의 조합 측면도 새로운 분야입니다.여기서 동적 시스템은 조합 객체에 정의할 수 있습니다.그래프 다이내믹시스템의 예를 참조해 주세요.

조합과 물리

조합론과 물리학, 특히 통계 물리학 사이의 상호작용이 증가하고 있습니다.예로는 Ising 모델의 정확한 해와 한편으로는 Potts 모델 간의 연결, 그리고 다른 한편으로는 색다항식과 Tutte 다항식이 있습니다.

「 」를 참조해 주세요.

메모들

  1. ^ Pak, Igor. "What is Combinatorics?". Retrieved 1 November 2017.
  2. ^ 라이저 1963, 페이지 2
  3. ^ Mirsky, Leon (1979), "Book Review" (PDF), Bulletin of the American Mathematical Society, New Series, 1: 380–388, doi:10.1090/S0273-0979-1979-14606-8
  4. ^ Rota, Gian Carlo (1969). Discrete Thoughts. Birkhaüser. p. 50. ... combinatorial theory has been the mother of several of the more active branches of today's mathematics, which have become independent ... . The typical ... case of this is algebraic topology (formerly known as combinatorial topology)
  5. ^ 비외르너와 스탠리, 2페이지
  6. ^ Lovász, László (1979). Combinatorial Problems and Exercises. North-Holland. ISBN 9780821842621. In my opinion, combinatorics is now growing out of this early stage.
  7. ^ Acerbi, F. (2003). "On the shoulders of Hipparchus". Archive for History of Exact Sciences. 57 (6): 465–502. doi:10.1007/s00407-003-0067-0. S2CID 122758966.
  8. ^ Stanley, Richard P.; "히파르쿠스, 플루타르쿠스, 슈뢰더, 호프", 미국 수학 월간 104호(1997), 제4, 344–350호.
  9. ^ Habsieger, Laurent; Kazarian, Maxim; Lando, Sergei (1998). "On the Second Number of Plutarch". The American Mathematical Monthly. 105 (5): 446. doi:10.1080/00029890.1998.12004906.
  10. ^ Netz, R.; Acerbi, F.; Wilson, N. "Towards a reconstruction of Archimedes' Stomachion". Sciamvs. 5: 67–99.
  11. ^ Hogendijk, Jan P. (1986). "Arabic Traces of Lost Works of Apollonius". Archive for History of Exact Sciences. 35 (3): 187–253. doi:10.1007/BF00357307. ISSN 0003-9519. JSTOR 41133783. S2CID 121613986.
  12. ^ Huxley, G. (1967). "Okytokion". Greek, Roman, and Byzantine Studies. 8 (3): 203.
  13. ^ O'Connor, John J.; Robertson, Edmund F., "Combinatorics", MacTutor History of Mathematics archive, University of St Andrews
  14. ^ Puttaswamy, Tumkur K. (2000). "The Mathematical Accomplishments of Ancient Indian Mathematicians". In Selin, Helaine (ed.). Mathematics Across Cultures: The History of Non-Western Mathematics. Netherlands: Kluwer Academic Publishers. p. 417. ISBN 978-1-4020-0260-1.
  15. ^ Biggs, Norman L. (1979). "The Roots of Combinatorics". Historia Mathematica. 6 (2): 109–136. doi:10.1016/0315-0860(79)90074-0.
  16. ^ Maistrov, L.E. (1974), Probability Theory: A Historical Sketch, Academic Press, p. 35, ISBN 978-1-4832-1863-2. (1967년 러시아어판 번역)
  17. ^ White, Arthur T. (1987). "Ringing the Cosets". The American Mathematical Monthly. 94 (8): 721–746. doi:10.1080/00029890.1987.12000711.
  18. ^ White, Arthur T. (1996). "Fabian Stedman: The First Group Theorist?". The American Mathematical Monthly. 103 (9): 771–778. doi:10.1080/00029890.1996.12004816.
  19. ^ 조합론과 그래프 이론 저널 참조
  20. ^ Sanders, Daniel P., Wayback Machine에서 2008-12-31에 아카이브된2자리 MSC 비교
  21. ^ 연속적이고 불한한 조합론

레퍼런스

외부 링크