12정도

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

12정도는 집합 N과 X의 함수에 조건을 부여하고, 4가지 동치 관계를 적용하여 12가지 경우로 분류하는 조합론적 문제이다. 이는 유한 개의 구를 유한 개의 상자에 넣는 문제로 비유될 수 있으며, 함수의 단사, 전사 여부와 정의역, 공역의 순열 무시 여부에 따라 경우의 수가 달라진다. 12정도는 공의 개수 n과 상자의 개수 x에 대한 다양한 경우의 수를 계산하는 문제이며, 통계역학, 표본 추출 등 다양한 분야와 연관된다. 이 개념은 잔카를로 로타에 의해 분류되었고, 리처드 피터 스탠리에 의해 "12정도"라는 이름으로 널리 알려지게 되었다.

12정도

📚 더 읽어볼만한 페이지

순열 - 레비치비타 기호
레비치비타 기호는 n차원 공간에서 정의되는 완전 반대칭 텐서로, 순열의 부호에 따라 +1, -1, 0의 값을 가지며 벡터곱, 행렬식 계산 등 다양한 분야에서 활용된다.
순열 - 완전순열
완전순열은 집합의 순열 중 모든 원소가 원래 위치에 있지 않은 순열, 즉 고정점이 없는 순열을 의미하며, 크기가 n인 집합의 완전순열의 수는 준계승 !n으로 나타내고, 점화식 또는 포함-배제 원리로 계산하며, 몽모르 수라고도 불린다.
조합론 - 집합의 분할
집합의 분할은 주어진 집합을 서로소인 부분 집합들로 나누는 것이며, 동치 관계와 밀접하게 관련되어 있고, 벨 수로 표현되며, 플레잉 카드를 나누는 것과 같은 예시가 있다.
조합론 - 계승 (수학)
계승은 음이 아닌 정수 n에 대해 1부터 n까지의 자연수를 곱한 값으로, 0의 계승은 1로 정의되며, 대칭군의 크기와 같다는 성질을 통해 기수로 확장될 수 있고, 다중 계승, 지수 계승 등으로 확장 및 응용되어 다양한 분야에서 활용된다.

1. 개요
2. 정의
3. 해석
4. 해
5. 일반화
6. 역사

2. 정의

집합 $N$ 과 $X$ 가 있고, 그 크기가 각각 $|N|=n$ , $|X|=x$ 라고 하자. $N$ 을 정의역으로, $X$ 를 공역으로 하는 함수에 대해 다음과 같은 조건들을 생각할 수 있다.

* 아무런 조건이 없을 때의 함수 집합: $\operatorname{Fun}(N,X)$
* 단사 함수일 때의 함수 집합: $\operatorname{Inj}(N,X)$
* 전사 함수일 때의 함수 집합: $\operatorname{Surj}(N,X)$
* 전단사 함수 조건은 $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개의 동치 관계를 부여했을 때 존재하는 동치류의 수를 묻는 12가지(3×4=12) 열거 문제가 존재한다. 이를 12정도라고 한다.

이 문제들은 난이도가 모두 같지 않으며, 체계적인 해결 방법은 없다. 문제 중 두 개는 자명하고(동치류 수가 0 또는 1), 다섯 개는 $n$ 과 $x$ 의 곱셈 공식으로, 나머지 다섯 개는 조합 함수(스털링 수, 분할 함수)로 답이 나온다.

3. 해석

12정도는 주어진 함수와 동치 관계에 따라 여러 방식으로 해석될 수 있다.

공과 상자 모델

* 함수: $n$ 개의 공을 $x$ 개의 상자에 넣는 것으로 생각할 수 있다.
* 함수 조건:
* 조건 없음: 각 상자에 임의의 개수의 공을 넣을 수 있다. (보스 통계)
* [[단사 함수]]: 각 상자에 최대 1개의 공만 넣을 수 있다. (페르미온 통계)
* [[전사 함수]]: 각 상자에 적어도 1개의 공을 넣어야 한다.
* 동치 관계:
* 함수 일치: 공과 상자에 번호가 매겨져 있어 서로 구별 가능하다.
* 정의역의 순열 무시: 상자는 구별 가능하지만, 공은 구별할 수 없다.
* 공역의 순열 무시: 공은 구별 가능하지만, 상자는 구별할 수 없다.
* 정의역과 공역의 순열 무시: 공과 상자 모두 서로 구별할 수 없다.

통계역학적 모델

* $n$ 개의 입자가 $x$ 개의 상태에 속하는 것으로 생각할 수 있다.
* 함수 조건:
* 조건 없음: 각 상태에 임의의 수의 입자가 존재할 수 있다. (보스 통계)
* [[단사 함수]]: 각 상태에 최대 1개의 입자가 존재할 수 있다. (페르미온 통계)
* [[전사 함수]]: 각 상태에 적어도 1개 이상의 입자가 존재해야 한다.
* 정의역 순열 무시: 입자들이 서로 구분 불가능한 양자 입자인지에 대응한다.
* 공역 순열 무시: 상태들이 겹침(degeneracy)이 있는지에 대응한다.

표본 추출 모델

* $X$ 개의 항목(또는 사람)의 모집단에서 $N$ 개를 선택하는 문제로 생각할 수 있다.
* [[복원 추출]]: 항목을 선택한 후 다시 모집단에 넣어 다시 선택될 수 있게 한다. (독립 동일 분포)
* [[비복원 추출]]: 항목을 선택한 후 다시 선택할 수 없도록 제거한다.
* 순서 고려: 선택 순서가 중요한 경우 (순열)
* 순서 무시: 선택 순서가 중요하지 않은 경우 (조합)

기타 관점

* 라벨링: $N$ 의 각 원소에 $X$ 의 원소를 라벨링하는 것으로 생각할 수 있다.
* 선택: $N$ 의 각 원소에 대해 $X$ 의 원소 하나를 선택하는 것으로 생각할 수 있다.
* 그룹화: $N$ 의 원소 중 $X$ 의 동일한 원소로 매핑되는 원소들을 함께 그룹화하는 것으로 생각할 수 있다.

4. 해

정의역의 크기가 $|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 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

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

5. 일반화

과 를 유한 집합이라 하고, $n=|N|$ 와 $x=|X|$ 를 각 집합의 기수라고 하자. 즉, 은 개의 원소를, 는 개의 원소를 가진다.

여기서 다루는 일반적인 문제는 함수 $f: N \to X$ 의 동치류를 나열하는 것이다. 함수는 다음 세 가지 제약 조건 중 하나를 따른다.

* 조건 없음: 의 각 원소 는 에 의해 의 어떤 원소 로든 갈 수 있으며, 각 는 여러 번 나타날 수 있다.
* 는 단사 함수: 의 각 에 대한 $f(a)$ 값은 모두 달라야 하므로, 의 각 는 의 상에서 최대 한 번만 나타난다.
* 는 전사 함수: 의 각 에 대해 $f(a) = b$ 인 의 가 적어도 하나 존재해야 하므로, 각 는 의 상에서 적어도 한 번 나타난다.

$n=x$ 인 경우에만 "는 전단사 함수"라는 조건이 추가될 수 있지만, 이 조건은 "는 단사 함수"와 "는 전사 함수" 조건과 동일하다.

에서 로 가는 함수 에 대해 정의할 수 있는 네 가지 동치 관계는 다음과 같다.

* 같음
* 의 순열에 따른 같음
* 의 순열에 따른 같음
* 과 의 순열에 따른 같음

함수에 대한 세 가지 조건과 네 가지 동치 관계를 조합하면 12가지 경우의 수가 생긴다.

함수의 동치류를 세는 열두 가지 문제는 난이도가 서로 다르며, 이를 해결하는 체계적인 방법은 없다. 이 중 두 문제는 간단하고(동치류 개수가 0 또는 1), 다섯 문제는 과 에 대한 곱셈 공식으로 답을 얻을 수 있으며, 나머지 다섯 문제는 조합 함수(스털링 수와 주어진 부분에 대한 분할 함수)를 이용하여 답을 구할 수 있다.

이러한 설정에는 다음과 같은 고전적인 조합 문제들이 포함된다.

* 의 -순열(부분 순열 또는 중복 없는 순열)을 세는 것은 단사 함수를 세는 것과 같다.
* 의 -조합을 세는 것은 의 순열까지의 단사 함수를 세는 것과 같다.
* 집합 의 순열을 세는 것은 = 일 때 단사 함수 를 세는 것과 같으며, = 일 때 전사 함수를 세는 것과 같다.
* 원소로 이루어진 크기 의 중복집합(중복을 허용하는 -조합)을 세는 것은 의 순열까지 모든 함수를 세는 것과 같다.
* 집합 을 개의 부분집합으로 분할하는 것은 의 순열까지 모든 전사 함수를 세는 것과 같다.
* 을 개의 부분으로 분할하는 것은 의 순열까지 모든 전사 함수를 세는 것과 같다.

과 에 작용하는 다른 순열군을 허용하면 더 일반화할 수 있다. 가 의 순열군이고, 가 의 순열군일 때, 함수 $f \colon N \rightarrow X$ 의 동치류를 계산한다. 이때 두 함수 와 는 $g\in G, h \in H$ 가 존재하여 $F = h \circ f \circ g$ 를 만족하는 경우에만 동치로 간주한다. 이러한 확장은 순환 순열, 이산면체군과 같은 개념과 숫자 및 집합의 순환 및 이산면체 분할로 이어진다.

케네스 P. 보가트는 그의 저서 "가이드된 발견을 통한 조합론(Combinatorics Through Guided Discovery)"에서 "20가지 방식"이라 불리는 또 다른 일반화를 제시했다. 이는 물체를 상자에 분배하는 문제에서 물체와 상자가 모두 동일하거나 구별될 수 있는 경우를 고려하여 20가지 경우를 식별한다. 로버트 A. 프록터는 30가지 방식을 구성했다.

👆

좌우로 밀어서 보기

20가지 방식; 개의 물체를 명의 수령인에게 분배하는 모델
번호	물체	분배 조건	수령인
번호	물체	분배 조건	구별됨	동일함
1	구별됨	제한 없음	에서 로의 시퀀스	을 ≤ 개의 부분 집합으로 분할
2		각각 최대 하나	의 순열
3		각각 최소 하나	을 개의 부분 집합으로 구성	을 개의 부분 집합으로 분할
4		각각 정확히 하나	순열
5	구별됨, 순서 지정됨	제한 없음	순서가 지정된 함수	분할된 순열(≤ 부분)
6	구별됨, 순서 지정됨	각각 최소 하나	순서가 지정된 전사 함수	$L(n,x) = \left( {n \atop x} \right) (n-1)^{\underline{n-x}}$ 분할된 순열 ( 부분) 여기서 $L(n,x)$ 는 라 수
7	동일함	제한 없음	의 다중 부분 집합	분할 숫자(≤ 부분)
8		각각 최대 하나	의 부분 집합
9		각각 최소 하나	조성 ( 부분)	을 부분으로 분할
10		각각 정확히 하나

6. 역사

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

케네스 P. 보가트는 그의 저서 "가이드된 발견을 통한 조합론(Combinatorics Through Guided Discovery)"에서 "20가지 방식"이라고 불리는 또 다른 일반화를 개발했다. 보가트는 물체를 상자에 분배하는 문제에서 물체와 상자 모두 동일하거나 구별될 수 있는 20가지 경우를 식별한다. 로버트 A. 프록터는 30가지 방식을 구성했다.