어떤 문제인가
이 문제는 주어진 세 가지 조건을 만족하는 함수 $f$의 개수를 구하는 문제입니다. 문제를 풀기 위해 이해해야 할 핵심 개념은 다음과 같습니다.
- 치역과 합성함수의 치역: 함수 $f$의 치역 $A$와 합성함수 $f \circ f$의 치역 $B$ 사이의 관계를 이해해야 합니다.
- 일대일 대응과 완전순열(교란순열): 자기 자신으로 화살표를 보내지 않는 ($f(x) \ne x$) 함수를 구성하는 방법입니다.
- 경우의 수 나누기: 조건 (가)에 따라 치역의 원소 개수가 될 수 있는 상황을 나누어 각각 계산합니다.
단계별 풀이
1단계: 조건 (나)와 (다)의 의미 해석하기
가장 먼저 조건 (나) $n(A) = n(B)$와 조건 (다) $f(x) \ne x$가 무엇을 뜻하는지 알아봅시다.
- **치역 $A$와 $B$의 관계**:
$A$는 $f$의 치역이므로 $A = f(X)$입니다. 합성함수의 치역 $B$는 $B = f(f(X)) = f(A)$가 됩니다.
즉, $B$는 집합 $A$의 원소들이 함수 $f$에 의해 이동한 결과입니다. 따라서 항상 $B \subseteq A$가 성립합니다.
그런데 조건 (나)에서 두 집합의 원소 개수가 같다고 했으므로, 사실상 **$A = B$**가 되어야 합니다.
이것이 가능하려면, **함수 $f$를 치역 $A$ 안에서만 생각했을 때 ($f|_A : A \to A$), 이 함수는 일대일 대응(일대일 함수)**이어야 합니다. 만약 $A$의 서로 다른 두 원소가 $A$ 안의 같은 원소로 간다면 원소의 개수가 줄어들어 $n(B) < n(A)$가 되기 때문입니다.
- 조건 (다)의 적용:
모든 $x \in X$에 대해 $f(x) \ne x$입니다.
특히 치역 $A$에 속하는 원소 $a \in A$에 대해서도 $f(a) \ne a$여야 합니다.
즉, 치역 $A$에서 $A$로 가는 일대일 대응 $f|_A$는 자기 자신으로 가지 않는 일대일 대응(완전순열 또는 교란순열)이어야 합니다.
2단계: 조건 (가) $n(A) \le 3$에 따라 경우 나누기
치역 $A$의 원소 개수는 자연수이므로 $n(A)$는 $1, 2, 3$ 중 하나가 될 수 있습니다. 각각의 경우를 살펴봅시다.
경우 1) $n(A) = 1$인 경우
- 치역 $A$의 원소가 1개뿐이므로, $A = \{a\}$라고 해봅시다.
- 그러면 모든 $x \in X$에 대해 $f(x) = a$여야 합니다.
- 이 경우, $f(a) = a$가 되어 조건 (다) $f(x) \ne x$에 모순이 됩니다.
- 따라서 **$n(A) = 1$인 경우는 존재하지 않습니다.**
경우 2) $n(A) = 2$인 경우
치역 $A$의 원소가 2개인 경우입니다.
- **치역 $A$ 선택하기**: 전체 5개의 원소 중 $A$가 될 2개의 원소를 고릅니다.
$$\binom{5}{2} = 10 \text{가지}$$
예를 들어, $A = \{1, 2\}$라고 해봅시다.
- **치역 $A$에서의 함수 정의하기**: $f|_A : A \to A$는 자기 자신으로 가지 않는 일대일 대응이어야 합니다.
$A = \{1, 2\}$일 때, $f(1) \ne 1$, $f(2) \ne 2$여야 하므로 가능한 대응은 오직 하나뿐입니다.
$$f(1) = 2, \quad f(2) = 1 \quad (1\text{가지})$$
- 나머지 원소들의 화살표 정하기: $X \setminus A = \{3, 4, 5\}$의 원소들은 치역이 $A = \{1, 2\}$가 되도록 화살표를 보내야 합니다.
이 원소들은 $A$에 포함되지 않으므로, $f(x) \ne x$ 조건은 자동으로 만족합니다. (예를 들어 $f(3)$은 $1$ 또는 $2$로 가므로 절대 $3$이 될 수 없습니다.)
따라서 $3, 4, 5$ 각각이 갈 수 있는 길은 $1$ 또는 $2$로 2가지씩 있습니다.
$$2 \times 2 \times 2 = 2^3 = 8 \text{가지}$$
- 경우 2의 총 개수:
$$10 \times 1 \times 8 = 80 \text{가지}$$
경우 3) $n(A) = 3$인 경우
치역 $A$의 원소가 3개인 경우입니다.
- **치역 $A$ 선택하기**: 전체 5개의 원소 중 $A$가 될 3개의 원소를 고릅니다.
$$\binom{5}{3} = 10 \text{가지}$$
예를 들어, $A = \{1, 2, 3\}$이라고 해봅시다.
- **치역 $A$에서의 함수 정의하기**: $f|_A : A \to A$는 자기 자신으로 가지 않는 일대일 대응(원소 3개짜리 완전순열)이어야 합니다.
$A = \{1, 2, 3\}$일 때 가능한 대응은 다음과 같이 2가지가 있습니다.
* $f(1)=2, f(2)=3, f(3)=1$
* $f(1)=3, f(2)=1, f(3)=2$
$$2\text{가지}$$
- 나머지 원소들의 화살표 정하기: $X \setminus A = \{4, 5\}$의 원소들은 치역 $A = \{1, 2, 3\}$ 중 하나로 화살표를 보내야 합니다.
이 역시 자기 자신으로 가지 않는 조건은 자동으로 만족합니다.
$4$와 $5$ 각각이 갈 수 있는 길은 $1, 2, 3$ 중 하나이므로 3가지씩 있습니다.
$$3 \times 3 = 3^2 = 9 \text{가지}$$
- 경우 3의 총 개수:
$$10 \times 2 \times 9 = 180 \text{가지}$$
3단계: 최종 계산
구하고자 하는 함수 $f$의 개수는 경우 2와 경우 3의 합입니다.
$$80 + 180 = 260$$
답
$$260$$
확인해보기
오늘 배운 개념을 잘 이해했는지 스스로 점검해 봅시다.
질문: 만약 조건 (가)가 $n(A) \le 4$로 바뀌었다면, $n(A) = 4$인 경우를 구하기 위해 원소가 4개인 집합에서 자기 자신으로 가지 않는 일대일 대응(완전순열)의 개수를 구해야 합니다. 이 개수는 모두 몇 가지일까요? (직접 수형도를 그리거나 규칙을 찾아보세요!)