PUERTA | Maqueta de puerta 2017 | Pregunta 39

¿Cuántas relaciones antisimétricas hay en un conjunto de n elementos?
(A) 2 ⁿ .3 ^n(n-1)/2
(B) 2 ⁿ
(C) n ²
(D) n

Respuesta: (A)
Explicación: Cualquier subconjunto de pares diagonales es una relación antisimétrica. En una relación antisimétrica cada par diagonal puede aparecer de 2 formas. En relación antisimétrica cada combinación no diagonal puede presentarse de 3 formas.
Por regla del producto,
Número de relaciones antisimétricas posibles en A = 2^n. 3^(n(n-1)/2).

Explicación alternativa –

Relación antisimétrica: Si R(a,b) y R(b,a) entonces a=b
Considere todos los pares de elementos (llamemos a los elementos a,b) entre n elementos tales que a!=b.
En a,b podemos formar 2 relaciones (es decir, R(a,b) o R(b,a)). Podemos mantener uno de ellos o ninguno de ellos, pero no ambos. Entonces, tenemos 3 opciones. Número total de tales pares a,b = C(n,2) = n*(n-1)/2. Entonces, el total de opciones hasta ahora = 3^(n(n-1)/2).
Considerando los pares de elementos donde a=b, podemos mantenerlos o descartarlos. Hay n de esos pares, por lo que el total de opciones = 2^n.
Entonces, opciones totales = 2^n. 3^(n(n-1)/2).

Cuestionario de esta pregunta