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정도의 문제들은 보통 다음과 같은 용어로 묘사된다. {| class="wikitable" |+ 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정도의 해는 다음과 같다. {| class="wikitable" |+ 12정도의 공식 |- ! 동치 관계 ╲ 함수 조건 ! (없음) ! 단사 함수 ! 전사 함수 |- ! 함수 일치 | x^n | x^{\underline n} | \textstyle x!\\n\atop x}\\} |- ! 정의역의 순열을 무시 | \textstyle x^{\overline n}/n!=\binom{x+n-1}n | \textstyle\binom xn | \textstyle\binom{n-1}{n-x} |- ! 공역의 순열을 무시 | B_n | [n\le x] | \textstyle\\n\atop x}\\} |- ! 정의역과 공역의 순열을 무시 | p_x(n+x) | [n\le x] | p_x(n) |} 여기서 사용한 기호는 다음과 같다. * 계승 *:x!=x(x-1)\cdots2\cdot1 * 하강 포흐하머 기호 *:x^{\underline n}=x!/(x-n)! * 상승 포흐하머 기호 *:x^{\overline n}=(x+n-1)!/(x-1)! * 이항 계수 *:\binom xn=\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)언어=en에서 "12정도"라는 이름으로 대중화시켰다. "12정도"(Twelvefold Way)라는 이름은 불교의 팔정도(八正道) 및 입자물리학의 팔정도(Eightfold Way)에 빗댄 것이며, 조엘 스펜서(Joel Spencer)가 명명하였다.