12정도

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

정의

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

${\displaystyle |N|=n}$

${\displaystyle |X|=x}$

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

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

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

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

• 함수의 일치 ${\displaystyle f\sim g\iff f=g}$
• 정의역 ${\displaystyle N}$의 순열을 무시한 동치. 즉, ${\displaystyle f\sim g\iff \exists \sigma _{N}\in \operatorname {Sym} (N)\colon f\circ \sigma _{N}=g\}}$이다.
• 공역 ${\displaystyle X}$의 순열을 무시한 동치. 즉, ${\displaystyle f\sim g\iff \exists \sigma _{X}\in \operatorname {Sym} (X)\colon \sigma _{X}\circ f=g\}}$이다.
• 정의역 ${\displaystyle N}$의 순열과 공역 ${\displaystyle X}$의 순열을 무시한 동치. 즉, ${\displaystyle 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정도의 공식

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

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

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

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

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

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

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

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

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

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

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

해

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

12정도의 공식

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

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

• 계승

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

• 하강 포흐하머 기호

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

• 상승 포흐하머 기호

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

• 이항 계수

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

• 제2종 스털링 수

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

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

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

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

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

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

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

이다. 다만, ${\displaystyle n=x=0}$일 경우

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

${\displaystyle {\binom {n-1}{x-1}}={\binom {-1}{-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. 

• 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일에 확인함.