12정도 문서 원본 보기

{{위키데이터 속성 추적}}
[[조합론]]에서 '''12정도'''(十二正道, {{llang|en|the Twelvefold Way}})는 자주 등장하는 열거 문제를 12가지로 분류하는 방법이다. 이를 통하여, [[순열]] · [[조합]] · [[이항 계수]] · [[스털링 수]] · [[벨 수]] · [[분할수]]와 같은 개념들을 체계적으로 다룰 수 있다.

== 정의 ==
두 개의 [[집합]] <math>N</math>과 <math>X</math>가 있다고 하고, 그 [[집합의 크기|크기]]가 각각
:<math>|N|=n</math>
:<math>|X|=x</math>
라고 하자. 그렇다면, <math>N</math>을 [[정의역]]으로, <math>X</math>를 [[공역]]으로 하는 함수 가운데, 다음과 같은 조건을 부여한 집합을 생각할 수 있다.
* 아무런 조건이 없을 경우, 함수 집합 <math>\operatorname{Fun}(N,X)</math>
* [[단사 함수]]일 경우, 함수 집합 <math>\operatorname{Inj}(N,X)</math>
* [[전사 함수]]일 경우, 함수 집합 <math>\operatorname{Surj}(N,X)</math>
([[전단사 함수]]의 조건을 부여하는 것은 자명하다.)

이 세 개의 집합에, 다음과 같이 4가지의 [[동치 관계]] <math>\sim</math>를 줄 수 있다. 여기서 <math>\operatorname{Sym}(S)</math>는 집합 <math>S</math> 위의 [[순열]]들의 집합([[대칭군 (군론)|대칭군]])이다.
* 함수의 일치 <math>f\sim g\iff f=g</math>
* [[정의역]] <math>N</math>의 [[순열]]을 무시한 동치. 즉, <math>f\sim g\iff\exists\sigma_N\in\operatorname{Sym}(N)\colon f\circ\sigma_N=g\}</math>이다.
* [[공역]] <math>X</math>의 [[순열]]을 무시한 동치. 즉, <math>f\sim g\iff\exists\sigma_X\in\operatorname{Sym}(X)\colon \sigma_X\circ f=g\}</math>이다.
* [[정의역]] <math>N</math>의 [[순열]]과 [[공역]] <math>X</math>의 [[순열]]을 무시한 동치. 즉, <math>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\}</math>이다.
그렇다면, 이 3개의 함수 집합에 4개의 동치 관계를 부여하였을 때 존재하는 [[동치류]]의 수에 대하여 물을 수 있다. 즉, 3×4=12개의 열거 문제가 존재한다. 이를 '''12정도'''라고 한다.

=== 해석 ===
12정도의 문제들은 보통 다음과 같은 용어로 묘사된다.
{| class="wikitable"
|+ 12정도의 공식
|-
! [[동치 관계]] ╲ 함수 조건
! (없음)
! [[단사 함수]]
! [[전사 함수]]
|-
! 함수 일치
| <math>X</math>의 원소들의 길이 <math>n</math>의 열
| <math>X</math>의 원소들의 크기 <math>n</math>의 [[순열]]
| —
|-
! 정의역의 순열을 무시
| <math>X</math>의 크기 <math>n</math>의 부분 [[중복집합]]
| <math>X</math>의 크기 <math>n</math>의 [[부분 집합]]
| —
|-
! 공역의 순열을 무시
| 집합 <math>N</math>의, <math>x</math>개 이하의 부분 집합들로의 [[집합의 분할|분할]]
| —
| 집합 <math>N</math>의, <math>x</math>개의 부분 집합들로의 [[집합의 분할|분할]]
|-
! 정의역과 공역의 순열을 무시
| 자연수 <math>n</math>의, <math>x</math>개 이하의 양의 정수들로의 [[자연수의 분할|분할]]
| —
| 자연수 <math>n</math>의, <math>x</math>개의 양의 정수들로의 [[자연수의 분할|분할]]
|}

이들은 <math>|N|=n</math>개의 공들을 <math>|X|=x</math>개의 통들에 넣는 문제로 해석할 수 있다. 이 경우, 함수에 대한 조건은 통에 들어가는 공의 수에 대한 제약이다. 즉, 다음과 같은 조건을 부여할 수 있다.
* 조건 없음: 각 통에 임의의 수의 공이 들어간다.
* 단사 함수: 각 통에 최대 1개의 공이 들어간다.
* 전사 함수: 각 통에 1개 이상의 공이 들어간다.
함수 집합 위의 [[동치 관계]]는 공이나 통에 부여된 번호(또는 색칠 따위)의 유무에 대응한다.
* 함수 일치: 각 공은 번호 1~<math>n</math>이 매겨져 구별할 수 있으며, 각 통도 마찬가지로 번호 1~<math>x</math>가 매겨져 구별할 수 있다.
* 정의역의 순열을 무시: 통들은 번호가 매겨져 구별할 수 있지만, 공들은 구별할 수 없다.
* 공역의 순열을 무시: 통들은 구별할 수 없지만, 공들은 번호가 매겨져 구별할 수 있다.
* 정의역과 공역의 순열을 무시: 공들과 통들 모두 서로 구별할 수 없다.

12정도는 [[통계역학]]적으로도 생각할 수 있다. 즉, <math>n</math>개의 입자가 <math>x</math>개의 상태에 속한다고 하자. 이 경우, 함수에 대한 조건은 입자들이 따르는 통계이다.
* 조건 없음: 각 상태에 임의의 수의 입자들이 존재할 수 있다 (보스 통계).
* 단사 함수: 각 상태에 최대 1개의 입자가 존재할 수 있다 ([[페르미온]] 통계).
* 전사 함수: 각 상태에 적어도 1개 이상의 입자가 존재하여야 한다.
정의역의 순열의 무시 여부는 입자의 구별 가능성에 대응한다.
* 정의역의 순열을 무시: 입자가 양자 입자여서 서로 구분할 수 없다.
* 정의역의 순열을 무시하지 않음: 입자가 고전적 입자여서 구분 가능하다.
마찬가지로, 공역의 순열의 무시 여부는 다음과 같이 해석할 수 있다.
* 공역의 순열을 무시하지 않음: 각 상태들 역시 [[에너지]] 및 기타 [[양자수]]가 달라 구분 가능하다.
* 공역의 순열을 무시: 입자의 가능한 상태들이 대칭으로 인해 [[겹침 (물리학)|겹침]]이 일어나며, 계 전체에 대칭의 작용은 [[게이지 대칭]]으로 여겨 구분하지 않는다.

== 해 ==
정의역의 크기가 <math>|N|=n</math>, 공역의 크기가 <math>|X|=x</math>라고 하면, 12정도의 해는 다음과 같다.
{| class="wikitable"
|+ 12정도의 공식
|-
! [[동치 관계]] ╲ 함수 조건
! (없음)
! [[단사 함수]]
! [[전사 함수]]
|-
! 함수 일치
| <math>x^n</math>
| <math>x^{\underline n}</math>
| <math>\textstyle x!\{{n\atop x}\}</math>
|-
! 정의역의 순열을 무시
| <math>\textstyle x^{\overline n}/n!=\binom{x+n-1}n</math>
| <math>\textstyle\binom xn</math>
| <math>\textstyle\binom{n-1}{n-x}</math>
|-
! 공역의 순열을 무시
| <math>B_n</math>
| <math>[n\le x]</math>
| <math>\textstyle\{{n\atop x}\}</math>
|-
! 정의역과 공역의 순열을 무시
| <math>p_x(n+x)</math>
| <math>[n\le x]</math>
| <math>p_x(n)</math>
|}
여기서 사용한 기호는 다음과 같다.
* [[계승 (수학)|계승]]
*:<math>x!=x(x-1)\cdots2\cdot1</math>
* [[하강 포흐하머 기호]]
*:<math>x^{\underline n}=x!/(x-n)!</math>
* [[상승 포흐하머 기호]]
*:<math>x^{\overline n}=(x+n-1)!/(x-1)!</math>
* [[이항 계수]]
*:<math>\binom xn=\frac{x!}{n!(x-n)!}=x^{\underline n}/n!</math>
* [[제2종 스털링 수]]
*:<math>\left\{{x\atop n}\right\}</math>
* [[아이버슨 괄호]]. 주어진 조건이 참이면 1, 거짓이면 0이다.
*:<math>[P]=\begin{cases}1&P\\0&\lnot P\end{cases}</math>
* [[분할수]] <math>p_x(n)</math>는 자연수 <math>n</math>을 <math>x</math>개의 조각으로 분할하는 경우의 수이다.
* [[벨 수]]
*:<math>B_n=\sum_{k=0}^x\left\{{n\atop k}\right\}</math>

여기서 전사 함수를 정의역의 순열을 무시하여 세는 것에서, 만약 <math>n>0</math>이거나 <math>x>0</math>일 경우
:<math>\binom{n-1}{n-x}=\binom{n-1}{x-1}</math>
이다. 다만, <math>n=x=0</math>일 경우
:<math>\binom{n-1}{n-x}=\binom{-1}0=1</math>
:<math>\binom{n-1}{x-1}=\binom{-1}{-1}=0</math>
이므로, 전자가 맞는 표현이다.

== 역사 ==
조합론의 열거 문제들을 12가지로 분류하는 것은 [[잔카를로 로타]]가 최초였다. 이후 로타의 제자인 리처드 피터 스탠리({{llang|en|Richard Peter Stanley}})가 1986년에 출판된 교재 《열거 조합론》({{llang|en|Enumerative Combinatorics}})<ref>{{서적 인용|url=http://www-math.mit.edu/~rstan/ec/|제목=Enumerative Combinatorics. Volume 1|이름=Richard P.|성=Stanley|출판사=Wadsworth & Brooks/Cole|날짜=1986|판=1|언어=en}}</ref>에서 "12정도"라는 이름으로 대중화시켰다. "12정도"({{llang|en|Twelvefold Way}})라는 이름은 불교의 [[팔정도]](八正道) 및 [[입자물리학]]의 [[팔정도 (물리학)|팔정도]]({{llang|en|Eightfold Way}})에 빗댄 것이며, 조엘 스펜서({{llang|en|Joel Spencer}})가 명명하였다.

== 참고 문헌 ==
{{각주}}
* {{저널 인용|arxiv=math/0606404|제목=Let's Expand Rota's Twelvefold Way For Counting Partitions!|이름=Robert A. |성=Proctor|bibcode=2006math......6404P|언어=en}}

== 외부 링크 ==
* {{웹 인용|url=http://www.math.wisc.edu/~ddrake/pdf/twelvefold-way.pdf|제목=Stanley’s Twelvefold Way|이름=Dan|성=Drake|날짜=2009-03-09|언어=en|확인날짜=2015-10-21|보존url=https://web.archive.org/web/20150724080305/http://www.math.wisc.edu/~ddrake/pdf/twelvefold-way.pdf#|보존날짜=2015-07-24|url-status=dead}}
* {{웹 인용|url=http://www.johndcook.com/TwelvefoldWay.pdf|제목=Richard Stanley’s Twelvefold Way|이름=John D.|성=Cook|날짜=2009-08-31|언어=en}}
* {{웹 인용|url=http://blog.janmr.com/2008/12/twelve-ways-of-counting.html|제목=Twelve Ways of Counting|이름=Jan Marthedal|성=Rasmussen|웹사이트=janmr blog|날짜=2008-12-26|언어=en|확인날짜=2015-10-21|보존url=https://web.archive.org/web/20160304115201/http://blog.janmr.com/2008/12/twelve-ways-of-counting.html#|보존날짜=2016-03-04|url-status=dead}}

[[분류:조합론]]
[[분류:순열]]