[Nub]

Hola, había visto conteo de relaciones sin usar la matriz asociada a la relación y vi un metodo o una forma de ver usándola. Este método lo vi para reflexivas pero no para simétricas y me gustaría ver si es correcto mi razonamiento.

Sea \( A=\{a_{1},a_{2},...,a_{n}\} \) , \( \left |{A}\right |=n \) hacemos la matriz asociada a la relación



Luego como en la diagonal principal, al ser simétrica no afecta en nada que tipo de entrada pueda tener, es decir pueden existir pares como por ejemplo (2,2) en la diagonal o no, y si existen colocaremos un 1 en la matriz en la posición fila 2 columna 2 y si no existe colocaremos un 0. Sabiendo esto para las n entradas de la diagonal principal, por cada entrada de estas n entradas tenemos 2 posibilidades, ser 1 o ser 0, entonces quedaría \( 2^n \) entradas posibles de la diagonal.

Ahora nos queda ver las posibilidades de la entradas restantes, es decir la triangular superior e inferior, como debe ser una relación simétrica cualquier entrada de la triangular superior al elegir una opción esta deberá ser la misma opción en su simétrico, es decir, si existe (1,2) y colocamos un 1 en la posición fila 1 columna 2, entonces debe existir el par (2,1) y en la posición fila 2 columna 1 debe haber un 1, entonces cada entrada de la triangular superior determina las de las entradas de la triangular inferior. Entonces tomando cualquier elemento de la triangular superior y su simétrico en la triangular inferior, ver cuantas opciones hay, por ejemplo tomo el elemento en la posición 3,4 y el 4,3 , entonces para el elemento 3,4 tenemos 2 posibilidades ser 0 o ser 1, si es 1 entonces en la posición 4,3 también debe ser 1, si es 0 lo mismo. Entonces como cada triangular tiene n2-n/2 elementos, usando regla del producto quedaría \( 2^{(n^2-n)/2} \) posibles entradas para una triangular y como los elementos de una triangular superior determinan los elementos de la triangular inferior, entonces ya no hay que elegir mas nada en la triangular inferior. Luego usando regla del producto \( 2^n*(n^2-n)/2 \)

Ahora un ejercicio visto aca en el foro.

Halle el número de relaciones \( R \) en el conjunto \( A = \{a, b, c, d\} \) que verifican simultáneamente las 3 condiciones siguientes: \( R \) es simétrica; \( (a,b)\in{ R} \); \( (c,c) \in{R} \).

Usando lo que dije con la matriz, aqui solo bastaría colocar un 1 en la posición fila a columna b y otro 1 en fila c columna c? entonces me quedaría la triangular \( (n^2-n)/2 - 2 \) elementos a elegir? ya que elegí colocar un dos 1 en fila c columna c y fila a columna b

Gracias

[Luis Fuentes]

Hola

Sea \( A=\{a_{1},a_{2},...,a_{n}\} \) , \( \left |{A}\right |=n \) hacemos la matriz asociada a la relación



Luego como en la diagonal principal, al ser simétrica no afecta en nada que tipo de entrada pueda tener, es decir pueden existir pares como por ejemplo (2,2) en la diagonal o no, y si existen colocaremos un 1 en la matriz en la posición fila 2 columna 2 y si no existe colocaremos un 0. Sabiendo esto para las n entradas de la diagonal principal, por cada entrada de estas n entradas tenemos 2 posibilidades, ser 1 o ser 0, entonces quedaría \( 2^n \) entradas posibles de la diagonal.

Ahora nos queda ver las posibilidades de la entradas restantes, es decir la triangular superior e inferior, como debe ser una relación simétrica cualquier entrada de la triangular superior al elegir una opción esta deberá ser la misma opción en su simétrico, es decir, si existe (1,2) y colocamos un 1 en la posición fila 1 columna 2, entonces debe existir el par (2,1) y en la posición fila 2 columna 1 debe haber un 1, entonces cada entrada de la triangular superior determina las de las entradas de la triangular inferior. Entonces tomando cualquier elemento de la triangular superior y su simétrico en la triangular inferior, ver cuantas opciones hay, por ejemplo tomo el elemento en la posición 3,4 y el 4,3 , entonces para el elemento 3,4 tenemos 2 posibilidades ser 0 o ser 1, si es 1 entonces en la posición 4,3 también debe ser 1, si es 0 lo mismo. Entonces como cada triangular tiene n2-n/2 elementos, usando regla del producto quedaría \( 2^{(n^2-n)/2} \) posibles entradas para una triangular y como los elementos de una triangular superior determinan los elementos de la triangular inferior, entonces ya no hay que elegir mas nada en la triangular inferior. Luego usando regla del producto \( 2^n*(n^2-n)/2 \)

La idea la tienes, pero mi impresión es que al final te lías combinando todo. La conclusión es que tanto los pares de la diagonal, como los de la parte triangular superior, cada uno de ellos puedes incluirlo o no (los de la triangular inferior con copia de los de la triangular superior). Entonces hay \( \dfrac{n^2-n}{2}+n=\dfrac{n^2+n}{2} \) elecciones posibles y así el número de relaciones es:

\( 2^{\frac{n^2+n}{2}} \).

Halle el número de relaciones \( R \) en el conjunto \( A = \{a, b, c, d\} \) que verifican simultáneamente las 3 condiciones siguientes: \( R \) es simétrica; \( (a,b)\in{ R} \); \( (c,c) \in{R} \).

Usando lo que dije con la matriz, aqui solo bastaría colocar un 1 en la posición fila a columna b y otro 1 en fila c columna c? entonces me quedaría la triangular \( (n^2-n)/2 - 2 \) elementos a elegir? ya que elegí colocar un dos 1 en fila c columna c y fila a columna b
[/quote]

Aquí más bien es \( \dfrac{n^2+n}{2}-2 \), con \( n=4 \), es decir lo mismo que con todas las simétricas pero hay dos posibilidades menos de elección porque los pares \( (c,c),(a,b) \) son obligados. Queda:

\( 2^{\frac{4^2+4}{2}-2} \)

Saludos.

[Nub]

Hola

Sea \( A=\{a_{1},a_{2},...,a_{n}\} \) , \( \left |{A}\right |=n \) hacemos la matriz asociada a la relación



Luego como en la diagonal principal, al ser simétrica no afecta en nada que tipo de entrada pueda tener, es decir pueden existir pares como por ejemplo (2,2) en la diagonal o no, y si existen colocaremos un 1 en la matriz en la posición fila 2 columna 2 y si no existe colocaremos un 0. Sabiendo esto para las n entradas de la diagonal principal, por cada entrada de estas n entradas tenemos 2 posibilidades, ser 1 o ser 0, entonces quedaría \( 2^n \) entradas posibles de la diagonal.

Ahora nos queda ver las posibilidades de la entradas restantes, es decir la triangular superior e inferior, como debe ser una relación simétrica cualquier entrada de la triangular superior al elegir una opción esta deberá ser la misma opción en su simétrico, es decir, si existe (1,2) y colocamos un 1 en la posición fila 1 columna 2, entonces debe existir el par (2,1) y en la posición fila 2 columna 1 debe haber un 1, entonces cada entrada de la triangular superior determina las de las entradas de la triangular inferior. Entonces tomando cualquier elemento de la triangular superior y su simétrico en la triangular inferior, ver cuantas opciones hay, por ejemplo tomo el elemento en la posición 3,4 y el 4,3 , entonces para el elemento 3,4 tenemos 2 posibilidades ser 0 o ser 1, si es 1 entonces en la posición 4,3 también debe ser 1, si es 0 lo mismo. Entonces como cada triangular tiene n2-n/2 elementos, usando regla del producto quedaría \( 2^{(n^2-n)/2} \) posibles entradas para una triangular y como los elementos de una triangular superior determinan los elementos de la triangular inferior, entonces ya no hay que elegir mas nada en la triangular inferior. Luego usando regla del producto \( 2^n*(n^2-n)/2 \)

La idea la tienes, pero mi impresión es que al final te lías combinando todo. La conclusión es que tanto los pares de la diagonal, como los de la parte triangular superior, cada uno de ellos puedes incluirlo o no (los de la triangular inferior con copia de los de la triangular superior). Entonces hay \( \dfrac{n^2-n}{2}+n=\dfrac{n^2+n}{2} \) elecciones posibles y así el número de relaciones es:

\( 2^{\frac{n^2+n}{2}} \).

No entiendo a que te refieres con "cada un de ellos puedes incluirlo o no"

[Nub]

Crees que estaría mal lo que yo hice al final con la regla del producto o da problemas? es decir tu dijiste

Entonces hay \( \dfrac{n^2-n}{2}+n=\dfrac{n^2+n}{2} \) elecciones posibles y así el número de relaciones es:
\( 2^{\frac{n^2+n}{2}} \).

Supongo que \( \dfrac{n^2-n}{2} \) elecciones de la triangular y mas las \( n \) de la diagonal.

Pero yo calcule primero la de la triangular y luego las de la diagonal y use regla del producto, pero al final da el mismo resultado y en el ejercicio me equivoque ya que falta tambien multiplicar por \( 2^n \) pero al final da el mismo resultado. La pregunta dará problemas hacer esto?

[Luis Fuentes]

Hola

No entiendo a que te refieres con "cada un de ellos puedes incluirlo o no"

Pues que cada par \( (a,a),(b,b) \) ó \( (a,b) \) ó \( (a,c) \) puede estar incluido o no en una posible relación de las que estamos buscando y por eso hay dos opciones por cada par y de ahí el "2 elevado al número de pares que pueden estar o no".

Es el razonamiento (o uno de los razonamientos) que se usan en general para probar que un conjunto de \( n \) elementos tiene \( 2^n \) subconjuntos.

Supongo que \( \dfrac{n^2-n}{2} \) elecciones de la triangular y mas las \( n \) de la diagonal.

Si.

Pero yo calcule primero la de la triangular y luego las de la diagonal y use regla del producto, pero al final da el mismo resultado y en el ejercicio me equivoque ya que falta tambien multiplicar por \( 2^n \) pero al final da el mismo resultado. La pregunta dará problemas hacer esto?

Si te refieres a

\( 2^n\cdot 2^{\frac{n^2-n}{2}} \)

 es correcto y si puedes usar la regla del producto. Pero es que tu habías escrito:

Luego usando regla del producto \( 2^n*(n^2-n)/2 \)

Saludos.

[Nub]

Pues que cada par \( (a,a),(b,b) \) ó \( (a,b) \) ó \( (a,c) \) puede estar incluido o no en una posible relación de las que estamos buscando y por eso hay dos opciones por cada par y de ahí el "2 elevado al número de pares que pueden estar o no".

Es el razonamiento (o uno de los razonamientos) que se usan en general para probar que un conjunto de \( n \) elementos tiene \( 2^n \) subconjuntos.

Ahh a eso te referías, ahora entiendo. Gracias Luis