f(X)=X 인 부분집합의 개수

실마리: $U$의 원소마다 $f$의 값을 구해 화살표로 이어 보면 몇 개의 순환 고리로 나뉜다. $f ( 1 ) = 3$, $f ( 2 ) = 6$, $f ( 3 ) = 9$, $f ( 4 ) = 2$, $f ( 5 ) = 5$, $f ( 6 ) = 8$, $f ( 7 ) = 1$, $f ( 8 ) = 4$, $f ( 9 ) = 7$ 즉 $1 \rightarrow 3 \rightarrow 9 \rightarrow 7 \rightarrow 1$, $2 \rightarrow 6 \rightarrow 8 \rightarrow 4 \rightarrow 2$, $5 \rightarrow 5$의 세 고리 $C _{1} = \left\{ 1 , 3 , 9 , 7 \right\}$, $C _{2} = \left\{ 2 , 6 , 8 , 4 \right\}$, $C _{3} = \left\{ 5 \right\}$ 로 나뉘고, $f$의 값은 모두 서로 다르다. $f ( X ) = X$라 하면 $x \in X$일 때 $f ( x ) \in f ( X ) = X$이므로, $X$는 어떤 원소를 가지면 그 원소에서 화살표를 따라가며 만나는 원소를 모두 가진다. 즉 $X$는 $C _{1}$, $C _{2}$, $C _{3}$ 중 몇 개의 합집합이다. 거꾸로 고리들의 합집합 $X$에 대하여 $f$는 각 고리의 원소를 같은 고리의 원소로 빠짐없이 옮기므로 $f ( X ) = X$이다. 세 고리 중 하나 이상을 고르는 방법의 수는 $2 ^{3} - 1 = 7$ 따라서 구하는 집합 $X$의 개수는 $7$이다.