MathDB

Ordered subsets of [n]

Source: Canada Repêchage 2017/7

April 13, 2017

combinatoricsnumber theory

Problem Statement

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