Question 79
Given an one-to-one correspondence $f : \{1, 2, \dots, n\} \to \{1, 2, \dots, n\}$ for some positive integer $n$, define four sets $A$, $B$, $C$, $D$ as follows:
$$
A = \{i \mid i \gt f(i)\}
$$
$$
B = \{(i, j) \mid i \lt j \le f(j) \lt f(i) \text{ or } f(j) \lt f(i) \lt i \lt j\}
$$
$$
C = \{(i, j) \mid i \lt j \le f(i) \lt f(j) \text{ or } f(i) \lt f(j) \lt i \lt j\}
$$
$$
D = \{(i, j) \mid i \lt j \text{ and } f(i) \gt f(j)\}
$$
Prove that $|A| + 2|B| + |C| = |D|$, where $|X|$ is the number of all elements in $X$.
$$
A = \{i \mid i \gt f(i)\}
$$
$$
B = \{(i, j) \mid i \lt j \le f(j) \lt f(i) \text{ or } f(j) \lt f(i) \lt i \lt j\}
$$
$$
C = \{(i, j) \mid i \lt j \le f(i) \lt f(j) \text{ or } f(i) \lt f(j) \lt i \lt j\}
$$
$$
D = \{(i, j) \mid i \lt j \text{ and } f(i) \gt f(j)\}
$$
Prove that $|A| + 2|B| + |C| = |D|$, where $|X|$ is the number of all elements in $X$.