Número de relaciones en un conjunto con n elementos

Question

Dejemos que $A$ sea un conjunto con $n$ elementos.

¿Cuántas relaciones (1)simétricas, (2)antisimétricas y (3)asimétricas hay en $A$ ?

(4)¿Cuántas relaciones lineales hay?

Esto es lo que hice:

1. En el caso de la simetría, para cada $n$ hay $n$ opciones, multiplicarlas todas y eliminar todos los duplicados obtendremos $n^n-n$

2. Para los antisimétricos, sólo puede haber relaciones de un tipo: $(x,x)$ por lo que obtendremos $n$ relaciones.

3. En el caso de la asimetría, empiezo a tener problemas porque para cada relación hay menos relaciones posibles. Creo que hay $(n-1)+(n-2)+...+(n-n+1)+(n-n)$ relaciones.

4. Sobre las relaciones lineales, creo que es $n^n$ .

¿Es correcto?

Gracias.

Answer 1

1. Relaciones simétricas: hay que decidir si los miembros de la pareja $(x,y)$ están en relación. Hay $\binom{n}{2} + n$ tales parejas, hasta el orden. Así que hay $2^{\binom{n}{2} + n}$ relaciones simétricas.

2. Relaciones antisimétricas: Se puede decidir si $x$ está en relación consigo mismo para cualquier $x$ que da $2^n$ opciones. Entonces para cualquier pareja $(x,y)$ con $x \neq y$ Tienes que decidir si $x \mathcal{R} y$ o $y \mathcal{R} x$ o no hay relación entre $x$ y $y$ . Esto da $3$ posibilidades la $\binom{n}{2}$ tales parejas. El total de las relaciones antisimétricas es, por lo tanto $2^n \times 3^{\binom{n}{2}}$ .

3. Relaciones asimétricas: Esta vez, $x$ no puede estar en relación consigo mismo. Entonces, tiene las mismas opciones que las anteriores; así que hay $3^{\binom{n}{2}}$ relaciones asimétricas

4. Relaciones lineales: sólo tienes que decidir cuál de tus elementos es el más pequeño, luego decidir el más pequeño entre los elementos restantes... Se obtiene $n!$ estas relaciones

Espero no equivocarme.