제한 조건을 만족하는 함수의 개수와 포함-배제의 원리
두 집합 $X=\{1, 2, 3, 4, 5\}$, $Y=\{1, 2, 3, 4\}$에 대하여 다음 조건을 만족시키는 $X$에서 $Y$로의 함수 $f$의 개수는? [4점]
(가) 집합 $X$의 모든 원소 $x$에 대하여 $f(x) \ge \sqrt{x}$ 이다.
(나) 함수 $f$의 치역의 원소의 개수는 $3$이다.
이 문항은 주어진 부등식 조건을 통해 함수의 함숫값 범위를 제한하고, 치역의 개수 조건에 따라 경우를 논리적으로 분류하여 해결하는 능력을 평가합니다.
조건 (가)에 의해 $f(x) \ge \sqrt{x}$ 가 성립해야 합니다. 정의역 $X=\{1, 2, 3, 4, 5\}$의 각 원소 $x$에 대하여 가능한 함숫값 $f(x)$를 공역 $Y=\{1, 2, 3, 4\}$ 내에서 구해보겠습니다.
$x=1$일 때 : $f(1) \ge 1 \quad \Rightarrow \quad f(1) \in \{1, 2, 3, 4\}$
$x=2$일 때 : $f(2) \ge \sqrt{2} \approx 1.414 \quad \Rightarrow \quad f(2) \in \{2, 3, 4\}$
$x=3$일 때 : $f(3) \ge \sqrt{3} \approx 1.732 \quad \Rightarrow \quad f(3) \in \{2, 3, 4\}$
$x=4$일 때 : $f(4) \ge \sqrt{4} = 2 \quad \Rightarrow \quad f(4) \in \{2, 3, 4\}$
$x=5$일 때 : $f(5) \ge \sqrt{5} \approx 2.236 \quad \Rightarrow \quad f(5) \in \{3, 4\}$
중요 포인트 : $f(1)$만이 유일하게 함숫값으로 $1$을 가질 수 있으며, $f(5)$는 반드시 $3$ 또는 $4$만을 가져야 합니다.
조건 (나)에 의해 함수 $f$의 치역 원소 개수는 $3$개입니다. 공역 $Y$의 원소 $4$개 중 $3$개를 선택하는 방법의 수는 $_4C_3 = 4$가지이므로, 치역이 될 수 있는 집합은 다음과 같이 $4$가지 경우로 나뉩니다.
함숫값으로 $1$을 가질 수 있는 원소는 오직 $x=1$뿐입니다. 따라서 치역에 $1$이 포함되는 위 세 가지 경우는 무조건 $f(1)=1$ 로 고정됩니다.
$f(1)=1$ 이고, $f(5)$는 $3$ 또는 $4$만 가능한데 치역에 $4$가 없으므로 반드시 $f(5)=3$ 이어야 합니다.
남은 정의역 원소 $\{2, 3, 4\}$는 공역 $\{2, 3\}$으로 대응되어야 합니다. 단, 치역에 $2$가 포함되어야 하므로 모두 $3$으로 대응되는 경우(1가지)를 제외해야 합니다.
Case 1과 구조가 동일합니다. $f(1)=1$ 이고, 치역에 $3$이 없으므로 반드시 $f(5)=4$ 이어야 합니다.
남은 $\{2, 3, 4\}$가 $\{2, 4\}$로 대응되며, $2$를 최소 하나 포함해야 하므로 모두 $4$로 가는 경우를 뺍니다.
$f(1)=1$ 고정입니다. 남은 정의역 $\{2, 3, 4, 5\}$는 조건 (가)에 의해 모두 $\{3, 4\}$로 대응될 수 있습니다.
단, 치역이 $\{3, 4\}$를 모두 포함해야 하므로, 전부 $3$으로 가거나 전부 $4$로 가는 $2$가지를 전체에서 제외합니다.
Case 4 : 치역이 $\{2, 3, 4\}$ 인 경우
$x=1, 2, 3, 4$ 모두 $\{2, 3, 4\}$로 자유롭게 갈 수 있습니다. $f(5)$는 여전히 $\{3, 4\}$ 중 하나를 선택해야 합니다. $f(5)$의 선택에 따라 경우를 나누어 포함-배제의 원리(또는 여사건)를 적용합니다.
나머지 $x=\{1, 2, 3, 4\}$는 $\{2, 3, 4\}$로 갈 수 있습니다 (전체 $3^4 = 81$가지). 치역이 $\{2, 3, 4\}$가 되려면 이미 $3$은 확보했으므로 반드시 $2$와 $4$를 적어도 하나씩 포함해야 합니다.
여사건을 빼서 구합니다:
- $2$를 포함하지 않는 경우 ($\{3, 4\}$로만 가는 경우) : $2^4 = 16$가지
- $4$를 포함하지 않는 경우 ($\{2, 3\}$으로만 가는 경우) : $2^4 = 16$가지
- $2$와 $4$ 모두 포함하지 않는 경우 ($\{3\}$으로만 가는 경우, 위 두 경우에 중복 계산됨) : $1^4 = 1$가지
위와 완전히 대칭적인 구조입니다. 이미 $4$를 확보했으므로, $x=\{1, 2, 3, 4\}$가 대응될 때 반드시 $2$와 $3$을 적어도 하나씩 포함해야 합니다.
Case 4 총합 = $50 + 50 = 100$
모든 Case의 경우의 수를 합산합니다. 각 Case는 치역이 다르므로 서로 배반사건입니다.
정답 : ① 128
문제의 조건 (나)는 "치역의 원소가 3개"라고 명시했습니다. 하지만 단순히 "선택 가능한 공역 3개를 뽑아 매핑하면 되겠지"라고 생각하여 여사건(해당 공역의 진부분집합으로 매핑되는 경우)을 빼주지 않는 실수가 매우 흔합니다.
교정 : '치역이 A이다' 라는 말은 A 집합 내의 모든 원소가 적어도 하나의 화살표를 받아야 한다는 것을 의미합니다. 따라서 공역을 A로 제한한 전체 함수 개수에서, A의 진부분집합으로만 화살표가 가는 경우를 반드시 빼주어야 합니다.
조건 (가) $f(x) \ge \sqrt{x}$ 에서 $x=5$일 때 $f(5) \ge \sqrt{5} \approx 2.236$ 이므로 $f(5)$는 $1, 2$를 가질 수 없습니다. 이를 잊고 Case 1 등에서 $f(5)$가 $2$로 가는 경우까지 허용하여 계산하면 오답이 나옵니다.
고등학교 정규 교육과정에서 치역과 공역이 일치하는 함수(전사함수)의 개수를 구할 때는 주로 '조합을 이용한 조 나누기(분할과 분배)' 또는 '여사건과 합의 법칙'을 사용합니다.
방법 1. 분할과 분배 : 예를 들어 정의역 원소가 $4$개, 공역 원소가 $3$개인 경우, 정의역 원소를 $3$개의 비어 있지 않은 부분집합으로 분할($2$개, $1$개, $1$개 조)한 뒤 공역 원소에 일대일 대응시킵니다.
방법 2. 여사건 (이 문항 Step 4의 적용 방식) : 공역의 특정 원소로 화살표가 전혀 가지 않는 경우를 전체에서 빼는 방식입니다. 이 문항처럼 $f(5)$에 특수한 제약 조건이 섞여 있는 경우, 집합의 연산 법칙인 $n(A \cup B) = n(A) + n(B) - n(A \cap B)$ 공식을 활용하여 여사건을 제외해주는 방법이 교육과정에 완벽히 부합하며 계산 구조도 훨씬 깔끔합니다.
위 여사건의 논리를 $m$개의 공역으로 확장하여 일반화한 것이 바로 포함-배제의 원리입니다. (정규 과정에서는 $2 \sim 3$개 원소의 합집합 원소 개수 공식을 배우며, 아래와 같은 시그마($\Sigma$) 일반항은 심화수학이나 이산수학에서 다루게 됩니다.)
정의역 원소가 $n$개이고, 공역 $Y$의 원소가 $m$개일 때, 치역이 $Y$ 전체가 되는(전사 함수) 함수의 개수는 여사건을 이용하여 구합니다. ($A_i$를 공역의 $i$번째 원소를 치역에서 제외하는 사건이라 정의)
전체 함수 개수 $m^n$에서 위 합집합의 크기(적어도 하나의 공역 원소가 비어 있는 경우)를 빼주면 됩니다.
이 문제의 Case 4에서 $f(5)=3$일 때, 나머지 $4$개의 원소가 공역 $3$개($\{2, 3, 4\}$) 중 특정 $2$개($2$와 $4$)를 반드시 치역으로 가져야 하는 상황을 위 공식의 원리를 차용해 쉽게 계산한 것입니다.
■ 좌표평면 위 부등식 영역과 함수 매핑
$x$축과 $y$축 상에 조건 $y \ge \sqrt{x}$ 를 그렸습니다. 격자점들은 가능한 매핑 $(x, f(x))$를 의미합니다. 하단 버튼으로 치역 Case를 선택하면, 조건을 만족하는 무작위 함수 매핑을 시각적으로 확인할 수 있습니다.