\problemdata      
        {?} % latex-friendly label for the prob.
        {Counting} % The topic(s) of the problem content.
        {?} % Source (if known)
        {Fall 2001, quiz 3} % Usage (list ones you are aware of).
        {Christos Kapoutsis, S02} % Last revision info (author, date).



\begin{problem}
\bparts

\ppart
Write closed form formulas which may involve factorials and
binomial coefficients for the following four functions:
\begin{itemize}

\item $G(n)\eqdef $ the number of directed simple graphs with vertices
$\set{ 1, 2, \dots, n }$ (self-loops permitted).

\brule{1in}
\solution{$2^{n^2}$.  There are $n^2$ possible directed edges, each of
which may or may not be in a graph.}

\item $U(n) \eqdef$ the number of undirected simple graphs with vertices
$\set{ 1, 2, \dots, n }$ (self-loops NOT permitted).

\brule{1in}
\solution{$2^{\binom{n}{2}}$.  There are $\dbinom{n}{2}$ possible
undirected edges between distinct vertices, and each edge may or may not
be in a graph.}

\item $M(n) \eqdef$ the number of mappings from $\set{ 1, 2, \dots, n
}$ to $\set{ 1, 2, \dots, 2n }$.

\brule{1in} \solution{$(2n)^n$.  For each of the $n$ arguments of a
mapping, there are $2n$ possible values.
  
  Note: We used the word ``mapping'' to mean a \emph{function} from one
  set to another, \ie an assignment of exactly one element of the first
  set, $\set{1,\dots,n}$, to an element of the second set.  However, some
  of you took mapping to mean any relation between the two sets.  In this
  case, the number of relations between $\set{ 1, 2, \dots, n }$ and
  $\set{ 1, 2, \dots, 2n }$ is $(2^{2n})^n = 2^{2n^2}$; we awarded full
  credit for this answer also.}

\item $B(n) \eqdef$ the number of \emph{injections} from $\set{ 1, 2,
\dots, n }$ to $\set{ 1, 2, \dots, 2n }$.

\brule{1in} \solution{$P(2n,n) = \cfrac{2n!}{n!}$.}

\end{itemize}

\ppart Order the functions $G,U,M,B$ above so that each function is O() of
the next function.  Also indicate whether the $\Theta()$ relationship
holds between each successive pair of functions.  No proofs are required.


\solution{The order is $B, M, U, G$, and each is o() of the next, and
therefore is O() but not $\Theta()$ of the next.

\[
B(n) = \frac{2n!}{n!} \sim \frac{\sqrt{2\pi 2n}(\frac{2n}{e})^{2n}}{\sqrt{2\pi
n}(\frac{n}{e})^n} = \sqrt{2} \frac{(2n)^{2n}}{(en)^n} = \sqrt{2}
(\frac{4}{e})^n n^n = o(2^n) n^n = o((2n)^n).
\]

Note that Stirling's formula is not really needed here, since we can
also reason in a simple way as follows:
\begin{eqnarray*}
\frac{2n!}{n!} &  =  & 2n(2n-1)\cdots\ceil{(3/2)n}(\ceil{(3/2)}n-1)\cdots
(n+1)\\
& \le & (2n)^{\floor{n/2}}((3/2)n)^{\ceil{n/2}}\\
& = & (2n)^{n/2}\cdot o((2n)^{n/2})\\
& = & o((2n)^n).
\end{eqnarray*}
\[
M(n) = (2n)^n = 2^n n^n = 2^n2^{n\log n}=2^{n(1+\log n)} = 2^{o(n^2)} =
o(2^{\binom{n}{2}}).
\]
\[
U(n) = 2^{\binom{n}{2}} \le 2^{n^2/2} = (\sqrt{2})^{n^2} = o(2^{n^2}),
\]
so
\[
U(n) = o(G(n)).
\]

In grading this part of the problem, we only considered your answers from
part (a).  So if you answered part (a) with incorrect formulas but were
still able to order these formulas correctly, you were awarded full credit
for part (b).  Conversely, if your answer to (b) was inconsistent with
your answer to (a), you did not receive credit even if you happened to
come up with the ``correct'' sequence $B, M, U, G$.

If you took ``mapping'' to mean ``relation'' as described in the part
(a) solution for $M(n)$, then the correct order is $B, U, G, M$.  
}

\eparts
\end{problem}
