함수의 개수

함수

임의의 원소 $x\in X$에 대해, 그에 대응하는 $y\in Y$가 유일하게 존재하면, 함수라고 한다.

$x_1\ne x_2\Rightarrow f(x_1)\ne f(x_2)$ 조건을 만족하면 일대일(1 to 1)이라 부르며, $f(X)=Y$ 조건을 만족하면 전사(onto)라 부른다. 일대일 함수 중 $f(X)=Y$ 조건을 만족하면 일대일 대응(1 to 1, onto)이라 부른다.

$x_1<x_2\Rightarrow f(x_1)<f(x_2)$을 만족하면 (순)증가 함수, $x_1<x_2\Rightarrow f(x_1)\le f(x_2)$을 만족하면 단조 증가 함수라 부른다.

함수의 개수

유형	공식
함수1	${}_{|Y|}{\Pi }_{|X|}$
일대일 함수2	${}_{|Y|}{P}_{|X|}$
일대일 대응 함수3	$|Y|!$
증가 함수45	${}_{|Y|}{C}_{|X|}$
단조 증가 함수67	${}_{|Y|}{H}_{|X|}$
전사 함수8	$S(|X|,|Y|)\times |Y|!$
치역의 원소 개수가 $n$인 함수9	$S(|X|,n)\times n!$

집합의 분할

분할과 분배라는 개념을 확장한 해보자.

$n$개의 원소를 가진 집합을 공집합이 아닌 $k$개의 부분집합으로 분할하는 경우의 수를 $S(n,k)$(제 $2$종 스털링 수)라 한다.

예를들어 $S(4,2)$를 보자. $4$개의 원소를 $2$개로 분할하는 방법은 $\{3,1\}$또는 $\{2,2\}$로 나눌 수 있다. $\{3,1\}$로 나누는 경우의 수는 ${}_4{C}_3\times {}_1{C}_1$이고, $\{2,2\}$로 나누는 경우의 수는 ${}_4{C}_2\times {}_2{C}_2\times \frac{1}{2!}$이므로 $S(4,2)=4+3=7$이다.

같은 방법으로 $S(6,3)$의 경우를 구해보자. $6$개의 원소를 $3$개로 분할하는 방법은 $\{4,1,1\}$ 또는 $\{3,2,1\}$ 또는 $\{2,2,2\}$로 나눌 수 있다. 각각의 경우의 수는 ${}_6{C}_4{\times }_2{C}_1{\times }_1{C}_1\times \frac{1}{2!}$, ${}_6{C}_3{\times }_3{C}_2{\times }_1{C}_1$, ${}_6{C}_2{\times }_4{C}_2{\times }_2{C}_2\times \frac{1}{3!}$이므로 $S(6,3)=15+60+15=90$이다.

Footnotes

1. $X$의 임의의 원소 $x$가 선택할 수 있는 원소의 개수는 $|Y|$개이므로(중복 순열), 함수의 개수는 ${}_{|Y|}{\Pi }_{|X|}$이다. ↩

2. $X$의 한 원소 $x_1$가 선택할 수 있는 원소의 개수는 $|Y|$개다. 일대일 함수의 성질에 의해 $x_2$가 선택할 수 있는 원소의 개수는 $x_1$이 선택하지 않은 나머지 원소이므로 $|Y|-1$이다. 이를 반복하면 일대일 함수의 개수는 ${}_{|Y|}{\mathrm{P}}_{|X|}$이다. ↩

3. 일대일 대응함수는 일대일 함수 중에서 정의역의 원소와 치역의 원소가 같으므로 $|X|=|Y|$이다. 따라서 ${}_{|Y|}{\mathrm{P}}_{|X|}={}_{|Y|}{\mathrm{P}}_{|Y|}=|Y|!$ 이다. ↩

4. 증가 함수는 자명하게 일대일 함수이다. 일대일 함수 중에서 $x_1<x_2$일 때, $f(x_1)<f(x_2)$을 만족 하므로 $|X|!$만큼 중복이 생긴다. 그러므로 $\frac{{}_{|Y|}{\mathrm{P}}_{|X|}}{|X|!}={}_{|Y|}{\mathrm{C}}_{|X|}$이다. ↩

5. $Y$에서 $|X|$개의 원소를 선택하면 $X$의 원소에서 작은 순서대로 $Y$의 원소를 선택해야만 한다. 따라서 ${}_{|Y|}{\mathrm{C}}_{|X|}$이다. ↩

6. 집합 $X$의 원소는 집합 $Y$에서 같은 원소를 선택할 수 있으므로, $X$의 원소를 같은 공이라 생각하고 $Y$의 원소를 서로 다른 바구니라고 생각하자. 그렇다면 서로 다른 바구니에 같은 공을 집어넣는 상황과 같다. 같은 공은 순서가 정해져 있으므로 $x_1<x_2$일 때, $f(x_1)\le f(x_2)$을 만족하므로 ${}_{|Y|}{\mathrm{H}}_{|X|}$이다. ↩

7. 증가함수(조합)에서 집합 $Y$원소의 중복을 허용하므로 중복조합 공식을 사용하면 ${}_{|Y|}{\mathrm{H}}_{|X|}$이다. ↩

8. 앞서 설명에서 $n=|Y|$이므로 $S(|X|,|Y|)\times |Y|!$이다. 전사함수에서 $|Y|\le |X|$여야 함을 주의하자. ↩

9. 포함배제의 원리로 구해도 상관없지만 생각을 조금 바꾸어보자. $X$의 원소를 치역의 개수 $n$개만큼 덩어리로 묶어주는 경우의 수와 덩어리로 묶인 것을 $Y$로 보내는 일대일 대응함수의 개수를 생각하면 서로다른 원소를 $n$개로 묶는 경우의 수인 $S(|X|,n)$와 일대일 함수의 개수인 $n!$로 부터 치역의 개수가 정해진 함수의 개수는 $S(|X|,n)\times n!$임이 유도된다. ↩