\problemdata                                                             
        {counting-23} % latex-friendly label for the prob.
        {Counting; Product Rule; Relations} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S02 cp7W; F00 PS8} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}
On a set of $n$ elements how many of the following are there?

\begin{problemparts}
\problempart binary relations

\solution{$2^{n^2}$. We look at the matrix that corresponds to the relations such the element of the 
$n \times n$ matrix is 1 if the corresponding pair is in the relation and it is 0 otherwise.
 There are $2^{n^2}$ many different possible
boolean ($0-1$) $n \times n$ matrices. Another way of reasoning about
this is to say that there are $n^2$ possible ordered pairs, and any
subset of those pairs is a possible relation. If $A$ is the set of all
pairs, then all possible relations are just all possible subsets of
$A$, and we know that $P(A) = 2^{|A|} = 2^{n^2}$.}

\problempart symmetric binary relations

\solution{ In a symmetric binary relation, if (a,b) is in R, then (b,a) is in R.
The matrix associated with a symmetric relation is
symmetric (the entries in the triangle above the diagonal is the same
as the entries in the triangle below the diagonal). 
The total number of entries are $n^2$.  The number of entries on the diagonal is $n$ and the 
number of entries on the upper side of the diagonal is $(n^2-n)/2$.
Therefore there
are $\frac{n(n+1)}{2}$ entries that can be set. Hence there are
$2^{\frac{n(n+1)}{2}}$ different symmetric matrices / symmetric
relations.}

\problempart reflexive binary relations 

\solution{In a reflesive binary relations, (a,a) is in R for all a.
The matrix associated with a reflexive relation has $1$'s
along the main diagonal, so those entries are fixed. Hence the number
of entries that can be set is $n^2 - n$.  The number of matrixes is $2^{n^2 -
n}$. Therefore the number of reflexive binary relations is $2^{n^2 -
n}$. 
Note that using this idea you could count the number of relations
that are not reflexive, by just substracting the number of reflexive
relations from the total number of relations.}

\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. The total number of entries
is $n^2$ and there are $\frac{n^2-n}{2}$ that are on the upper side of the diagonal.
Hence the
number of such relations is $2^{\frac{n(n-1)}{2}}$.}

\problempart 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.}

\problempart Count the number of undirected graphs with $n$ nodes,
where every node has a self-loop, by showing that there is a
one-to-one mapping (bijection) with one of the types of relations in
parts (a-e). Prove that your mapping is a bijection.

\solution{
There is a one-to-one relationship between the set of 
undirected graphs with nodes $\set{1,\dots,n}$, where every node has a
 self-loop, to the set of symmetric and reflexive binary 
relations.  To show the one to one relationship, 
we define a bijective function $f$ as follows:  for any 
undirected graph (with self loops at each node) $G$, 
$f$ maps to the symmetric and reflexive 
binary relation that contains $(a,b)$ if and only if there 
is a directed edge $(a,b)$ in $G$. 

First we show that $f$ is one-to-one.  For any two distinct undirected graphs 
(with self loops at each node) $G_1$ and $G_2$, there must exists 
an edge in $G_1$ that does not exist in $G_2$ or there must exists 
an edge in $G_2$ that does not exist in $G_1$, thus $f(G_1)$ is 
not equal to $f(G_2)$.  
Now we show that $f$ is onto.  For any symmetric reflexive relation 
$R$, there exists an undirected graph (with self loop at each node) 
$G$ such that $f(G) = R$.  This is because  
graph $G$ can always be constructed such that edge from $a$ to $b$ 
exists if and only if $(a,b)$ is in $R$.
Thus $f$ is indeed a bijection.

The number of undirected graphs with nodes $\set{1,\dots,n}$, where every node has a self-loop, is 
$2^{\frac{n(n-1)}{2}}$.
}

\end{problemparts}
\end{problem}

                                 