Number of symmetric relations with $k$ pairs

Question

I need to get number of symmetric relations on set $A$, where $|A| = n$ elements and $|R| = k$ pairs

I know how to get number of all symmetric relations - $2^\frac{n(n+1)}{2}$, but this cover all relations with all possible $|R|$

Answer 1

It sounds like you already know that the total number of individual symmetric relations is $m:= \frac 12n(n+1)$, so to find to find relations with $|R|= k$ you just need to pick $k$ of the possible $m$, that is: ${m \choose k}$. Note that, as required, $\sum_{k=0}^m {m \choose k} = 2^m$