Una biyección entre conjuntos de tablas de Young de dos tipos

Question

Suponiendo que el problema de la exhibición de una biyección no se considere una búsqueda frívola, permítanme plantear una pregunta que me preocupa desde hace algún tiempo.

Dejemos que $\lambda \vdash n$ denotan el hecho de que $\lambda$ es una partición de $n$ . Denote el número de partes por $l(\lambda)$ . Si $T$ es una tabla de Young estándar (SYT), denotaremos la forma de partición subyacente por $sh(T)$ .

Dado un número entero par positivo $2n$ , dejemos que $$ Pe_{2n}=\{ \lambda: \lambda\vdash 2n,\text{ } l(\lambda) \leq3 \text{ and all parts of } \lambda \text{ are even} \}$$ y $$ Qe_{2n}=\{ \lambda: \lambda\vdash 2n, \lambda = (k,k,1^{2n-2k}), \text{ }k\geq 1 \}$$

A partir de estos conjuntos definiremos otros dos conjuntos cuyos elementos son SYTs. $$ TPe_{2n}=\{T: T \text{ an SYT, } sh(T)\in Pe_{2n} \}$$ y $$ TQe_{2n}=\{T: T \text{ an SYT, } sh(T)\in Qe_{2n} \}$$

$\textbf{Question}$ : ¿Existe una prueba biyectiva que demuestre que las cardinalidades de $TPe_{2n}$ y $TQe_{2n}$ son iguales?

La segunda pregunta es muy similar. Dado un entero positivo impar $2n+1$ , dejemos que $$ Po_{2n+1}=\{ \lambda: \lambda\vdash 2n+1,\text{ } l(\lambda)=3 \text{ and all parts of } \lambda \text{ are odd} \}$$ y $$ Qo_{2n+1}=\{ \lambda: \lambda\vdash 2n+1, \lambda = (k,k,1^{2n+1-2k}), \text{ }k\geq 1 \}$$

A partir de estos conjuntos definiremos otros dos conjuntos cuyos elementos son SYTs. $$ TPo_{2n+1}=\{T: T \text{ an SYT, } sh(T)\in Po_{2n+1} \}$$ y $$ TQo_{2n+1}=\{T: T \text{ an SYT, } sh(T)\in Qo_{2n+1} \}$$

$\textbf{Question}$ : ¿Existe una prueba biyectiva que demuestre que las cardinalidades de $TPo_{2n+1}$ y $TQo_{2n+1}$ son iguales?

Intenté varios enfoques (interpretaciones de la trayectoria de Motzkin, diagramas de correspondencia, etc.) pero no tuve éxito. Espero que alguien de aquí pueda guiarme.

La entrada pertinente de la OEIS sería texto del enlace

Gracias,

Vasu

Answer 1

No es una respuesta, pero es demasiado larga para un comentario. Esto responde a un comentario anterior y señala el caso más pequeño en el que la biyección solicitada no es obvia (para el caso par).

A través de $n = 8$ Los conjuntos de partición están en biyección a través de una combinación de transposición y el mapa de identidad, por lo que hay una correspondencia directa para los cuadros.

$Pe_{10} = \{10, 82, 64, 622, 442\}$ y $Qe_{10} = \{55, 4411, 331^4, 221^6, 1^{10}\}$ . Las particiones que no coinciden son 64 y 442 frente a 55 y 4411.

Utilizando la fórmula de la longitud del gancho, hay 90 tablas estándar de Young de la forma (6,4) y 252 de la forma (4,4,2), por lo que éstas contribuyen con 342 a $TPe_{10}$ . (Perdón por el cambio en la notación de las particiones, pero "90 de forma 64" parecía extraño). Hay 42 cuadros de forma (5,5) y 300 de forma (4,4,1,1), que también aportan 342 a $TQe_{10}$ . Por lo tanto, la conjetura es válida para $n=10$ .

Este ejemplo muestra que la biyección solicitada no puede preservar la forma del cuadro/partición subyacente.

---

El siguiente caso es aún más interesante porque los recuentos de los cuadros coinciden aunque no haya el mismo número de particiones en los conjuntos.

Las particiones no coincidentes son $(8,4),(6,4,2),(4,4,4) \in Pe_{12}$ y $(5,5,1,1),(4,4,1,1,1,1) \in Qe_{12}$ . Y las sumas funcionan: Escribir $\textrm{SYT}(\lambda)$ para el número de tablas estándar de Young con forma $\lambda$ tenemos $$\textrm{SYT}((8,4))+\textrm{SYT}((6,4,2))+\textrm{SYT}((4,4,4))=275+2673+462=3410,$$ $$\textrm{SYT}((5,5,1,1))+\textrm{SYT}((4,4,1,1,1,1))=1485+1925=3410.$$

Los dos casos siguientes funcionan pero no ofrecen nada nuevo. He aquí algunos comentarios generales.

• A partir de una fórmula para el número de particiones de $n$ con hasta tres partes, $|Pe_{2n}| = \lfloor \frac{(n+3)^2}{12} \rceil$ donde $\lfloor \cdot \rceil$ denota el número entero más cercano.

• Para $n$ impar, 3 particiones coinciden entre los dos conjuntos: $(2n)$ , $(2n-2,2)$ y $(2n-4,2,2)$ en $Pe_{2n}$ con $1^{2n}$ , $221^{2n-4}$ y $331^{2n-6}$ en $Qe_{2n}$ (coincidencia por transposición).

• Para $n$ incluso, 4 particiones coinciden porque $(n,n)$ está en ambos conjuntos.

• Siguiendo esta línea de razonamiento se necesitarían fórmulas para $\textrm{SYT}(\lambda)$ para las particiones de cada uno de los conjuntos.

---

Siguiendo con el último punto, en la nota de la JCTA de 1996 "Polygon Dissections and Standard Young Tableaux", Stanley atribuye a O'Hara y Zelevinsky una fórmula para $\textrm{SYT}(\lambda)$ para $\lambda = kk1^m$ . Reescrito en términos de $k$ y $m$ Es decir, es $$\frac{1}{2k+m+1} \binom{2k+m+1}{k} \binom{m+k-1}{k-1}.$$ Tal vez la biyección de Stanley entre tales cuadros y ciertos conjuntos de diagonales no intersectadas en un polígono que se discute en la nota podría ayudar.

---

No es difícil averiguar que $$\textrm{SYT}((a,b,c))=\frac{(a+b+c)!(a-b+1)(b-c+1)(a-c+2)}{(a+2)!(b+1)!c!}$$ (sin tener en cuenta la paridad de $a,b,c$ ).

Answer 2

Permítanme explicar una forma de probar tales resultados. Hay (en su mayoría) dos tipos de personas, las que piensan en el $n$ El número catalán como $\frac{1}{n+1}\binom{2n}{n}$ y los que piensan en ello como $\binom{2n}{n}-\binom{2n}{n-1}$ . El primer tipo de personas probablemente pensará en las trayectorias de Dyck como clases de equivalencia o $\mathbb Z/(n+1)\mathbb Z$ órbitas de trayectorias, mientras que el segundo tipo probablemente pensará en las trayectorias de Dyck como "trayectorias dentro de una $n\times n$ rectángulo que no cruzar el origen" (Ver prueba 2 vs prueba 3 ici ). Mientras que el primer tipo probablemente se contentaría con contar cuadros jóvenes estándar utilizando la forma habitual del fórmula de la longitud del gancho El segundo tipo probablemente preferiría el (equivalente):

Fórmula de Jacobi-Trudi

El número de tablas de Young estándar en una partición de forma $\lambda=(\lambda_1,\dots,\lambda_k)$ de $n$ es $$f^{\lambda}=\sum_{\sigma \in S_k}\varepsilon(\sigma)\binom{n}{\lambda_1+k-\sigma(k)\, ,\dots,\,\lambda_k+1-\sigma(1)}.$$ Donde $\varepsilon$ denota el signo de una permutación. Como en el caso de los números catalanes, en esta presentación se sacrifica la positividad obvia pero se tiene la integralidad obvia. A modo de ilustración, en el caso $k=3$ , esto dice $$f^{(a,b,c)}=\binom{n}{a,b,c}+\binom{n}{a+1,b+1,c-2}+\binom{n}{a+2,b-1,c-1}-\binom{n}{a+1,b-1,c}-\binom{n}{a,b+1,c-1}-\binom{n}{a+2,b,c-2}.$$

El cómputo:

Tomemos el caso de tres partes pares, aunque este método funcionará tanto para el caso impar como para el caso general de particiones con un número fijo (arbitrario) de filas. Si se suma la cantidad $f^{(a,b,c)}$ sobre todos los triples de enteros $a\geq b\geq c\geq 0$ con $a+b+c=n$ entonces los coeficientes multinomiales forman la fórmula anterior telescopio y nos queda $$|TPe_{2n}|=\sum_{k\geq 0}\binom{2n}{k,k,2n-2k}-\sum_{k\geq 0}\binom{2n}{k,k+1,2n-2k-1}$$

Ahora podemos centrar nuestra atención en $TQe_{2n}$ . Podemos contar el número de SYT de forma $(k,k,1^{2n-2k})$ de la fórmula de la longitud del gancho, pero en lugar de presentarlo en "tipo uno" como hizo Brian Hopkins en la otra respuesta, utilizaremos la presentación "tipo dos" $$f^{(k,k,1^{2n-2k})}=\binom{2n}{k}\binom{2n-k-1}{k-1}-\binom{2n}{k+1}\binom{2n-k}{k}$$ $$=\binom{2n}{k,k,2n-2k}-\binom{2n}{k}\binom{2n-k-1}{k}-\binom{2n}{k-1}\binom{2n-k}{k}.$$

Así que para obtener la igualdad deseada sumamos sobre todos los $k\geq 1$ $$|TQe_{2n}|=\sum_{k\geq 1}f^{(k,k,1^{2n-2k})}=\sum_{k\geq 1}\left(\binom{2n}{k,k,2n-2k}-\binom{2n}{k}\binom{2n-k-1}{k}-\binom{2n}{k-1}\binom{2n-k}{k}\right)$$ $$=\sum_{k\geq 1}\binom{2n}{k,k,2n-2k}-\sum_{k\geq 0}\left(\binom{2n}{k}\binom{2n-k-1}{k}+\binom{2n}{k}\binom{2n-k-1}{k+1}\right)+\binom{2n}{0}\binom{2n-1}{0}$$ $$=\sum_{k\geq 1}\binom{2n}{k,k,2n-2k}-\binom{2n}{k,k+1,2n-2k-1}+\binom{2n}{0,0,2n}$$ $$=\sum_{k\geq 0}\binom{2n}{k,k,2n-2k}-\sum_{k\geq 0}\binom{2n}{k,k+1,2n-2k-1}=|TPe_{2n}|.$$

¿Puede hacerse biyectiva?

Sí. Todas las manipulaciones con coeficientes binomiales tienen interpretaciones biyectivas obvias en términos de caminos de la red, así que habría que hacer lo mismo con la fórmula de Jacobi-Trudi mencionada anteriormente. Esto es clásico para el caso de los números catalanes pero se puede generalizar para cualquier partición utilizando un truco de reflexión similar. He sido perezoso y no he elaborado la biyección final para ti, pero al menos esto es un comienzo. Actualmente estoy escribiendo una nota sobre tales biyecciones entre SYT's con partes acotadas, así que si nadie lo ha explicado para entonces me aseguraré de actualizar esta respuesta.