12정도

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기

조합론에서, 12정도(十二正道, 영어: the Twelvefold Way)는 자주 등장하는 열거 문제를 12가지로 분류하는 방법이다. 이를 통하여, 순열 · 조합 · 이항 계수 · 스털링 수 · 벨 수 · 분할수와 같은 개념들을 체계적으로 다룰 수 있다.

정의[편집]

두 개의 집합 가 있다고 하고, 그 크기가 각각

라고 하자. 그렇다면, 정의역으로, 공역으로 하는 함수 가운데, 다음과 같은 조건을 부여한 집합을 생각할 수 있다.

  • 아무런 조건이 없을 경우, 함수 집합
  • 단사 함수일 경우, 함수 집합
  • 전사 함수일 경우, 함수 집합

(전단사 함수의 조건을 부여하는 것은 자명하다.)

이 세 개의 집합에, 다음과 같이 4가지의 동치 관계 를 줄 수 있다. 여기서 는 집합 위의 순열들의 집합(대칭군)이다.

  • 함수의 일치
  • 정의역 순열을 무시한 동치. 즉, 이다.
  • 공역 순열을 무시한 동치. 즉, 이다.
  • 정의역 순열공역 순열을 무시한 동치. 즉, 이다.

그렇다면, 이 3개의 함수 집합에 4개의 동치 관계를 부여하였을 때 존재하는 동치류의 수에 대하여 물을 수 있다. 즉, 3×4=12개의 열거 문제가 존재한다. 이를 12정도라고 한다.

해석[편집]

12정도의 문제들은 보통 다음과 같은 용어로 묘사된다.

12정도의 공식
동치 관계 ╲ 함수 조건 (없음) 단사 함수 전사 함수
함수 일치 의 원소들의 길이 의 열 의 원소들의 크기 순열
정의역의 순열을 무시 의 크기 의 부분 중복집합 의 크기 부분 집합
공역의 순열을 무시 집합 의, 개 이하의 부분 집합들로의 분할 집합 의, 개의 부분 집합들로의 분할
정의역과 공역의 순열을 무시 자연수 의, 개 이하의 양의 정수들로의 분할 자연수 의, 개의 양의 정수들로의 분할

이들은 개의 공들을 개의 통들에 넣는 문제로 해석할 수 있다. 이 경우, 함수에 대한 조건은 통에 들어가는 공의 수에 대한 제약이다. 즉, 다음과 같은 조건을 부여할 수 있다.

  • 조건 없음: 각 통에 임의의 수의 공이 들어간다.
  • 단사 함수: 각 통에 최대 1개의 공이 들어간다.
  • 전사 함수: 각 통에 1개 이상의 공이 들어간다.

함수 집합 위의 동치 관계는 공이나 통에 부여된 번호(또는 색칠 따위)의 유무에 대응한다.

  • 함수 일치: 각 공은 번호 1~이 매겨져 구별할 수 있으며, 각 통도 마찬가지로 번호 1~가 매겨져 구별할 수 있다.
  • 정의역의 순열을 무시: 통들은 번호가 매겨져 구별할 수 있지만, 공들은 구별할 수 없다.
  • 공역의 순열을 무시: 통들은 구별할 수 없지만, 공들은 번호가 매겨져 구별할 수 있다.
  • 정의역과 공역의 순열을 무시: 공들과 통들 모두 서로 구별할 수 없다.

12정도는 통계역학적으로도 생각할 수 있다. 즉, 개의 입자가 개의 상태에 속한다고 하자. 이 경우, 함수에 대한 조건은 입자들이 따르는 통계이다.

  • 조건 없음: 각 상태에 임의의 수의 입자들이 존재할 수 있다 (보스 통계).
  • 단사 함수: 각 상태에 최대 1개의 입자가 존재할 수 있다 (페르미온 통계).
  • 전사 함수: 각 상태에 적어도 1개 이상의 입자가 존재하여야 한다.

정의역의 수열의 무시 여부는 입자의 구별 가능성에 대응한다.

  • 정의역의 순열을 무시: 입자가 양자 입자여서 서로 구분할 수 없다.
  • 정의역의 순열을 무시하지 않음: 입자가 고전적 입자여서 구분 가능하다.

마찬가지로, 공역의 수열의 무시 여부는 다음과 같이 해석할 수 있다.

  • 공역의 순열을 무시하지 않음: 각 상태들 역시 에너지 및 기타 양자수가 달라 구분 가능하다.
  • 공역의 순열을 무시: 입자의 가능한 상태들이 대칭으로 인해 겹침이 일어나며, 계 전체에 대칭의 작용은 게이지 대칭으로 여겨 구분하지 않는다.

[편집]

정의역의 크기가 , 공역의 크기가 라고 하면, 12정도의 해는 다음과 같다.

12정도의 공식
동치 관계 ╲ 함수 조건 (없음) 단사 함수 전사 함수
함수 일치
정의역의 순열을 무시
공역의 순열을 무시
정의역과 공역의 순열을 무시

여기서 사용한 기호는 다음과 같다.

  • 계승
  • 하강 포흐하머 기호
  • 상승 포흐하머 기호
  • 이항 계수
  • 제2종 스털링 수
  • 아이버슨 괄호. 주어진 조건이 참이면 1, 거짓이면 0이다.
  • 분할수 는 자연수 개의 조각으로 분할하는 경우의 수이다.
  • 벨 수

여기서 전사 함수를 정의역의 순열을 무시하여 세는 것에서, 만약 이거나 일 경우

이다. 다만, 일 경우

이므로, 전자가 맞는 표현이다.

역사[편집]

조합론의 열거 문제들을 12가지로 분류하는 것은 잔카를로 로타가 최초였다. 이후 로타의 제자인 리처드 피터 스탠리(영어: Richard Peter Stanley)가 1986년에 출판된 교재 《열거 조합론》(영어: Enumerative Combinatorics)[1] 에서 "12정도"라는 이름으로 대중화시켰다. "12정도"(영어: Twelvefold Way)라는 이름은 불교의 팔정도(八正道) 및 입자물리학팔정도(영어: Eightfold Way)에 빗댄 것이며, 조엘 스펜서(영어: Joel Spencer)가 명명하였다.

참고 문헌[편집]

  1. Stanley, Richard P. (1986). 《Enumerative Combinatorics. Volume 1》 (영어) 1판. Wadsworth & Brooks/Cole. 

외부 링크[편집]