Problem

Source: Canada RepĂȘchage 2017/7

Tags: combinatorics, number theory



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$.