
\problemdata     
{S01-PS7-6}           
{counting}              
{} 		
{S01-PS7}
{S01 Karger}






\begin{problem}


On a set of $n$ elements how many of the following are there?

\ppart binary relations

\solution{

    $2^{n^2}$ since there are this many different $0-1$ matrices of order $n$.
}   
\ppart 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.
}

\ppart reflexive binary relations

\solution{
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}$.
}
\ppart 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} }$.}

\ppart symmetric or reflexive binary relations

\solution{
The number of
  symmetric or reflexive relations $=$ the number of reflexive
  relations $+$ the number of symmetric relations $-$ the number of
  reflexive and symmetric relations $= 2^{n^2 - n} + 2^{n+\binom{n}{2}} - 2^{\binom{n}{2}}$.
}
\end{problem}