Given a set $S_n = \{1, 2, 3, \ldots, n\}$, we define a preference list to be an ordered subset of $S_n$. Let $P_n$ be the number of preference lists of $S_n$. Show that for positive integers $n > m$, $P_n - P_m$ is divisible by $n - m$.
Note: the empty set and $S_n$ are subsets of $S_n$.
We wish to show that if $n$ and $k$ are positive integers, then $k \mid P_{n + k} - P_n$. However, $P_{n + k} - P_n$ is just the number of ordered subsets of $S_{n + k}$ containing at least one of $n + 1, \dots, n + k$.
Let $\mathcal{F}$ be the family of all ordered subsets of $S_{n + k}$ containing at least one of $n + 1, \dots, n + k$, and define $f: \mathcal{F} \to \mathcal{F}$ by cycling the numbers $n + 1 \to n + 2 \to \cdots \to n + k \to n + 1$ in each $T \in \mathcal{F}$. It is obvious that $f^k(T) = T$ for any $T \in \mathcal{F}$, and that $f^r(T) \neq T$ for all $T \in \mathcal{F}$ and $1 \le r \le k - 1$.
Thus, $f$ splits $\mathcal{F}$ into orbits of size $k$, so $k \mid |\mathcal{F}| = P_{n + k} - P_n$, as desired.