CAPS 1998 Problem 6

In a summer camp there are $n$ girls $D_1,D_2, ... ,D_n$ and $2n-1$ boys $C_1,C_2, ...,C_{2n-1}$ . The girl $D_i, i = 1,2,... ,n,$ knows only the boys $C_1,C_2, ... ,C_{2i-1}$ . Let $A(n, r)$ be the number of different ways in which $r$ girls can dance with $r$ boys forming $r$ pairs, each girl with a boy she knows. Prove that $A(n, r) = \binom{n}{r} \frac{r!}{(n-r)!}.$