함수의 개수 세기

$n = 4$, $5$, $6$일 때, $f \left( f \left( n \right) \right) = n$을 만족시키는 경우는 $f \left( n \right) = n$ 또는 $f \left( n \right) = m$, $f \left( m \right) = n \left( n \neq m , m \in X \right)$ $\cdots$$\cdots$$\left( \right)$ (ⅰ) $f \left( 4 \right) < 4$인 경우 $f \left( 4 \right) = a \left( a < 4 \right)$라 하면 $\left( \right)$에 의하여 $f \left( a \right) = 4$ $f \left( 4 \right) < f \left( a \right)$이므로 조건 (가)를 만족시키는 함수 $f$는 존재하지 않는다. (ⅱ) $f \left( 4 \right) = 4$인 경우 조건 (가)에 의하여 $1 \leq f \left( 1 \right) \leq f \left( 2 \right) \leq f \left( 3 \right) \leq 4$이므로 세 수 $f \left( 1 \right)$, $f \left( 2 \right)$, $f \left( 3 \right)$을 선택하는 경우의 수는 $\mathit{_{4}} {\mathrm{H}} \mathit{_{3}}$ $f \left( 5 \right) = b$라 하면 ($\star$)에 의하여 $f \left( b \right) = 5$이므로 $b \neq 4$ $f \left( b \right) = 5 > f \left( 4 \right) = 4$이므로 조건 (가)에 의하여 $b > 4$ 그러므로 $b = 5$ 또는 $b = 6$ ① $f \left( 5 \right) = 5$인 경우 $f \left( 6 \right) = c$라 하면 (★)에 의하여 $f \left( c \right) = 6$이므로 $c \neq 5$ $f \left( c \right) = 6 > f \left( 4 \right) = 4$이므로 조건 (가)에 의하여 $c > 4$ 그러므로 $c = 6$ $f \left( 4 \right) = 4$, $f \left( 5 \right) = 5$, $f \left( 6 \right) = 6$이므로 조건을 만족시키는 경우의 수는 $\mathit{_{4}} {\mathrm{H}} \mathit{_{3}} \times 1 = \mathit{_{6}} {\mathrm{C}} \mathit{_{3}} = 20$ ② $f \left( 5 \right) = 6$인 경우 $\left( \right)$에 의하여 $f \left( 6 \right) = 5$ 그러므로 $f \left( 4 \right) = 4$, $f \left( 5 \right) = 6$, $f \left( 6 \right) = 5$ 조건을 만족시키는 경우의 수는 $\mathit{_{4}} {\mathrm{H}} \mathit{_{3}} \times 1 = \mathit{_{6}} {\mathrm{C}} \mathit{_{3}} = 20$ ①, ②에 의하여 $f \left( 4 \right) = 4$일 때, 조건을 만족시키는 경우의 수는 $20 + 20 = 40$ (ⅲ) $f \left( 4 \right) = 5$인 경우 $1 \leq f \left( 1 \right) \leq f \left( 2 \right) \leq f \left( 3 \right) \leq 5$이므로 세 수 $f \left( 1 \right)$, $f \left( 2 \right)$, $f \left( 3 \right)$을 선택하는 경우의 수는 $\mathit{_{5}} {\mathrm{H}} \mathit{_{3}}$ $\left( \star \right)$에 의하여 $f \left( 5 \right) = 4$ $f \left( 6 \right) = c$라 하면 $\left( \star \right)$에 의하여 $f \left( c \right) = 6$이므로 $c \neq 5$ $f \left( c \right) = 6 > f \left( 4 \right) = 5$이므로 조건 (가)에 의하여 $c > 4$ 그러므로 $c = 6$ $f \left( 4 \right) = 5$, $f \left( 5 \right) = 4$, $f \left( 6 \right) = 6$이므로 조건을 만족시키는 경우의 수는 $\mathit{_{5}} {\mathrm{H}} \mathit{_{3}} \times 1 = \mathit{_{7}} {\mathrm{C}} \mathit{_{3}} = 35$ 따라서 (ⅰ), (ⅱ), (ⅲ)에 의하여 $40 + 35 = 75$