12정도

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

정의

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

| N | = n

| X | = x

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

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

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

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

함수의 일치 $f \sim g ⟺ f = g$
정의역 $N$ 의 순열을 무시한 동치. 즉, $f \sim g ⟺ \exists σ_{N} \in Sym (N) : f \circ σ_{N} = g}$ 이다.
공역 $X$ 의 순열을 무시한 동치. 즉, $f \sim g ⟺ \exists σ_{X} \in Sym (X) : σ_{X} \circ f = g}$ 이다.
정의역 $N$ 의 순열과 공역 $X$ 의 순열을 무시한 동치. 즉, $f \sim g ⟺ \exists σ_{N} \in Sym (N), σ_{X} \in Sym (X) : : σ_{X} \circ f \circ σ_{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}}$	$x! {\binom{n}{x}}$
정의역의 순열을 무시	$x^{\overline{n}} / n! = (\binom{x + n - 1}{n})$	$(\binom{x}{n})$	$(\binom{n - 1}{n - x})$
공역의 순열을 무시	$B_{n}$	$[n \leq x]$	${\binom{n}{x}}$
정의역과 공역의 순열을 무시	$p_{x} (n + x)$	$[n \leq x]$	$p_{x} (n)$

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

계승
$x! = x (x - 1) \dots 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종 스털링 수
${\binom{x}{n}}$
아이버슨 괄호. 주어진 조건이 참이면 1, 거짓이면 0이다.
$[P] = {\begin{matrix} 1 & P \\ 0 & \neg P \end{matrix}$
분할수 $p_{x} (n)$ 는 자연수 $n$ 을 $x$ 개의 조각으로 분할하는 경우의 수이다.
벨 수
$B_{n} = \sum_{k = 0}^{x} {\binom{n}{k}}$

여기서 전사 함수를 정의역의 순열을 무시하여 세는 것에서, 만약 $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가지로 분류하는 것은 잔카를로 로타가 최초였다. 이후 로타의 제자인 리처드 피터 스탠리(틀:Llang)가 1986년에 출판된 교재 《열거 조합론》(틀:Llang)^[1]에서 "12정도"라는 이름으로 대중화시켰다. "12정도"(틀:Llang)라는 이름은 불교의 팔정도(八正道) 및 입자물리학의 팔정도(틀:Llang)에 빗댄 것이며, 조엘 스펜서(틀:Llang)가 명명하였다.

참고 문헌

틀:각주

틀:저널 인용

외부 링크

↑ 틀:서적 인용

[1] 틀:서적 인용

[1]

12정도

목차

정의

해석

해

역사

참고 문헌

외부 링크

둘러보기 메뉴

12정도

정의

해석

해

역사

참고 문헌

외부 링크

둘러보기 메뉴

검색