\problemdata
{basic combinatorics}
{s00 ps7}
{s95 ps7}

%source: spring00 ps7-5
% source: spring95, ps7
% topic: basic combinatorics
\begin{problem}
\begin{problemparts}
\problempart How many ways can $2n$ people be divided into $n$ pairs?

\solution{
\[
\frac{(2n)!}{n! 2^n}.
\]

Consider all the ways of ordering the $2n$ people 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 persons, group the third
and fourth persons,..., group the $(2n-1)$th and $2n$th persons. 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$ people can be divided into
$n$ pairs is $ (2n)!/ n! 2^n$.

\iffalse
First we pick $n$ leaders from the $2n$ people. 
There are $\binom{2n}{n}$ ways to do this. 
Then we pair the remaining $n$ people with the $n$ leaders. That gives
us $n!$ different ways for each choice of leaders. However,
$\binom{2n}{n}n!$ will be overcounting, since for any fixed pairing,
we count each pair twice depending on who is the leader.
 So for any valid pairing, we counted it $2^n$ times.
Therefore, the answer should be
 $\displaystyle \binom{2n}{n} n! /2^n$.

\fi
}

\problempart How many ways can you choose $n$ out of $2n$ objects, given that
$n$ of the $2n $ objects are identical?

\solution{
The answer is $2^n$, since you can pick any subset from the $n$
nonidentical objects, and make up the rest with the identical ones. And the
number of subsets of $n$ different objects is $2^n$. 
}

\end{problemparts}
\fi
\end{problem}