Question

Seja A = {1, 2, ... , n} um conjunto, com n ∈ ℕ. Uma relação binária R ⊆ A × A é dita simétrica se para todo a, b ∈ A,

     se (a, b) ∈ R, então (b, a) ∈ R.

Calcule a quantidade de relações simétricas que existem sobre A.

Obs.: Considere a relação vazia como simétrica.

─────

Gabarito: $2^{n(n+1)/2}.$​

Answer 1

Seja $E_1$ um conjunto somente com pares de números em que $a=b$. Portanto $E_1$ possui $n$ elementos. Seja $E_2$ um conjunto somente com os pares $(a, b)$, descartando $(b, a)$, com $a \neq b$. Este conjunto tem:

$C_{n,2} = \cfrac{n!}{(n-2)!2!} = \cfrac{n(n-1)(n-2)!}{2(n-2)!} = \cfrac{n(n-1)}{2}$ elementos.

Logo, a quantidade de conjuntos $R$ que possuem somente elementos simétricos corresponde ao agrupamento dos elementos de $E_1$ e $E_2$, em qualquer quantidade.

$\#(E_1 \cup E_2) \\= n + \cfrac{n(n - 1)}{2} \\\\= \cfrac{2n + n(n - 1)}{2}\\\\= \cfrac{2n + n^2 - n}{2} \\\\= \cfrac{n^2 + n}{2}\\\\= \cfrac{n(n+1)}{2}$

(total de elementos)

Posso escolher o elemento ou não escolhê-lo, portanto 1 escolha de 2 possibilidades, e esta escolha sendo tomada para cada um de todos os elementos ($E_1 \cup E_2$).

$\underbrace{2 \cdot 2 \cdot ... \cdot 2} _{\frac{n(n+1)}{2}\mathrm{vezes}} = 2^{\frac{n(n+1)}{2}}$