Me animaron a publicar esta pregunta por Jim Propp, durante una reunión de la Cambridge Combinatoria y Café Club. Es un contrapunto a la MathOverflow pregunta "Problemas de Recuento de donde la Etiqueta es Conocida pero sin etiquetar No es" el que pide ejemplos donde se sabe cómo contar los objetos de etiquetado, pero no se sabe cómo contar sin etiquetar los objetos.
Creo que la expectativa general en la combinatoria enumerativa es que debería ser más fácil para el conteo de objetos de etiquetado como contraposición a la etiqueta de los objetos. Por ejemplo, tenemos mucho más agradable fórmulas para el número de la etiqueta de los árboles, etiqueta, gráficas de la etiqueta conectada gráficos en $n$ vértices de la correspondiente etiqueta de los objetos. (Aquí la etiqueta significa que los vértices están etiquetados.)
Sin embargo, yo estoy pidiendo contraejemplos a esta tendencia general. Es decir, estoy buscando ejemplos de problemas de aritmética donde el sin etiquetar los objetos tienen un mejor fórmula que la de los objetos de etiquetado. Yo sé de dos ejemplos de ello.
Semiorders. Un semiorder, también conocido como unidad de intervalo de orden, es un poset, que evita la $2+2$ e $3+1$ como la inducida subposets. El número de semiorders en $n$ no marcado de los elementos es el $n$th catalán número $C_n := \frac{1}{n+1}\binom{2n}{n}$. El número de la etiqueta semiorders es la secuencia de A006531 en la OEIS. La etiqueta semiorders en $n$ elementos tienen un exponencial de la generación de la función de $C(1-e^{-x})$ donde $C(x) = \frac{1-\sqrt{1-4x}}{2x}$ es el ordinario de generación de función para el catalán números.
Umbral de gráficos. Un umbral gráfico es un gráfico de $G=(V,E)$ por que hay algunos umbral de la función $\omega\colon V\to\mathbb{R}$ en los vértices tal que $\{i,j\}\in E$ fib $\omega(i)+\omega(j) > 0$. El número de umbral de gráficos en $n$ sin etiquetar los vértices es $2^{n-1}$ (porque no es un simple recursivo de construcción de estos gráficos). El número de la etiqueta umbral de gráficos de secuencia A005840 en la OEIS. La etiqueta umbral de gráficos en $n$ vértices tiene una exponencial de generación de función $\frac{e^x(1-x)}{(2-e^x)}$.
¿Alguien sabe de otros ejemplos como estos? Curiosamente, tanto semiorders y el umbral de gráficos que hemos asociado un hyperplane acuerdo; véase Stanley notas.
