자연계열 3번

[3.1] ① $\displaystyle f(1)=1$이므로 함수 $\displaystyle f$의 개수는 $\displaystyle \{2,3,\ldots,k\}$에서 $\displaystyle Y$로의 함수의 개수와 같다. 그러므로 $\displaystyle n$개에서 중복을 허락하여 $\displaystyle k-1$개를 택하여 일렬로 나열하는 수 $\displaystyle {}_{n}\Pi_{k-1}=n^{k-1}$이다.② 합성함수 $\displaystyle g\circ f$는 $\displaystyle X$에서 $\displaystyle X$로의 함수이므로 $\displaystyle k$개에서 중복을 허락하여 $\displaystyle k$개를 택하여 일렬로 나열하는 수 $\displaystyle {}_{k}\Pi_k=k^k$이다.

[3.2] 합성함수 $\displaystyle g\circ f$는 항등함수이므로 1가지이다.

[3.3] 조건을 만족하는 합성함수 $\displaystyle g\circ f$는 $\displaystyle X$의 $\displaystyle k$개의 수 $\displaystyle 1,2,\ldots,k$에서 중복을 허락하여 $\displaystyle k$개를 택한 후, 그 $\displaystyle k$개의 수를 작은 것부터 크기순으로 일렬로 나열하고 차례로 $\displaystyle (g\circ f)(1)$, $\displaystyle (g\circ f)(2)$, $\displaystyle \ldots,(g\circ f)(k)$에 대응시키면 된다. 따라서 합성함수 $\displaystyle g\circ f$의 개수는 $\displaystyle k$개에서 중복을 허락하여 $\displaystyle k$개를 택하는 조합인 중복조합의 수 $\displaystyle {}_{k}\mathrm H_k$(또는 $\displaystyle {}_{2k-1}\mathrm C_k=\frac{(2k-1)!}{(k-1)!k!}$)이다.

[3.4] $\displaystyle f$는 일대일함수이어야 한다. 일대일함수 $\displaystyle f$의 개수는 $\displaystyle n$개에서 $\displaystyle k$개를 택하여 일렬로 나열하는 순열의 수 $\displaystyle {}_{n}\mathrm P_k=\frac{n!}{(n-k)!}$이다.

[3.5] 함수 $\displaystyle g$는 $\displaystyle f(X)$에서 $\displaystyle X$로는 일대일로 대응되어야 하고, $\displaystyle Y-f(X)$에서 $\displaystyle X$로는 어떠한 값이라도 대응되면 된다. 함수 $\displaystyle f$는 일대일함수이고 $\displaystyle f(X)$의 원소의 개수는 $\displaystyle k$이므로 $\displaystyle f(X)$에서 $\displaystyle X$로의 일대일로 대응시키는 방법은 $\displaystyle {}_{k}\mathrm P_k=k!$가지이다. 또한, $\displaystyle Y-f(X)$에서 $\displaystyle X$로 함수의 조건을 만족하며 대응시키는 방법은 $\displaystyle {}_{k}\Pi_{n-k}=k^{n-k}$가지이다. 그러므로 함수 $\displaystyle g$의 개수는$\displaystyle {}_{k}\mathrm P_k\times{}_{k}\Pi_{n-k}=k!\times k^{n-k}$이다.