대수 · 개념 허브깊이 읽기

조합론

Combinatorics

AD 165417세기 프랑스 (파스칼·페르마)

개념

세는 법의 학문. "n개에서 r개를 고르는 방법은?"이라는 단순 질문이 확률·암호·통계물리·컴퓨터 알고리즘의 기본 도구가 되었다.

한 호흡으로 이해하기

"몇 가지 방법이 있나?"를 중복 없이 세는 기술. 카드 패, 자리 배치, 비트 문자열은 각각 다른 제약을 조합론의 원리로 모델링한다. 조합론은 확률·암호·알고리즘 분석에 중요한 도구를 제공하며, 파스칼의 삼각형은 이항계수를 읽는 대표적인 구조다.

한눈에 보기

n

계수들 (k=0,1,2,...)

0

1

1

1 1

2

1 2 1

3

1 3 3 1

4

1 4 6 4 1

5

1 5 10 10 5 1

6

1 6 15 20 15 6 1

파스칼의 삼각형 — n번째 행이 (a+b)ⁿ의 전개 계수.

핵심 식

(nk)=n!k!(n−k)!\binom{n}{k} = \dfrac{n!}{k!(n-k)!}

n 중 k개 선택 = nCk

풀이 예제

  1. 1

    Q.5명 중 2명 선택

  2. 2

    Q.8비트 문자열 가짓수

핵심 순간

BC 300

인도 — 순열의 첫 사용

핀갈라의 운율 분석에서 이항계수가 처음 등장. 피보나치 수도 이때 먼저 등장.

AD 1654

파스칼의 삼각형

파스칼이 삼각형의 패턴으로 이항계수를 정리. 확률론의 출발과 동시.

AD 1750

오일러 — 7개 다리 문제

쾨니히스베르크의 다리 문제 해결로 그래프 이론과 조합론이 결합.

AD 1989

에르되시 — 공동저자 네트워크

평생 1500편의 논문, 511명의 공저자. 에르되시 수가 수학자 사회의 친밀도 척도가 됨.

오늘날의 응용

확률 계산, 암호 키 공간 분석, RAID 디스크의 패리티, 코딩 이론, 알고리즘 복잡도 분석, 통계물리(엔트로피).

MathVoyage 너머로

불러오는 중…