함수의 개수

원문 보기: https://dawoum.duckdns.org/wiki/함수의_개수

See also: 중복순열 and 조합

일반적인 함수와 특별한 몇 가지 함수에 대해서 알아 보았습니다. 여기서는 정의역과 공역에 유한 개의 원소를 있을 때, 서로 다른 함수를 몇 개나 만들 수 있을지 알아보겠습니다.

정의역과 공역의 원소의 개수가 같을 때

정의역의 원소가 3개이고 공역의 원소가 3개일 때, 서로 다른 함수는 몇 개나 만들 수 있을까요?
함수는 모든 정의역의 원소가 제각각 공역의 원소에 대응을 마쳤을 때 1개가 만들어집니다. 그러므로, 경우의 수에서 소개한 곱의 법칙을 사용해서 구해야 합니다. 그리고 정의역에 있는 1개의 원소가 공역의 원소를 선택할 때에 제약사항이 없기 때문에 모두 3가지 경우가 발생합니다. 또한, 정의역의 원소가 3개이기 때문에, 제각각(연속으로) 3번을 선택해야 합니다. 즉, 다음과 같이 경우의 수가 구해집니다.

\(\quad\)\(3\times 3\times 3=3^3=(\rm 공역의 개수)^{정의역의 개수}\)

정의역과 공역의 원소의 개수가 같기 때문에 일대일 함수와 일대일 대응의 개수가 같습니다. 그러나, 함수의 개수와는 다릅니다. 왜냐하면, 정의역에 있는 첫번째 원소가 공역의 원소를 선택할 때에는 제약사항이 없습니다. 그러나 두 번째 원소는 일대일이 되기 위해서 첫 번째 원소가 선택한 원소를 선택할 수 없습니다. 따라서, 두 번째 원소는 첫 번째 원소가 선택할 수 있는 원소보다 1개 적게 선택할 수 있습니다.

\(\quad\)\(3\times 2\times 1\)

일반적으로 정의역의 원소가 \(n\)이면, 다음과 같이 구해집니다.

\(\quad\)\(n\times (n-1)\times (n-2) \cdots 2 \times 1=n! \)

항등함수는 정의역과 공역의 원소가 모두 같을 때에만, 1개 만들 수 있습니다. 그러므로 정의역과 공역의 원소가 다르면 항등함수는 만들 수 없습니다.

상수함수는 항상 공역의 개수만큼 만들 수 있습니다.

정의역의 원소의 개수가 많을 때

정의역의 원소가 4개이고 공역의 원소가 3개일 때, 서로 다른 함수는 몇 개나 만들 수 있을까요?

함수는 정의역의 원소마다 공역의 원소를 3개씩 선택할 수 있습니다. 그러나 일대일 함수나 일대일 대응은 만들 수 없습니다. 왜냐하면, 정의역의 원소가 3개이면 공역의 원소가 3개 필요한데, 4번째 정의역의 원소는 선택할 수 있는 공역의 원소가 없기 때문입니다.

• 함수: \(3^4\)
• 일대일함수, 일대일 대응: 0개
• 항등함수: 0개
• 상수함수: 3개

공역의 원소의 개수가 많을 때

정의역의 원소가 3개이고 공역의 원소가 4개일 때, 서로 다른 함수는 몇 개나 만들 수 있을까요? 

일대일 함수는 만들 수 있지만, 일대일 대응은 만들 수 없습니다. 일대일 대응은 정의역과 공역의 개수가 같아야 만들 수 있습니다.

• 함수: \(4^3\)
• 일대일함수: \(4\times 3\times 2\)
• 일대일 대응: 0개
• 항등함수: 0개
• 상수함수: 4개

치역과 공역이 같은 함수의 개수

중복순열#함수의 개수를 참고하십시오.

증가함수의 개수

증가함수나 감소함수의 개수는 어떻게 만들까요? 조합#증가함수, 감소함수의 개수에서 확인하십시오.

비-증가함수 또는 비-감소함수의 개수

중복조합#비-감소 함수 또는 비-증가함수에서 확인하십시오.

응용예제

응용예제1

집합 \(A=\{1,2,3,4\}\)에 대하여 함수 \(f:A \to A\)입니다. 이때, 임의의 \(a \in A\)에 대하여 \(af(a)\)가 짝수인 함수 \(f\)의 개수를 구하여라.

응용예제2

집합 \(X=\{0,1,2,3,4\}\)에 대하여 함수 \(f:X \to X\) 중에서 다음 조건을 만족시키는 함수 \(f\)의 개수는? 

\(\quad\)(ㄱ) 함수 \(f\)는 일대일 대응이다.

\(\quad\)(ㄴ) \(f(0)\left\{f(1)-2\right\} \ne 0\)

\(\quad\)(ㄷ) \(f(0) = f^{-1}(0)\)

응용예제3

다음은 집합 \(X=\{1,2,3,4,5,6\}\)과 함수 \(f: X \to X\)에 대하여 합성함수 \(f\circ f\)의 치역의 원소의 개수가 \(5\)인 함수 \(f\)의 개수를 구하는 과정이다. 

함수 \(f\)와 함수 \(f\circ f\)의 치역을 각각 \(A\)와 \(B\)라 하자. \(n(A)=6\)이면 함수 \(f\)는 일대일 대응이고, 함수 \(f\circ f\)도 일대일 대응이므로 \(n(B)=6\)이다.
또한 \(n(A) \le 4\)이면 \(B \in A\)이므로 \(n(B) \le 4\)이다.
그러므로 \(n(A)=5\), 즉 \(B=A)\인 경우만 생각하면 된다.

(i) \(n(A)=5\)인 \(X\)의 부분집합 \(A\)를 선택하는 경우의 수는 (가)이다.
(ii) (i)에서 선택한 집합 \(A\)에 대하여, \(X\)의 원소 중 \(A\)에 속하지 않는 원소를 \(k\)라 하자. \(n(A)=5\)이므로 집합 \(A\)에서 \(f(k)\)를 선택하는 경우의 수는 (나)이다.
(iii) (i)에서 선택한 \(A=\{a_1,a_2,a_3,a_4,a_5\}\)와 (ii)에서 선택한 \(f(k)\)에 대하여, \(f(k) \in A\)이며 \(A=B\)이므로

\(\quad\)\(A=\{f(a_1),f(a_2),f(a_3),f(a_4),f(a_5)\} \cdots\) (*)

이다. (*)을 만족시키는 경우의 수는 집합 \(A\)에서 집합 \(A\)로의 일대일 대응의 개수와 같으므로 (다)이다.
따라서 (i), (ii), (iii)에 의하여 구하는 함수 \(f\)의 개수는 (가)\(\times\)(나)\(\times\)(다)이다.

위의 (가), (나), (다)에 알맞은 수를 각각 \(p,q,r\)라 할 때, \(p+q+r\)의 값은? [4점] [2019학년도 수능 가형 17번]