Problema de combinatoria relacionado con los números de Motzkin con premio I

Question

Aquí un problema de combinatoria. Ofrezco 30 euros por una prueba y 100 puntos de recompensa por un contraejemplo: Sea $n \geq 2$ .

Un $n$ - Serie Kupisch es una lista de $n$ números $c:=[c_1,c_2,...,c_n]$ con $c_n=1$ , $c_i \ge 2$ para $i \neq n$ y $c_i-1 \leq c_{i+1}$ para todos $i=1,...,n-1$ y el ajuste $c_0:=c_n$ . El número de estos $n$ -La serie de Kupisch es igual a $C_{n-1}$ (números catalanes). El Serie CoKupisch $d$ de $c$ se define como $d=[d_1,d_2,...,d_n]$ con $d_i:= \min \{k | k \geq c_{i-k} \} $ y $d_1=1$ . Se puede demostrar que el $d_i$ son una permutación de los $c_i$ . Un número $a \in \{1,...,n \}$ es un descenso si $a=1$ o $c_a >c_{a-1}$ . Definir un conjunto correspondiente, indexado por descensos: $X_1 := \{1,2,...,c_1-1 \}$ y $X_a := \{ c_{a-1}, c_{a-1}+1 ,..., c_a -1 \}$ para los descensos $a > 1$ .

A $n$ -La serie Kupisch se llama $2-$ Gorenstein si satisface la siguiente condición:

para cada descenso $a$ y cada $b \in X_a$ : o bien $c_{a+b} \geq c_{a+b-1}$ o $d_{a+b-1} = d_{a+b + c_{a+b}-1} - c_{a+b}$ se satisface.

Conjetura: El número de $n$ -Serie Kupisch que son $2$ -Gorenstein para $n \geq 2$ es igual a 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, ... que son los números Motzin. https://oeis.org/A001006

Mi ordenador dice que es cierto para $n=2,3,...,14$ . (también para n=1 si [1] es la única serie de 1-Kupisch, por una interpretación teórica de la representación)

Aquí un ejemplo que visualiza las secuencias c y d en una imagen de un camino de Dyck: https://drive.google.com/file/d/0B9hKtvQe-4-bQlpjcURfYnNzUGs/view

Antecedentes: Esto tiene un fondo de teoría de la representación (ver http://www.sciencedirect.com/science/article/pii/0022404994900442 )y daría un cierto resultado de clasificación junto con una nueva categorización de los números de Motzkin. Hay una biyección muy natural de las series de n-Kupisch a los caminos de Dyck desde (0,0) a (2n-2,0) y probablemente las álgebras de 2-Gorenstein entre ellas podrían dar una nueva interpretación combinatoria de los caminos de Motzkin como subcaminos de los caminos de Dyck.

Encontré de hecho muchas cosas de este tipo y las traduje en problemas elementales, pero no tengo talento en combinatorias complicadas :(

ejemplo para n=5:

Todas las series 5-Kupisch (el número es 14): [ [ 2, 2, 2, 2, 1 ], [ 3, 2, 2, 2, 1 ], [ 2, 3, 2, 2, 1 ], [ 3, 3, 2, 2, 1 ], [ 4, 3, 2, 2, 1 ], [ 2, 2, 3, 2, 1 ], [ 3, 2, 3, 2, 1 ], [ 2, 3, 3, 2, 1 ], [ 3, 3, 3, 2, 1 ], [ 4, 3, 3, 2, 1 ], [ 2, 4, 3, 2, 1 ], [ 3, 4, 3, 2, 1 ], [ 4, 4, 3, 2, 1 ], [ 5, 4, 3, 2, 1 ] ]

Todas las series 2-Gorenstein 5-Kupisch (el número es 9): [ [ 2, 2, 2, 2, 1 ], [ 3, 2, 2, 2, 1 ], [ 2, 3, 2, 2, 1 ], [ 4, 3, 2, 2, 1 ], [ 2, 2, 3, 2, 1 ], [ 3, 2, 3, 2, 1 ], [ 3, 3, 3, 2, 1 ], [ 2, 4, 3, 2, 1 ], [ 5, 4, 3, 2, 1 ] ]

Conjetura/antecedentes de la teoría de la representación:

Conjetura:

El número de álgebras de 2-Gorenstein que son álgebras de Nakayama con n módulos simples con una línea lineal orientada como carcaj es igual a la secuencia de números de Motzkin.

Antecedentes/explicaciones:

Aquí el $c_i$ son la dimensión de los módulos proyectivos indescomponibles que determinan el álgebra de forma única (suponiendo que las álgebras son álgebras quiver conectadas sobre un campo). La página $d_i$ son la dimensión de los módulos inyectivos indecomponibles en el punto $i$ . 2-Gorenstein significa que el dual del módulo regular $D(A)$ tiene una presentación proyectiva $P_1 \rightarrow P_0 \rightarrow D(A) \rightarrow 0$ con $P_1$ que tiene una dimensión inyectiva limitada por 1. ( $P_0$ es siempre proyectiva-inyectiva para las álgebras de Nakayama)

Aquí un enlace para el programa que utilicé para probar las cosas (copiar todos los programas, y el programa finaltest hace el trabajo entonces. 1 significa que la serie de Kupisch es 2-Gorenstein y 0 significa que no lo es): https://docs.google.com/document/d/1U9mriuvCEE9FeXY1TfY_yJ1mi05TCdHRfppwCSwi1S8/pub

edit: Como ahora tenemos 2 personas con pruebas, les concedo 30 euros a cada uno por si su prueba es correcta (aún tengo que comprobarlo) y luego no hay más dinero para nuevas pruebas.

Concedo adicionalmente 200 puntos de recompensa a la prueba más bonita (que puede ser una de las dos primeras pruebas publicadas u otra prueba aún no publicada), que puede ser decidida por la comunidad en términos de upvotes cerca del final cuando la recompensa expira (16.08.)

edit 2: Ahora a las 16.08. Doy los puntos de recompensa a Anton, ya que es la respuesta más completa y los detalles de la respuesta de findstats no están publicados todavía. Daré 30 euros a cada uno después de comprobar la prueba de findstats (cuando se publique y sea correcta).

edit 3: Ya que findstat actualizó la respuesta y ahora tiene una prueba completa de una extensión de la conjetura justo un poco de tiempo después de que otorgué la primera recompensa, también les daré una recompensa y aceptaré su respuesta (la segunda recompensa tenía que ser 400 o más y puede ser otorgada después de 24 horas).

Answer 1

ACTUALIZACIÓN

El escrito prometido, que demuestra ambas conjeturas, ya está terminado. Estará disponible en el arxiv el viernes, mientras tanto está disponible en el arXiv .

Respuesta original de FindStat

Tengo la siguiente conjetura refinada, que espero pueda transformarse en una prueba sin demasiados problemas:

llamemos a un par $(a, b)$ donde $a$ es un descenso y $b\in X_a$ que no cumple la condición

$c_{a+b} \geq c_{a+b-1}$ o $d_{a+b-1} = d_{a+b + c_{a+b}-1} - c_{a+b}$

a $2$ -Fallo de Gorenstein.

Entonces parece que el número de $2$ -Los fallos de Gorenstein son la composición de http://findstat.org/Mp00129 (La bijección Billey-Jockusch-Stanley a permutaciones que evitan 321) y http://findstat.org/St000732 (El número de deficiencias dobles de una permutación).

En dicho estadístico se hace referencia a un trabajo de Sergi Elizalde, "Fracciones continuas para estadísticas de permutación", que contiene una biyección entre $321$ -Evitar permutaciones sin dobles excedencias y caminos de Motzkin.

Por lo tanto, queda por demostrar que $2$ -Los fracasos de Gorenstein corresponden, en efecto, a deficiencias dobles.

Esquema de la prueba

A lo largo de la prueba, un camino de Dyck comienza en el origen, tiene pasos hacia el norte y el este y nunca va por debajo de la diagonal $y=x$ . Pensamos en la trayectoria de Dyck como si se tratara de una matriz de columnas etiquetadas $1$ a $n$ de izquierda a derecha, y filas etiquetadas $1$ a $n$ de abajo a arriba.

Recordemos primero la biyección debida a Billey, Jockusch y Stanley, enviando un camino de Dyck $D$ a un $321$ -evitando la permutación $\pi$ . Para obtener la matriz de permutación (invertida horizontalmente) de $\pi$ correspondiente a $D$ , pon una cruz en cada valle (un paso al este seguido de un paso al norte) y rellena las ranuras restantes con una secuencia creciente de cruces.

Nuestra afirmación es una consecuencia inmediata de las tres afirmaciones siguientes.

Lema 1. $c_{x+1} = c_x - 1$ si y sólo si $x$ es una deficiencia débil de $\pi$ Es decir $\pi(x)\leq x$ . Equivalentemente, hay un doble escalón este que abarca las columnas $x$ y $x+1$ .

Lema 2. $c_{x+1} = c_x - 1$ y $c_{x+1} + d_x = d_{x+c_{x+1}}$ si y sólo si $x$ es un punto fijo de $\pi$ .

Lema 3. Dejemos que $x$ ser una deficiencia estricta de $\pi$ . Entonces $\pi^{-1}(x)$ es también una deficiencia estricta si y sólo si $x+1=a+b$ donde $a$ es un descenso y $b\in X_a$ .

Tenemos la intención de ofrecer una versión detallada e ilustrada de este argumento en los próximos días.

Código Sage utilizado para descubrir la conjetura

def kupisch(D):
    """
    sage: [kupisch(D) for D in DyckWords(3)]
    [[2, 2, 2, 1], [2, 3, 2, 1], [3, 2, 2, 1], [3, 3, 2, 1], [4, 3, 2, 1]]
    """
    H = D.heights()
    return [1+H[i] for i, s in enumerate(D) if s == 0]+[1]

def cokupisch(D):
    """
    sage: [cokupisch(D) for D in DyckWords(3)]
    [[1, 2, 2, 2], [1, 2, 2, 3], [1, 2, 3, 2], [1, 2, 3, 3], [1, 2, 3, 4]]
    """
    H = D.heights()
    return [1]+[1+H[i+1] for i, s in enumerate(D) if s == 1]

def descents(D):
    """
    sage: [(D, kupisch(D), descents(D)) for D in DyckWords(3)]
    [([1, 0, 1, 0, 1, 0], [2, 2, 2, 1], [1]),
     ([1, 0, 1, 1, 0, 0], [2, 3, 2, 1], [1, 2]),
     ([1, 1, 0, 0, 1, 0], [3, 2, 2, 1], [1]),
     ([1, 1, 0, 1, 0, 0], [3, 3, 2, 1], [1]),
     ([1, 1, 1, 0, 0, 0], [4, 3, 2, 1], [1])]
    """
    c = kupisch(D)
    return [1] + [a+1 for a in range(1, len(c)) if c[a] > c[a-1]]

def gorenstein_failures(D):
    D = DyckWord(D)
    c = kupisch(D)
    d = cokupisch(D)
    D = descents(D)
    f = 0
    for a in D:
        if a == 1:
            X = range(1, c[0])
        else:
            X = range(c[a-1-1], c[a-1])
        for b in X:
            if c[a+b-1] >= c[a+b-1-1] or d[a+b-1-1] == d[a+b+c[a+b-1]-1-1] - c[a+b-1]:
                continue
            else:
                f += 1
    return f

findstat("Dyck Paths", gorenstein_failures)
0: (St000732: The number of double deficiencies of a permutation., [Mp00129: to 321-avoiding permutation (Billey-Jokusch-Stanley)], 200)
1: (St000366: The number of double descents of a permutation., [Mp00129: to 321-avoiding permutation (Billey-Jokusch-Stanley), Mp00087: inverse first fundamental transformation], 200)
2: (St000731: The number of double exceedences of a permutation., [Mp00129: to 321-avoiding permutation (Billey-Jokusch-Stanley), Mp00066: inverse], 200)

Answer 2

He aquí un esbozo de la prueba. Para mí los caminos de Dyck de longitud $n$ son caminos de $(0,0)$ a $(n,n)$ que consiste en que los pasos del Norte y del Este se mantengan débilmente por encima de la diagonal. Norte significa $(0,1)$ Este significa $(1,0)$ . Una ruta se llama primitivo si no está vacío y toca la diagonal sólo en los puntos extremos.

Un número de la forma $a+b-1$ para un descenso $a$ y $b\in N_a$ se llamará doble subida . Un número $i$ tal que $c_{i+1}<c_i$ se llamará doble caída . Si un número $i$ es tanto de doble subida como de doble bajada, lo llamamos coincide con . Su condición puede ser reformulada de la siguiente manera:

Para cualquier coincidencia $i$ la parte del camino de Dyck desde $(i-d_i, i)$ a $(i, i+c_i)$ es una secuencia de pasos del Norte seguida de una secuencia de pasos del Este.

Para cualquier primitiva $2$ -Camino Dorenstein Dyck $p$ elegimos la menor coincidencia $i$ si existe y construye dos caminos $p_1$ , $p_2$ de la siguiente manera. $p_1$ es el camino desde $(0,0)$ a $(i,i)$ obtenida por medio de $p$ y luego, en cuanto alcanzamos la posición de doble subida, hacemos un "corte", es decir, simplemente realizamos $d_i$ Escalones del este. Entonces comenzamos el camino $p_2$ en $(i,i)$ por $c_i$ Pasos al norte para que lleguemos a la posición de doble caída y luego continuar por el camino $p$ .

Lema 1. La construcción anterior proporciona una biyección entre el conjunto de primitivas $2$ -Caminos Dorenstein Dyck $p$ de longitud $n$ con al menos una coincidencia y el conjunto de pares de caminos primitivos de Dyck $p_1, p_2$ cuyas longitudes suman $n$ y tal que $p_1$ no tiene coincidencias y $p_2$ es $2$ -Gorenstein.

Iterando esto tantas veces como sea necesario para eliminar todas las coincidencias obtenemos

Corolario 1. Existe una biyección entre el conjunto de primitivas $2$ -Gorenstein Dyck caminos de longitudes $n$ y el conjunto de tuplas de trayectorias Dyck primitivas sin coincidencias cuyas longitudes suman $n$ .

Alternativamente, tenemos una biyección entre las primitivas $2$ -Caminos de Dyck de Gorenstein y caminos de Dyck arbitrarios sin coincidencias.

Ahora miramos la definición de los números de Motzkin, denotándolos por $M_n$ . Utilizamos la definición que dice que $M_n$ es el número de caminos desde $(0,0)$ a $(n,0)$ que consiste en pasos $U=(1,1)$ , $D=(1,-1)$ , $F=(1,0)$ manteniéndose débilmente por encima del eje horizontal. Vamos a construir una biyección entre trayectorias sin coincidencias y números de Motzkin.

Teniendo un camino de Dyck sin coincidencias, construyamos un camino de Motzkin como sigue. Sea $DR$ sea el conjunto de subidas dobles. Sea $DF$ ser el conjunto de caídas dobles. Es bien sabido que $|DR|=|DF|$ . Para un camino de Dyck sin coincidencias, estos conjuntos no se cruzan. Obsérvese que el par $DR, DF$ determina de forma única la trayectoria de Dyck. A partir de un par de conjuntos no intersecantes $DR, DF\subset\{1,\ldots,n-1\}$ del mismo tamaño construimos un camino desde $(0,0)$ a $(n-1,0)$ de la siguiente manera: Pasamos por $i=1,\ldots,n-1$ . Cuando $i\in DR$ ponemos $U$ . Cuando $i\in DF$ ponemos $D$ . De lo contrario, ponga $F$ . Llamemos a la trayectoria resultante la $UDF$ -ruta correspondiente a $DR, DF$ . La prueba se completa con lo siguiente

Lema 2. Un par de subconjuntos no intersecantes $DR, DF\subset \{1,\ldots,n-1\}$ del mismo tamaño proviene de un camino de Dyck si y sólo si el correspondiente $UDF$ -es una ruta de Motzkin.

Prueba. Consideremos una ruta arbitraria desde $(0,0)$ a $(n,n)$ consistente en unos pasos de Norte y Este tales que el primer paso es el Norte. Veamos el camino como una unión de segmentos verticales y horizontales intercambiados (ahora de longitudes $\geq 1$ ). Etiquetamos los segmentos horizontales y verticales con números de $1$ a $k$ . Es decir, primero tenemos un segmento vertical con etiqueta $1$ y, a continuación, un segmento horizontal con la etiqueta $1$ y luego un segmento vertical con la etiqueta $2$ y así sucesivamente. Para cada $i$ dejar $h_i$ sea la etiqueta del segmento horizontal que cruza la línea $x=i-\frac12$ . Sea $v_i$ sea la etiqueta del segmento vertical que cruza la línea $y=i-\frac12$ . Sea $d_i=h_i-v_i$ . Compruebe que los puntos $(i-1,d_i)$ son precisamente los puntos por los que pasa el $UDF$ ruta va. Comprueba que la trayectoria es una trayectoria Dyck precisamente cuando $d_i\geq 0$ para todos $i$ .

Por ejemplo, tomemos la ruta Dyck NNENEE. Tenemos una doble subida $i=1$ , una caída doble $i=2$ . Tenemos $d_1=0$ , $d_2=1$ , $d_3=0$ . Esto corresponde a la trayectoria UD de Motzkin. Por otro lado, NENENE produce $d_1=d_2=d_3=0$ y Motzkin path FF.