\problemdata
{counting}
{relations}
{f01 ps9}
{s00 ps7}

\begin{problem}
On a set of $n$ elements how many of the following are there:

\begin{problemparts}

\problempart binary relations? 

\solution{$2^{n^2}$ since there are this many
  different 0-1-matrices of order $n$.}

\problempart symmetric binary relations?
 
\solution{The matrix associated with
  a symmetric relation is symmetric.  Since there are
\[
2^{n+\binom{n}{2}}
\]
  different symmetric matrices there are an equal number of symmetric
  relations.}

\problempart reflexive binary relations?
 
\solutionn{The matrix associated with a
  reflexive relation has $1$'s along the main diagonal . Hence the
  number of such matrices, and therefore reflexive relations, is
\[
2^{n^2 - n}.
\]}

\problempart symmetric and reflexive binary relations? 

\solution{The matrix
  associated with a symmetric and reflexive relation is symmetric and
  has $1$'s along the main diagonal.  Hence the number of such
  relations is
\[
2^{\binom{n}{2} }.
\]}

\problempart symmetric or reflexive binary relations?

\solution{The number of symmetric or reflexive relations equals the
number of reflexive relations plus the number of symmetric relations,
minus the number of reflexive and symmetric relations:
\[
2^{n^2 - n} + 2^{n+\binom{n}{2}} - 2^{\binom{n}{2}}.
\]
}

\end{problemparts}
\end{problem}
