Tengamos un alfabeto $A = \{a_1, a_2, \ldots, a_n\}$ avec $n$ elementos. Dos palabras cualesquiera $W_1$ y $W_2$ con longitud $n$ en este alfabeto que llamamos isomórfico si existe una permutación $P$ de símbolos alfabéticos tales que $W_1 = P(W_2)$ . ¿Puede demostrarse que el isomorfismo así definido es una relación de equivalencia? Si la respuesta a la pregunta anterior es "sí" dejemos que $Q$ sea el conjunto cociente de $A^n$ (conjunto de todas las palabras de longitud $n$ ) de esta relación. Cómo expresar el número de elementos de $Q$ para cualquier $n$ ?
Respuestas
¿Demasiados anuncios?
Como dijo Oria, la relación es una relación de equivalencia, pero el número de elementos en el cociente $Q$ es el número de particiones del configure $\{1,2,3,\dots,n\}$ que se denomina número de Bell (véase https://en.wikipedia.org/wiki/Partition_of_a_set )
Oria Gruber
Puntos
4889
La respuesta es sí.
Cada palabra puede permutarse a sí misma con la permutación de identidad. Toda permutación es invertible, por lo que si $W_1 = P(W_2)$ existe otra permutación $P'$ tal que $P'(W_1) = W_2$ . si $W_1$ puede permutarse en $W_2$ por permutación $P$ y $W_2$ puede permutarse en $W_3$ por permutación $P'$ entonces $P'(P(W_1)) = W_3$ .
Se trata, pues, de una relación de equivalencia.
En cuanto a las clases de equivalencia:
Dos palabras son equivalentes si se pueden permutar entre sí o, para decirlo mejor, si contienen las mismas letras.
Por ejemplo $n=2$ y $A = \{a,b\}$ entonces las clases son $\overline{[aa]} = \{aa\}$ , $\overline{[bb]} = \{bb\}$ , $\overline{[ab]} = \{ab,ba\}$ .
Así que, en realidad, el número de clases de equivalencia (o número de elementos en $Q$ ) es la respuesta a la pregunta "¿cuántas palabras de longitud $n$ podemos crear a partir del alfabeto $A$ con repetición (podemos usar una letra más de una vez) y sin orden (ab = ba))". La respuesta a esta pregunta es $\binom{n + |A| -1}{n}$
