Aclaración sobre uno de los problemas de Stanley sobre los números catalanes

Tengo una duda sobre el enunciado del problema (aa) en la lista de problemas de números catalanes de Stanley (ver aquí ), en la que enumera 66 conjuntos cuyos elementos se cuentan por el norte número catalán C norte .

La declaración parece ser imprecisa o incompleta. Lo estoy copiando aquí para facilitar la referencia:

[Consideramos] clases de equivalencia B de palabras en el alfabeto [ norte − 1 ] tal que tres letras consecutivas cualesquiera de cualquier palabra en B son distintos, bajo la relación de equivalencia tu i j v ∼ tu j i v para cualquier palabra, tu , v y cualquiera i , j ∈ [ norte − 1 ] satisfactorio | i − j | ≥ 2 . Para norte = 3 , las clases de equivalencia son { ∅ }, {1}, {2}, {12}, {21}. Para norte = 4 un representante de cada clase viene dado por ∅ , 1, 2, 3, 12, 21, 13, 23, 32, 123, 132, 213, 321, 2132.

Ahora, aunque esto no se dice, estamos claramente interesados ​​en la relación de equivalencia más pequeña que contiene esos pares ordenados. Además, parece que solo estamos considerando palabras de longitud máxima. norte . Incluso teniendo en cuenta esto, todavía no me queda claro por qué para norte = 4 solo tenemos una clase de equivalencia para palabras de longitud 4 . Por ejemplo, ¿por qué, además de [ 2132 ] , ¿no tenemos también las cuatro clases de equivalencia distintas por pares? [ 1231 ] , [ 1321 ] , [ 3123 ] , [ 3213 ] ?

Por ejemplo, consideremos [ 1231 ] . Entonces 1231 no es equivalente a 1321 , ya que solo estamos considerando permutaciones de pares i j con | i − j | ≥ 2 . En particular, parece que 1231 no es equivalente a ninguna otra palabra tal que tres letras consecutivas cualesquiera sean todas distintas.

Tenga en cuenta que no estoy pidiendo una solución al problema de conteo, sino simplemente tratando de entender la declaración. Dado que estos problemas son bastante conocidos y se usan en muchas clases de combinatoria, estoy un poco sorprendido por el hecho de que la afirmación parezca tan imprecisa.

Probablemente quiera evitar ser equivalente a un arreglo inválido. es decir, 1231 ∼ 1213 , 1321 ∼ 3121 , 3123 ∼ 1321 y 3213 ∼ 3231
No hay imprecisión. La relación de equivalencia se define explícitamente y se establece explícitamente que todos los miembros de una clase de equivalencia B debe satisfacer la restricción de que tres letras consecutivas sean distintas.
@BrianM.Scott No estoy de acuerdo contigo. ¿Cuál es el conjunto sobre el que se define la relación de equivalencia? De la declaración parece ser el conjunto de todas las palabras en el alfabeto [ norte − 1 ] de modo que tres letras consecutivas sean distintas. Por supuesto, se puede definir una relación de equivalencia en el conjunto de todas las palabras del alfabeto [ norte − 1 ] y, además, definir cualquier palabra que tenga tres entradas consecutivas con repeticiones para que sea equivalente a la palabra vacía. Así debería haberse formulado el problema.
@no: Está perfectamente claro que la relación de equivalencia se define en el conjunto de palabras sobre [ norte − 1 ] , pero que estamos considerando solo aquellas clases de equivalencia B tal que tres letras consecutivas cualesquiera de cualquier palabra en B son distintos. No hay necesidad de pasar por contorsiones para definir alguna otra relación de equivalencia.
Es perfectamente gramatical interpretar "palabras en el alfabeto [ norte − 1 ] tal que tres letras consecutivas cualesquiera de cualquier palabra en B son distintos" como un sintagma nominal, en cuyo caso estamos considerando la relación de equivalencia sobre un subconjunto de todas las palabras del alfabeto [ norte − 1 ].
Sin embargo, si aislamos el sintagma nominal "clases de equivalencia B de palabras en el alfabeto [ norte − 1 ] ", que luego modificamos por "tal que tres letras consecutivas cualesquiera de cualquier palabra en B son distintas" obtenemos la interpretación que pretendía Stanley, en cuyo caso, como señala Will, desaparece la dificultad relativa a la longitud de las palabras.
@BrianM.Scott, como explica Adrian Clough, hay dos lecturas posibles de la declaración, que son perfectamente válidas. Por lo tanto, escribir "está perfectamente claro" no solo es descortés, es falso. Esta es la primera vez que escribo una pregunta en Math.SE; Escribí esta pregunta junto con un estudiante para mostrarles cómo escribir preguntas en los sitios de SE, pero son comentarios como el suyo los que me hacen pensar dos veces antes de recomendar este sitio a los estudiantes en el futuro, ya que son engañosos y un estudiante podría no tener suficiente experiencia para entender eso.
@no: no estoy de acuerdo con el análisis de Adrian.
@BrianM.Scott bien, ¿quieres explicar por qué?
La dificultad que veo con la primera interpretación de Adrian es que B está fuera del alcance de esa lectura. La frase "de cualquier palabra en B " no tiene cabida en una cláusula de relativo que modifica el sintagma nominal "palabras en el alfabeto [ norte − 1 ] pero es perfectamente sensato en una cláusula de relativo que modifica el sintagma nominal "clases de equivalencia B de palabras en el alfabeto [ norte − 1 ] ". Estoy de acuerdo en que este pasaje de Stanley no es fácil de leer; no lo capté las primeras veces. Hubiera preferido ver la relación de equivalencia definida primero, en una oración separada.
Ah, este es un buen punto! Simplemente demuestra que gramatical no implica significativo (-:

Respuestas (1)

Creo que si alguna palabra en la clase de equivalencia es una palabra inválida, entonces todas las palabras en la clase de equivalencia son inválidas. Entonces 1231 no es válido ya que es equivalente a 1213, que no es válido. Para norte = 4 no puedes tener una palabra de longitud 5 o mayor. Esta no es una suposición adicional, sino que se deriva de la restricción. Para ver esto, tenga en cuenta que las tres letras del medio en una palabra de cinco letras no pueden ser todas 2s. Cualquier 3 en el interior de la palabra debe estar precedido o seguido por un 1. Asimismo, cualquier 1 debe estar precedido o seguido por un 3. En cualquier caso, las letras que lo rodean deben ser 2, dando 2132 o 2312 (que son equivalente). Cualquier letra que preceda o siga a esta palabra debe ser un 1 o un 3, pero ambos son imposibles.

Gracias por esta respuesta. Como comento en mi comentario anterior, uno debería haber formulado el problema definiendo una relación de equivalencia en el conjunto de todas las palabras del alfabeto [ 𝑛 − 1 ] , y además definiendo cualquier palabra que tenga tres entradas consecutivas con repeticiones para que sea equivalente a la palabra vacía. Entonces claramente uno no puede tener palabras con una longitud mayor que 5 para norte = 4 .
Mi lectura de Stanley, que creo que está de acuerdo con la de Brian Scott, es que uno primero considera todas las clases de equivalencia de palabras bajo la relación de equivalencia de Stanley y luego forma un conjunto seleccionando esas clases de equivalencia en las que tres letras consecutivas, en cualquier palabra en el clase de equivalencia, son distintos. No estoy seguro de que sea obvio sin comprobar que no se pueden tener palabras de más de 4 cuando norte = 4 , pero la verificación realizada en mi respuesta parece ser suficiente para mostrar esto. Para norte = 5 tenga en cuenta que puede tener palabras de longitud 6 (como 231423 ) pero no de longitud 7 o más.
Sí, no quise decir que sea obvio, pero me queda claro por qué en ese caso uno no tiene palabras de mayor longitud que 4 . Mi problema estaba en la configuración del problema, que todavía creo que debe abordarse. Como escribes correctamente, la tuya es una lectura, la mía fue otra lectura posible. De la misma manera que no debo leer una prueba de un teorema para entender lo que dice el teorema, no debo basarme en ejemplos para entender lo que pide un problema, especialmente en un libro de texto que se usa tanto.
Aclaración sobre uno de los problemas de Stanley sobre los números catalanes
RespuestasAquíPolítica de privacidad1y, 0v