MathDB
n girls, 2n-1 boys, dances with unknown, different ways

Source: Czech and Slovak Match 1998 P6

October 1, 2017
combinatorics

Problem Statement

In a summer camp there are nn girls D1,D2,...,DnD_1,D_2, ... ,D_n and 2n−12n-1 boys C1,C2,...,C2n−1C_1,C_2, ...,C_{2n-1}. The girl Di,i=1,2,...,n,D_i, i = 1,2,... ,n, knows only the boys C1,C2,...,C2i−1C_1,C_2, ... ,C_{2i-1}. Let A(n,r)A(n, r) be the number of different ways in which rr girls can dance with rr boys forming rr pairs, each girl with a boy she knows. Prove that A(n,r)=(nr)r!(n−r)!.A(n, r) = \binom{n}{r} \frac{r!}{(n-r)!}.
Back to ProblemsView on AoPS