How to determine the number of symmetric relations on a 7-element set that have exactly 4 ordered pairs?

Question

Let $A = \big \{1,2,3,4,5,6,7\big \}$. Find the number of symmetric relations on A, which contain exactly four ordered pairs ?

My approach : for a relation to be symmetric either pairs of type (i,i) should be present or both pairs (i,j) and (j,i) should be present. There are $n$ elements of type $(i,i)$ which can exist alone. and there are $\frac{n^2-n}{2}$ pairs of type $(i,j)$ and $(j,i)$, So, totally there are $n + \frac{n^2-n}{2} = \frac{n^2+n}{2}$ pairs, which evaluates to be $28$ for $n = 7$. So to form relations which contain only $4$ ordered pairs select $4$ from these in $\left(\begin{array}{c}28\\ 4\end{array}\right)$ ways.

What am i doing wrong?

Answer 1

You have:

4 different pairs with distinct numbers (i,j),(j,i),(k,l),(l,k) (out of the total of ${7\choose 2}=21$ pairs): ${21\choose 2}=210$

2 pairs with distinct elements and 2 pairs with same element (i,j),(j,i),(k,k),(l,l): ${7\choose 2}{7\choose 2}=441$

4 pairs with the same element (i,i),(j,j),(k,k),(l,l): ${7\choose 4}=35$

The total is 686

EDIT: At OP's request, here is a more systematic way of looking at the problem:

An element of your relation can come from one of the following two sources:

1. Choice of an unordered pair $\{i,j\}$, which gives you two elements of your relation, namely the ordered pairs $(i,j)$ and $(j,i)$ (to maintain symmetry). The number of unordered pairs to choose from is ${7\choose 2}=21$
2. A singleton $\{i\}$, which gives you only one element of your relation, namely $(i,i)$. The number of singletons to choose from is obviously $7$

One can get $4$ elements in the relation in one of the following three ways:

1. Choice of $2$ unordered pairs, $0$ singletons in ${21\choose2}{7\choose0}$ ways
2. Choice of $1$ unordered pair, $2$ singletons in ${21\choose1}{7\choose2}$ ways
3. Choice of $0$ unordered pairs, $4$ singletons in ${21\choose0}{7\choose4}$ ways

So the total is ${21\choose2}{7\choose0}+{21\choose1}{7\choose2}+{21\choose0}{7\choose4}=686$

The general formula for $n$ elements and $k$ ordered pairs is:

$$\sum_{i=0}^{\lfloor k/2\rfloor}{m\choose i}{n\choose k-2i}\text{, where }m={n\choose 2}$$

Answer 2

You can choose two pairs of pairs pairs $(i,j)$, $(j,i)$ with $i\ne j$ in $${{7\choose 2}\choose 2}={1\over2}\cdot21\cdot20=210$$ ways. Then you can choose one such pair of pairs plus two pairs of the form $(i,i)$ in ${7\choose2}\cdot{7\choose2}=441$ ways, and you can choose $4$ pairs of the form $(i,i)$ in ${7\choose4}=35$ ways. The total is $686$.