\problemdata                                                             
        {Lining up students} % latex-friendly label for the prob.
        {Counting, Asymptotics} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Tutorial 8, 2} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
In how many ways can $2n$ students be divided into $n$ pairs?
Investigate the asymptotic behavior of your answer.

\solution{

\textbf{Solution:}\\


$\displaystyle \frac{(2n)!}{n! 2^n} = 
\sqrt{2}\left(\frac{2n}{e}\right)^n(1 + o(1))$

Consider all the ways of ordering the $2n$ students in a line. There are
$(2n)!$ ways of doing this. Now group them into pairs based on the
linear order, i.e. group the first and second students, group the third
and fourth students, \ldots, group the $(2n-1)$th and $2n$th students. Thus
each linear order gives us a unique grouping into pairs. But observe
that two different linear orders could give rise to the same grouping
into pairs. So let us now count the number of linear orders that give
rise to the same grouping into pairs. Given a grouping into pairs, to
generate a linear order we need to order each pair (there are $2^n$
ways to do this) and then order the $n$ pairs (there are $n!$ ways to
do this). Hence $n! 2^n$ linear orders give the same grouping into
pairs. Thus the total number of ways $2n$ students can be divided into
$n$ pairs is $\frac{(2n)!}{n! 2^n}$.
Using Stirling's formula on this expression gives
\begin{displaymath}
  \frac{(2n)!}{n! 2^n}
  = 
  \frac{(2n)^{2n} e^{-2n}\sqrt{4\pi n} (1 + o(1))}
  {n^n e^{-n}\sqrt{2\pi n} (1 + o(1)) 2^{n}}
  =
  \sqrt{2}\left(\frac{2n}{e}\right)^n(1 + o(1)).
\end{displaymath}


}

\end{problem}

