12정도

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

정의

두 개의 집합 $N$과 $X$가 있다고 하고, 그 크기가 각각

$|N|=n$

$|X|=x$

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

• 아무런 조건이 없을 경우, 함수 집합 $\operatorname {Fun} (N,X)$
• 단사 함수일 경우, 함수 집합 $\operatorname {Inj} (N,X)$
• 전사 함수일 경우, 함수 집합 $\operatorname {Surj} (N,X)$

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

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

• 함수의 일치 $f\sim g\iff f=g$
• 정의역 $N$의 순열을 무시한 동치. 즉, $f\sim g\iff \exists \sigma _{N}\in \operatorname {Sym} (N)\colon f\circ \sigma _{N}=g\}$이다.
• 공역 $X$의 순열을 무시한 동치. 즉, $f\sim g\iff \exists \sigma _{X}\in \operatorname {Sym} (X)\colon \sigma _{X}\circ f=g\}$이다.
• 정의역 $N$의 순열과 공역 $X$의 순열을 무시한 동치. 즉, $f\sim g\iff \exists \sigma _{N}\in \operatorname {Sym} (N),\sigma _{X}\in \operatorname {Sym} (X)\colon \colon \sigma _{X}\circ f\circ \sigma _{N}=g\}$이다.

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

해석

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

12정도의 공식

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

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

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

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

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

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

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

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

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

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

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

해

정의역의 크기가 $|N|=n$, 공역의 크기가 $|X|=x$라고 하면, 12정도의 해는 다음과 같다.

12정도의 공식

동치 관계 ╲ 함수 조건	(없음)	단사 함수	전사 함수
함수 일치	$x^{n}$	$x^{\underline {n}}$	$\textstyle x!\{{n \atop x}\}$
정의역의 순열을 무시	$\textstyle x^{\overline {n}}/n!={\binom {x+n-1}{n}}$	$\textstyle {\binom {x}{n}}$	$\textstyle {\binom {n-1}{n-x}}$
공역의 순열을 무시	$B_{n}$	$[n\leq x]$	$\textstyle \{{n \atop x}\}$
정의역과 공역의 순열을 무시	$p_{x}(n+x)$	$[n\leq x]$	$p_{x}(n)$

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

• 계승

  $x!=x(x-1)\cdots 2\cdot 1$

• 하강 포흐하머 기호

  $x^{\underline {n}}=x!/(x-n)!$

• 상승 포흐하머 기호

  $x^{\overline {n}}=(x+n-1)!/(x-1)!$

• 이항 계수

  ${\binom {x}{n}}={\frac {x!}{n!(x-n)!}}=x^{\underline {n}}/n!$

• 제2종 스털링 수

  $\left\{{x \atop n}\right\}$

• 아이버슨 괄호. 주어진 조건이 참이면 1, 거짓이면 0이다.

  $[P]={\begin{cases}1&P\\0&\lnot P\end{cases}}$

• 분할수 $p_{x}(n)$는 자연수 $n$을 $x$개의 조각으로 분할하는 경우의 수이다.
• 벨 수

  $B_{n}=\sum _{k=0}^{x}\left\{{n \atop k}\right\}$

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

${\binom {n-1}{n-x}}={\binom {n-1}{x-1}}$

이다. 다만, $n=x=0$일 경우

${\binom {n-1}{n-x}}={\binom {-1}{0}}=1$

${\binom {n-1}{x-1}}={\binom {-1}{-1}}=0$

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

역사

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

참고 문헌

• Proctor, Robert A. “Let's Expand Rota's Twelvefold Way For Counting Partitions!” (영어). arXiv:math/0606404. Bibcode:2006math......6404P. 

외부 링크

• Drake, Dan (2009년 3월 9일). “Stanley’s Twelvefold Way” (PDF) (영어). 2015년 7월 24일에 원본 문서 (PDF)에서 보존된 문서. 2015년 10월 21일에 확인함. 
• Cook, John D. (2009년 8월 31일). “Richard Stanley’s Twelvefold Way” (PDF) (영어). 
• Rasmussen, Jan Marthedal (2008년 12월 26일). “Twelve Ways of Counting”. 《janmr blog》 (영어). 2016년 3월 4일에 원본 문서에서 보존된 문서. 2015년 10월 21일에 확인함.