12 votos

Misteriosa identidad entre los números de los sistemas de meandros Impares

Definiciones:

Un sistema de arco superior de orden $n$ es un subconjunto del plano formado por $n$ semicírculos cerrados no intersecantes en el semiplano superior cuyos puntos extremos pertenecen al conjunto $\{(k,0)\mid 1\leqslant k\leqslant2n\}$ .

Es bien sabido que el número de todos los sistemas de arcos superiores de orden $n$ es $C_n=\frac{(2n)!}{n!(n+1)!}$ El $n$ El número catalán.

Los sistemas de arco inferior son exactamente lo mismo en el medio plano inferior.

A (cerrado) sistema de ordenación de los meandros $n$ es la unión de un sistema de arcos superior y otro inferior de orden $n$ .

Dejemos que $MS_n$ sea el número de todos los sistemas de meandros de orden $n$ . Así, $MS_n=C_n^2$ .

Llama a un sistema de meandros impar , resp. incluso si tiene impar, resp. número par de componentes conectados.

Ilustraciones:

an even meander system of order 6

an odd meander system of order 8

(El primero es un sistema de meandro par de orden 6, el segundo - un sistema de meandro impar de orden 8).

Dejemos que $OMS_n$ , resp $EMS_n$ sea el número de sistemas Impares, resp. pares de meandros de orden $n$ .

La evidencia numérica sugiere que para todos los $k$ uno tiene

$$OMS_{2k}=EMS_{2k},$$ $$OMS_{2k+1}=EMS_{2k+1}+MS_k.$$

¿Alguien sabe si esto es cierto?

(Observación: si es cierto, entonces obviamente $OMS_{2k}=EMS_{2k}=\frac12C_{2k}^2$ y $OMS_{2k+1}=\frac12\left(C_{2k+1}^2+C_k^2\right)$ , $EMS_{2k+1}=\frac12\left(C_{2k+1}^2-C_k^2\right)$ )

Observación final: como ha señalado Gjergji Zaimi en un comentario más abajo, esto es en Estadísticas de meandros, pliegues y arcos de Di Francesco, Golinelli y Guiller (6.16, página 51). Así que tengo que disculparme por obligarles a pensar en la pregunta contestada hace 20 años.

Aun así fue divertido, ¿no?

6voto

tessein Puntos 1705

Déjame que te dé el esqueleto de una respuesta y luego puedo añadir más detalles si quieres.

Un sistema de arcos puede representarse como un conjunto de pares ordenados; por ejemplo, en el primer ejemplo el sistema de arcos superior es $$\{(1,12),(2,11),(3,10),(4,9),(5,6),(7,8)\}$$ y el sistema de arco inferior es $$\{(1,8),(2,5),(3,4),(6,7),(9,10),(11,12)\}.$$ Los números de cada par son siempre de paridad opuesta.

Definir la paridad de un sistema de arco como $$ \prod_{\text{pairs }(a,b)}(-1)^{\frac{b-a-1}{2}} $$ por lo que la paridad del sistema de arco superior es $-1$ y la paridad del sistema de arco inferior es $+1$ .

No es difícil ver que la paridad de un meandro $m$ (donde impar se identifica con $-1$ e incluso con $+1$ ) es igual al producto de las paridades de sus sistemas de arcos constitutivos y $(-1)^{\text{order}(m)}.$

EDITAR:

Consideremos un meandro en el que el sistema de arcos superior contiene dos pares de la forma $(a, b)$ y $(a+1,a+2)$ . Compárese con el meandro en el que sustituimos estos dos arcos por $(a,a+1)$ y $(b,a+2)$ . Es evidente que esto intercambia la paridad del meandro y del sistema de arco. Cualquier sistema de arco puede reducirse a $\{(1,2),\ldots,(2n-1,2n)\}$ por un número finito de estos movimientos.

(fin de la edición)

A continuación, contemos con los sistemas impar e incluso con los sistemas de arco. Dejemos que $A_{-1}(n)$ y $A_{+1}(n)$ sea el número de $-1$ y $+1$ sistemas de arco de paridad, respectivamente (conjunto formal $A_{+1}(0)=1$ y $A_{-1}(0)=0$ ). Entonces, al mirar lo que está emparejado con $1$ obtenemos las recursiones \begin{align*} A_{-1}(n)&=\sum_{i=0,2,\ldots} \big(A_{-1}(i)A_{+1}(n-i-1) + A_{+1}(i)A_{-1}(n-i-1)\big)\\ &+\sum_{i=1,3,\ldots}\big(A_{-1}(i)A_{-1}(n-i-1) + A_{+1}(i)A_{+1}(n-i-1)\big) \end{align*} y \begin{align*} A_{+1}(n)&=\sum_{i=1,3,\ldots} \big(A_{-1}(i)A_{+1}(n-i-1) + A_{+1}(i)A_{-1}(n-i-1)\big)\\ &+\sum_{i=0,2,\ldots}\big(A_{-1}(i)A_{-1}(n-i-1) + A_{+1}(i)A_{+1}(n-i-1)\big) \end{align*}

Un simple reordenamiento de las sumas muestra que $A_{+1}(2k)=A_{-1}(2k)$ lo que implica que ambos son $\frac{C_{2k}}{2}$ .

EDIT: argumento inductivo añadido.

El siguiente argumento inductivo muestra que $A_{\pm 1}(2k+1)=\frac{C_{2k+1}\pm(-1)^k C_k}{2}$ .

Si $n\equiv1\pmod 4$ entonces cuando $i$ es impar, entonces uno de $\{i,n-i-1\}$ es $1\pmod 4$ y uno es $3\pmod 4$ .

Por inducción, la suma anterior, para $A_{-1}(n)$ digamos, es: \begin{align*} A_{-1}(n)&= \sum_{i=0,2,\ldots} \frac{C_iC_{n-i-1}}{2}\\ &+\sum_{i=1,3,\ldots}\frac{1}{4}\left( \left(C_i+C_{\frac{i-1}{2}}\right)\left(C_{n-i-1} - C_{\frac{n-i-2}{2}}\right) + \left(C_i-C_{\frac{i-1}{2}}\right)\left(C_{n-i-1} + C_{\frac{n-i-2}{2}}\right)\right) \\ &=\sum_{i=0,1,2,\ldots} \frac{C_iC_{n-i-1}}{2} -\sum_{i=1,3,\ldots} \frac{C_{\frac{i-1}{2}}C_{\frac{n-i-2}{2}}}{2} \\ &=\frac{C_n}{2} -\sum_{j=0,1,2,\ldots}\frac{C_{j}C_{\frac{n-1}{2}-j-1}}{2} =\frac{C_n}{2} - \frac{C_{\frac{n-1}{2}}}{2}. \end{align*} Los otros casos de la inducción (para $n\equiv 3\pmod 4$ y/o si se quiere una inducción independiente para $A_{+1}(n)$ son similares.

(fin de la edición)

Entonces, utilizando la relación entre la paridad de los meandros y la paridad de los sistemas de arcos, el resultado se sigue por aritmética.

Puedo proporcionar más detalles sobre la recursión, el reordenamiento, el argumento inductivo o la aritmética final una vez que el $A_{\pm 1}$ se han determinado, si se desea.

5voto

Alexey Ustinov Puntos 3951

No es una solución, sólo una observación adicional. Es mejor dividir los números catalanes en dos partes $$C_n=O_n+E_n,$$ donde $O_n$ ( $E_n$ ) es el número de sistemas de arco superior "impar" ("par") de orden $n$ : el número con regiones fluviales Impares donde "región fluvial" son regiones del semiplano superior que estarán dentro de componentes conectados del futuro meandro. (En el primer diagrama tenemos 4 regiones fluviales en el semiplano superior y 4 regiones fluviales en el semiplano inferior. En el segundo diagrama 5 y 4) Estas secuencias se conocen como http://oeis.org/A007595 y http://oeis.org/A000150 .

Entonces $$OMS_{k}=2E_k\cdot O_k,\qquad EMS_{k}=O_k^2+E_k^2.$$

De este modo, es necesario demostrar que la paridad del meandro es una suma de las paridades de los sistemas de arcos superiores e inferiores.

EDT: Se hizo en la respuesta de Gabriel C. Drummond-Cole. También de su respuesta se desprende que
$$(-1)^{\text{parity of river regions}}=\prod_{{\rm pairs}(a,b)}(-1)^{\frac{b-a+1}2}.$$

(Imágenes añadidas por el OP - pensó que sería más instructivo de esta manera. La paridad de un sistema de arcos es la paridad del número de componentes conectados del subconjunto gris del medio plano correspondiente. Nótese que se puede hacer la coloración de una mitad sin saber nada de la otra).

enter image description here

enter image description here

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X