주 메뉴 열기

조합론에서, 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. 

외부 링크편집