확률과 통계 > 여러 가지 순열과 조합

응용 : 함수와 경우의 수

함수는 수능에서 매우 중요하게 다루어지는 개념이므로 경우의 수에 함수를 섞어 출제하는 경우가 많습니다. 우리가 알고 있는 개념들을 이용하여 함수와 경우의 수를 엮어 다루어봅시다.

정의역이 $X_f$이고 공역이 $Y_f$인 함수 $f$, 정의역이 $X_g$이고 공역이 $Y_g$인 함수 $g$, 정의역이 $X_h$이고 공역이 $Y_h$인 함수 $h$에 대하여 \[\begin{alignat*}{3} &X_f =\left\{ 1, 2, 3, 4 \right\}\qquad &&X_g =\left\{ 1, 2, 3, 4 \right\} \qquad &&X_h =\left\{ 1, 2, 3, 4, 5 \right\}\\ &Y_f =\left\{ 1, 2, 3, 4, 5 \right\}\qquad &&Y_g =\left\{ 1, 2, 3, 4 \right\} &&Y_h =\left\{ 1, 2, 3, 4 \right\}\qquad \end{alignat*}\] 일 때, 다음의 추가적인 조건을 만족시키는 함수 $f$, $g$, $h$의 개수를 구하시오.
  1. 아무런 추가 조건 없음.
  2. 일대일함수이다.
  3. 공역과 치역이 같다.
  4. 일대일대응이다.
  5. 역함수가 존재한다.

  1. 정의역의 원소 $1$와 대응되는 함숫값 $f\left( 1 \right) $은 $1$, $2$, $3$, $4$, $5$가 될 수 있습니다. 따라서 $1$에 대응되는 함숫값을 선택하는 방법의 수는 $5$입니다. 이는 $2$, $3$, $4$에 대해서도 모두 마찬가지입니다. 따라서 모든 함수 $f$의 개수는 $5\times 5\times 5\times 5 = 5^4$입니다. 같은 방법으로 모든 함수 $g$, $h$의 개수를 구하면 각각 $4^4$, $4^5$입니다.
  2. $n \left( X_i \right) =m$와 $n\left( Y_i \right)=n$의 대소관계에 따라 분류해봅시다.
    1. $m < n $ : 공역의 원소 $n$개 중에서 치역의 원소가 될 $m$개를 선택하는 방법의 수는 $\NCR nm$이고, 선택된 $m$개의 원소를 $X$의 원소 $m$개에 대응시키는 방법의 수는 $m!$입니다. 따라서 일대일함수의 개수는 $\NCR nm \times m!$입니다.1이는 $\NPR nm$이지만, 우리는 앞서 자연스러운 풀이를 위하여 $\NPR nr$을 쓰지 않기로 약속했습니다.
    2. $m=n$ : 공역의 원소 $n$개 중에서 치역의 원소가 될 $m$개를 선택하는 방법의 수는 $\NCR nm=\NCR nn=1$이고, 선택된 $m$개의 원소를 $X$의 원소 $m$개에 대응시키는 방법의 수는 $m!$입니다. 따라서 일대일함수의 개수는 $m! = n!$입니다.
    3. $m>n$ : 정의역의 원소 중 $m-n$개는 함숫값이 정의되지 않으므로, 일대일함수는 존재하지 않습니다.
    따라서 일대일함수 $f$, $g$의 개수는 $\left( 1 \right) $, $\left( 2 \right) $의 경우이므로 각각 $\NCR{5}{4}\times 4!$, $4!$입니다. 일대일함수 $h$는 $\left( 3 \right) $의 경우이므로 존재하지 않습니다.
  3. $m$과 $n$의 대소관계에 따라 분류해봅시다.
    1. $m < n $ : 치역의 원소는 최대 $m$개이고, 공역의 원소는 $n$개입니다. 따라서 공역과 치역이 같은 함수는 존재하지 않습니다.
    2. $m=n$ : 공역의 원소 $n$개가 모두 치역의 원소가 되어야 하고, 선택된 $n = m$개의 원소를 $X$의 원소 $m$개에 대응시키는 방법의 수는 $m!$입니다. 따라서 공역과 치역이 같은 함수의 개수는 $m! = n!$입니다.
    3. $m>n$ : 공역의 원소 $n$개가 모두 치역의 원소가 되어야 하고, 선택된 $n$개의 원소를 $X$의 원소 $m$개에 대응시키는 방법의 수는 앞서 `모둠 만들기'에서 배웠던 $m$명을 $n$개의 모둠으로 나누고, $n$개의 모둠을 $n$개의 원소에 하나씩 대응시키는 경우의 수와 같습니다.
    따라서 \hcn3을 만족시키는 함수 $f$는 $\left( 1 \right) $의 경우이므로 존재하지 않고, $g$의 개수는 $\left( 2 \right) $의 경우이므로 $4!$입니다. \hcn3을 만족시키는 함수 $h$의 개수는 $\left( 3 \right) $의 경우이므로 $5$명을 $4$개의 모둠으로 나누고, $4$개의 모둠을 $4$개의 원소에 하나씩 대응시키는 경우의 수와 같습니다. 이는 $2$명, $1$명, $1$명, $1$명으로 모둠을 만들고 일대일대응시키는 경우뿐이므로 $\NCR52 \times \NCR31\times \NCR21\times \dfrac{1}{3!}\times 4! = 240$입니다.2모둠을 나누는 방법이 다양할 경우는 합의 법칙을 이용하여야 합니다. 예를 들어 $7$명을 $3$개의 모둠으로 나누는 방법의 수는 $\xyz 115$, $\xyz 124$, $\xyz 133$, $\xyz 223$이므로 각각의 경우의 수를 모두 더해야 합니다.
  4. 일대일대응이려면, ②와 \hcn3을 동시에 만족시켜야 합니다. 따라서 일대일대응인 함수 $f$, $h$는 존재하지 않고, 일대일대응인 함수 $g$의 개수는 $4!$입니다.
  5. \hcn5는 \hcn4의 경우와 동치입니다. 따라서 \hcn4의 답과 같습니다.
정의역이 $X_f$이고 공역이 $Y_f$인 함수 $f$, 정의역이 $X_g$이고 공역이 $Y_g$인 함수 $g$, 정의역이 $X_h$이고 공역이 $Y_h$인 함수 $h$에 대하여 \[\begin{alignat*}{3} &X_f =\left\{ 1, 2, 3, 4 \right\}\qquad &&X_g =\left\{ 1, 2, 3, 4 \right\} \qquad &&X_h =\left\{ 1, 2, 3, 4, 5 \right\}\\ &Y_f =\left\{ 1, 2, 3, 4, 5 \right\}\qquad &&Y_g =\left\{ 1, 2, 3, 4 \right\} &&Y_h =\left\{ 1, 2, 3, 4 \right\}\qquad \end{alignat*}\] 일 때, 다음의 추가적인 조건을 만족시키는 함수 $f$, $g$, $h$의 개수를 구하시오.3문제에서 정의역이 $X_i$이고 공역이 $Y_i$인 함수 $i\left( x \right) $에 대한 조건이 주어진 경우는 $f$, $g$, $h$의 상황을 각각 대응시켜 생각하면 됩니다.
  1. $1 \le k < n\left( X_i \right) $인 모든 자연수 $k$에 대하여 $i\left( k \right) < i\left( k+1 \right) $이다.
  2. $1 \le k < n\left( X_i \right) $인 모든 자연수 $k$에 대하여 $i\left( k \right) > i\left( k+1 \right) $이다.
  3. $1 \le k < n\left( X_i \right) $인 모든 자연수 $k$에 대하여 $i\left( k \right) \le i\left( k+1 \right) $이다.
  4. $1 \le k < n\left( X_i \right) $인 모든 자연수 $k$에 대하여 $i\left( k \right) \ge i\left( k+1 \right) $이다.
  5. $1 \le k\le n\left( X_i \right) $인 모든 자연수 $k$에 대하여 $k \ne i\left( k \right) $이다.
  6. 공역과 치역이 같고, $1 \le k\le n\left( X_i \right) $인 모든 자연수 $k$에 대하여 $k \ne i\left( k \right) $이다.
  1. $m$과 $n$의 대소관계에 따라 분류해봅시다.
    1. $m < n $ : 공역의 원소 $n$개 중에서 치역의 원소 $m$개를 선택하기만 하면, 함숫값의 대소관계(순서)가 정해져 있기 때문에 대응 관계는 하나로 정해집니다. 따라서 ①을 만족시키는 함수의 개수는 $\NCR{n}{m}$입니다.
    2. $m=n$ : 공역의 원소 $n$개 중에서 치역의 원소 $m$개를 선택하기만 하면, 함숫값의 대소관계(순서)가 정해져 있기 때문에 대응 관계는 하나로 정해집니다. 따라서 ①을 만족시키는 함수의 개수는 $\NCR{n}{m} = \NCR{n}{n} = 1 $입니다.
    3. $m>n$ : ①을 만족시키는 함수는 일대일함수이므로, 존재하지 않습니다.
    따라서 ①을 만족시키는 함수 $f$의 개수는 $\left( 1 \right) $의 경우이므로 $\NCR{5}{4} = 5$입니다. ①을 만족시키는 함수 $g$의 개수는 $\left( 2 \right) $의 경우이므로 $1$입니다. ①을 만족시키는 함수 $h$는 $\left( 3 \right) $의 경우이므로 존재하지 않습니다.
  2. ①과 마찬가지로 함숫값 사이의 대소관계가 정해져 있습니다. 단지 그 방향이 반대일 뿐입니다. 따라서 이는 ①과 답이 같습니다.
  3. 공역의 원소 $n$개 중에서 중복을 허용하여 치역의 원소 $m$개를 선택하기만 하면, 함숫값의 대소관계가 정해져 있으므로 대응 관계는 하나로 정해집니다. 따라서 \hcn3을 만족시키는 함수의 개수는 $\NHR{n}{m}$입니다. 그러므로 함수 $f$의 개수는 $\NHR{5}{4} = \NCR{8}{4} = 70$, 함수 $g$의 개수는 $\NHR44 = \NCR73 = 35$, 함수 $h$의 개수는 $\NHR45 = \NCR{8}{3} = 56$입니다.
  4. \hcn3과 마찬가지로 함숫값 사이의 대소관계가 정해져 있습니다. 단지 그 방향이 반대일 뿐입니다. 따라서 이는 \hcn3과 답이 같습니다.
  5. $f$의 경우 정의역의 원소가 각각 자기 자신을 함숫값으로 취하지 않으면 되므로, 곱의 법칙에 의해 $4^4$입니다. $g$의 경우 같은 원리로 $3^4$입니다. $h$의 경우 $5$는 아무 함숫값이나 취해도 되므로 $4$이고, 나머지는 $f$와 $g$에서와 같은 논리로 $3^4$입니다. 따라서 곱의 법칙에 의해 $4\times 3^4$입니다.
  6. $f$, $g$, $h$의 경우를 각각 풀어보도록 하겠습니다.
    1. $f$의 경우, 예제 $1$의 \hcn3에 의해 존재하지 않습니다.
    2. $g$의 경우, 물물교환하는 상황과 같으므로 $9$입니다.
    3. $h$의 경우는 $1$, $2$, $3$, $4$가 각각 대응되는 함숫값의 총 개수가 $3$인 경우와 $4$인 경우로 나눌 수 있습니다. 이때 각 경우에서 $5$의 함숫값은 자유롭게 선택할 수 있으므로 $4$이고, $1$, $2$, $3$, $4$의 함숫값은 합, 곱의 법칙을 적절히 사용해 계산하면 각각 $3\times \left( 2+2 \right) = 12 $, $9$입니다.4이는 물물교환하는 경우의 수를 계산하는 과정과 동일하므로, 직접 계산해보시기 바랍니다. 따라서 $h$의 개수는 $4\times \left( 12+9 \right) = 84$입니다.
  1. 1. 이는 $\NPR nm$이지만, 우리는 앞서 자연스러운 풀이를 위하여 $\NPR nr$을 쓰지 않기로 약속했습니다.
  2. 2. 모둠을 나누는 방법이 다양할 경우는 합의 법칙을 이용하여야 합니다. 예를 들어 $7$명을 $3$개의 모둠으로 나누는 방법의 수는 $\xyz 115$, $\xyz 124$, $\xyz 133$, $\xyz 223$이므로 각각의 경우의 수를 모두 더해야 합니다.
  3. 3. 문제에서 정의역이 $X_i$이고 공역이 $Y_i$인 함수 $i\left( x \right) $에 대한 조건이 주어진 경우는 $f$, $g$, $h$의 상황을 각각 대응시켜 생각하면 됩니다.
  4. 4. 이는 물물교환하는 경우의 수를 계산하는 과정과 동일하므로, 직접 계산해보시기 바랍니다.