Combinatoria resultados sin que se conoce combinatoria pruebas

Question

Stanley le gusta mantener una lista de combinatoria de los resultados para los cuales no se conoce la combinatoria de la prueba. Por ejemplo, hasta hace poco yo creo que la enumeración explícita de de Brujin secuencias cayó en esta categoría (pero ahora vemos arXiv:0910.3442v1). Muchos unimodality resultados también entran en esta categoría. ¿Sabes de otros resultados de este tipo, sobre todo de los resultados que se ven y frustrante como deberían tener simple combinatoria de las pruebas?

Para los efectos de esta pregunta, "combinatoria" resultado debe ser interpretado en el sentido de algún tipo de enumeración exacta, y "combinatoria prueba" debe ser interpretado en el sentido de, más o menos, "bijective la prueba". (Así, por ejemplo, no estoy interesado en los límites de Ramsey números).

Answer 1

Este es un tema común en la combinatoria enumerativa. Usted puede encontrar una gran cantidad de ejemplos con la búsqueda de Google "no bijective prueba" (con comillas).

En primer lugar, me puede decir algo acerca de por qué podría la atención sobre bijective pruebas. La combinatoria de las especies son sin duda una buena teoría, pero son bastante específicas y elaboradas de respuesta relacionadas con la generación de funciones. Una razón más general es que un bijective prueba categorifies una igualdad en la combinatoria a la categoría de conjuntos. En otras palabras, promueve la igualdad de $|A| = |B|$ para un isomorfismo $A \cong B$. En mi opinión, es tan importante encontrar a ningún otro categorification, por ejemplo, a la categoría de espacios vectoriales. En lugar de demostrar que dos conjuntos tienen el mismo tamaño con un bijection, tendría que demostrar que son del mismo tamaño usando una matriz invertible.

Segundo, de los muchos ejemplos, puedo nombrar a uno con el que me encontré. Este ejemplo es interesante porque los objetos en cuestión parecen ser muy similares. Recordemos que una alternancia de signo de la matriz es una matriz cuya no-cero entradas en cada fila y columna se alternan entre $1$ y $-1$, y de tal manera que la primera y la última entrada distinto de cero en cada fila y columna es de $1$. Una interesante subclase es la ASMs de orden $2n+1$, que son simétricas respecto a una línea vertical. Otra interesante subclase es la ASMs de orden $2n$ que son en diagonal simétrica y tiene 0 en la diagonal. (ASMs de cualquier tipo de enfrente de la paridad no existen.) La primera clase fue descubierto por David Robbins y me encontré con la segunda clase. Me lo demostró David de la fórmula del producto para la primera clase y he establecido la misma fórmula del producto para la de segunda clase. Así que estas dos clases de ASMs son equinumerous, pero no bijective prueba es conocida.

---

Aquí está otro ejemplo interesante en la misma vena. Cíclico simétrico, la auto-complementarios plano de partición (CSSCPP) es equivalente a la de un suelo de baldosas de un hexágono regular de orden $2n$ por unidad de pastillas, que es invariante bajo de 60 grados de rotación. Aquí una unidad de rombo es la unidad de dos triángulos equiláteros pegadas. Totalmente simétrica, la auto-complementarios plano de partición (TSSCPP) es la misma cosa, excepto con plena diedro de simetría. (Hago el tamaño, incluso porque de lo contrario no hay ningún plano de las particiones con el impuesto de simetría.) Las fórmulas para ambas clases fueron también conjeturó por David Robbins; George Andrews demostró su conjetura para TSSCPPs y me lo demostró la conjetura de CSSCPPs. En particular, el número CSSCPPs de un tamaño fijo es el cuadrado del número de TSSCPPs, pero nadie sabe de un buen bijection.

El único más sorprendente que David Robbins encontró que el número de TSSCPPs, que son el plano de las particiones con total simetría, es igual al número de ASMs con ningún impuesto de la simetría. No bijective prueba de que es conocido. En el lado positivo, Doron Zeilberger la prueba de la ASM conjetura, y su papel en el refinado ASMs, podrían ser los pasos hacia el otro, porque equiparar ciertas generalizaciones y refinado de las enumeraciones. Sin embargo, la alternancia de signo matrices de tener un aspecto totalmente diferente desde el plano de las particiones. En mi opinión, el más frustrante caso es cuando ni siquiera podemos coincidir igual a igual.

Answer 2

Advertencia: este se utiliza para ser un gran ejemplo, pero me temo que ya no lo es.

Deje que $H(n)$ ser el número de horizontal-convexo polyominoes en el plano, donde "horizontalmente convexo" significa justo lo que creo que significa, y la equivalencia está justo arriba de traducciones (modo de espejo las imágenes y las rotaciones se consideran distintos). El uso de una secuencia de manipulaciones con dos variables de generación de funciones y una cantidad increíble de cancelación, se encuentra que

$H(n) = 5H(n-1) - 7(n-2) + 4H(n-3)$.

Esto lo aprendí de Gil Kalai en 1991 (y el resultado es mucho más), y estoy bastante seguro de que no había conocido combinatoria prueba de este resultado sorprendente para un rato. Sin embargo, recientemente Decano Hickerson encontrado uno. Estoy seguro de que Dean pensó que esto parece frustrante como algo que debe tener una combinatoria de prueba y, a continuación, se procedió a resolver este frustración de la única forma posible.

Answer 3

Por ejemplo, según Stanley la identidad $n \cdot \text{pp}(n) = \sum_{i=1}^{n} \sigma_2(i) \text{pp}(n-i)$ no se conoce ningún bijective prueba, donde $\text{pp}(n)$ denota el número de plano particiones de $n$.

Answer 4

El número de clases de isomorfismo) auto complementario gráficas de n vértices es la diferencia entre el número de gráficos en n vértices con un número impar de aristas y el número con un número par de aristas.

Esto es relativamente fácil de comprobar con el recuento de los argumentos, pero me encantaría tener una combinatoria prueba de ello...

Answer 5

Esto no es exactamente una respuesta, pero ya que este es el wiki de la comunidad espero que sea en el espíritu de las cosas si puedo añadir una vuelta de tuerca a la cuestión.

Una de las cosas excelentes sobre el excelente teoría de la especie es que tiene en su corazón una noción natural de bijective prueba. Permítanme esbozar la idea básica. Una especie es simplemente un functor de la categoría $$\mathcal{B} = (\mbox{finito de conjuntos } + \mbox{ bijections})$$ a la categoría de conjuntos. Uno piensa de una especie como una manera de decorar un conjunto finito con algo más de estructura combinatoria. Por ejemplo, hay una especie $L$ definida por $$L(X) = \{ \mbox{lineal órdenes } X\}$$ para finito de conjuntos de $X$ (y se define de la manera obvia de morfismos). Mus $L(X)$ es el conjunto de formas de "decoración" $X$, con un orden lineal. O bien, hay otra especie $P$ definida por $$P(X) = \{ \mbox{permutaciones }X\}$$ para finito de conjuntos de $X$ (y se define de la manera obvia de morfismos).

Usted puede pensar de especies como categorified funciones de generación. Más exactamente, para cualquier especie $S$ es finito (toma valores finitos conjuntos), usted puede formar su exponencial de la generación de la función $\sum_n s_n x^n/n!$, donde $s_n$ es la cardinalidad de $S(X)$ para $n$-elemento del conjunto $X$. Al pasar de una especie a su generación de función (decategorification), pierde algo de información. Te voy a dar un no-trivial ejemplo de esto en un momento.

Es obvio que la noción de isomorfismo de las especies, es decir, natural de isomorfismo de functors. Son las especies de $L$ y $P$ por encima isomorfos? Tenemos $L(X) \cong P(X)$ para todo $X$, desde una $n$-element set admite tanto $n!$ lineal órdenes y $n!$ permutaciones. Pero se puede mostrar que no es natural isomorfismo $L \cong P$. Así que no, $L$ y $P$ no son isomorfos. La intuición es la siguiente: en orden para que coincida permutaciones y órdenes, usted debe elegir un fin de corresponder a la identidad de permutación; pero un resumen conjunto finito no tiene canónica de la orden lineal, de manera que tendría que hacer una elección al azar. Por lo tanto no hay canónico de correspondencias entre ellos.

En particular, esto implica que las especies con la misma generación de función ($\sum_n n! x^n/n! = 1/(1-x)$, aquí) no necesitan ser isomorfos. Así que sí, pasando a la generación de función puede perder información.

Moral: una noción de "bijective prueba" es "la existencia de un isomorfismo de las especies". Se trata de una noción exigente, como la permutación/ejemplo de pedido muestra. Uno podría considerar la posibilidad de compilar una lista de todos los pares de especies que tienen la misma generación de función, pero no son isomorfos. Esta lista podría resultar útil en comparación con Stanley lista.