진부분집합 사슬을 이루는 순서쌍의 개수

실마리: $A \subset B \subset U$이면 $U$의 원소는 각각 $A$, $B - A$, $U - B$ 중 꼭 한 곳에 속한다. 먼저 $A \subset B \subset U$인 순서쌍 $( A , B )$의 개수를 구한다. $U$의 원소 $6$개가 각각 세 자리 $A$, $B - A$, $U - B$ 중 어디에 들어가는지 정하면 $( A , B )$가 하나 정해지므로 그 개수는 $3 ^{6} = 729$ 이 중에서 조건에 어긋나는 것을 뺀다. $A = B$인 것: $B - A = \emptyset$이므로 원소마다 $A$, $U - B$ 두 자리 중 하나 → $2 ^{6} = 64$개 $B = U$인 것: $U - B = \emptyset$이므로 원소마다 $A$, $B - A$ 두 자리 중 하나 → $2 ^{6} = 64$개 $A = B$이고 $B = U$인 것: $A = B = U$의 $1$개 따라서 구하는 순서쌍의 개수는 $729 - 64 - 64 + 1 = 602$