Number of subsets of a nonempty finite set with a given property. Let $S$ be a set with $|S|=n$, where $n$ is a positive integer. How many subsets $B$ of $S\times S$ are there with the property that $(a,a) \in B$ for all $a \in S$ and $(a,b) \in B \implies (b,a) \in B$ for all $a,b \in S$.
So, this is the question I am having a tough time finding a solution for. I was able to do the first part but I couldn't do the second part. Can anyone help me with this?

There are $\binom{n}{2}$ ways to choose $2$ (distinct) numbers $a$ and $b$ in $S$. (Note that this is the number of "hands" of $2$, and not a set of ordered pairs.) 
For any such distinct numbers $a$ and $b$ we can say Yes if $(a,b)$ and therefore $(b,a)$ will be in our set, and No if $(a,b)$, and therefore $(b,a)$, will not be in our set. So we have $2^{\binom{n}{2}}$ choices. 
If you prefer, you can write this as $2^{n(n-1)/2}$.
Remark: What we have just counted is the number of relations on the set $S$ that are reflexive and symmetric. 
