Solution: 2017 Winter Final - 2

Author: Michiel Smid

Question

Let $n \geq 2$ be an integer. Consider permutations $a_1,a_2,\dots,a_n$ of the set $\{1,2,\dots,n\}$ for which $a_1 < a_2$. How many such permutations are there?

(a)

$2{n \choose 2} \cdot (n-2)!$

(b)

$\frac{n!}{2}$

(c)

$n!$

(d)

None of the above.

Solution

Well, let’s break it down

We choose 2 numbers out of the n numbers: $ \binom{n}{2} $

The other n-2 numbers can be placed in any order: $ (n-2)! $

$ \binom{n}{2} \cdot (n-2)! $

$ = \frac{n!}{2! \cdot (n-2)!} \cdot (n-2)! $

$ = \frac{n!}{2!} $