Es posible que un número finito de combinatoria problema puede admitir una solución de forma cerrada, y para que esto sea imposible en la práctica para demostrar la validez de esta solución? No estoy seguro de si una definición rigurosa puede ser atribuido a la noción de un número finito de combinatoria problema, pero me refiero a los problemas de la siguiente naturaleza:
Dado un conjunto conjunto finito $X$, que puede o no puede tener una estructura adicional, enumerar el número de elementos en $X$ que satisface alguna restricción definida en términos de los elementos primitivos de la teoría de conjuntos y el adicional de la estructura de $X$.
Ya que estamos hablando de la forma cerrada de soluciones, realmente estamos muy interesados en las familias de los finitos de problemas de combinatoria, parametrizadas por $\mathbb{N}$, lo que escala en algunos de forma natural con el aumento de la $n\in \mathbb{N}$. No estoy seguro de si la noción de una forma cerrada de la solución se puede dar una definición rigurosa, pero me refiero a algo a lo largo de las líneas de la siguiente definición de Graham, Knuth, y Patashnik del Concreto de las Matemáticas:
Una expresión de una cantidad $f\left(n\right)$ es en forma cerrada si se pueden calcular utilizando en la mayoría de un número fijo de "bien conocidos" operaciones estándar, independiente de $n$.
Entiendo que esta pregunta es vaga y abierta, entonces yo sería feliz con respuestas o respuestas parciales a cualquiera de las siguientes preguntas.
Hay ejemplos de finitos de problemas de combinatoria para que la evidencia empírica sugiere que hay una forma cerrada de la solución, pero para los que significativo esfuerzo no ha logrado producir las pruebas de la validez de esta solución?
Es posible dar un riguroso axiomatization que captura la noción de un determinado problema combinatorio que el trabajo combinatorialists trabajar con y, a continuación, aportar ideas a lo largo de las líneas de los Teoremas de Gödel y Turing del trabajo sobre la detención Problema de producir una prueba de la existencia de tales familias de los problemas de combinatoria? Puede cualquier rigurosa formulación ser atribuido a la noción de una familia finita de combinatoria problemas de escala, naturalmente, con $n\in\mathbb{N}$?
Hay ejemplos de finitos de problemas de combinatoria que mostrar un tipo de regularidad para grandes $n$. Es decir, ¿se conocen las familias de los finitos de problemas de combinatoria que la escala natural con $n\in\mathbb{N}$, de tal manera que $f\left(n\right)$, la respuesta al problema asociado a $n$, se comporta de forma azarosa por pequeño $n$, pero después puede ser dada en términos de una forma cerrada de expresión para suficientemente grande $n$? Hay nada que sugiera que los difíciles problemas de combinatoria que se han estudiado, pero de la que poco se sabe, puede mostrar este tipo de regularidad?
Por último, existen resultados en la lógica matemática, teoría de conjuntos, o la prueba de la teoría, de la que soy consciente, que hacen que mi pregunta trivial o tonto?
Agradecería cualquier ayuda con esta pregunta, que puede ser dado. Como alguien con un buen fondo en la combinatoria, pero no profundo conocimiento de la lógica o de la teoría de conjuntos, no sé por dónde empezar con este.
Edit:(En respuesta a un comentario de Qiaochu Yuan) $n$ no necesita ser el tamaño de $X$. Espero que este ejemplo debe aclarar lo que estoy tratando de conseguir en. Considere el problema de la enumeración de las permutaciones de los elementos de un conjunto finito $X$ de cardinalidad $n$. Este problema puede ser lanzado como el siguiente problema.
Enumerar los elementos de $X^n$, $\left(x_0,\ldots ,x_{n-1}\right)$, para que $x_i = x_j$ si y sólo si $i = j$. El problema tiene solución $n!$, que puede o no puede considerarse cerrado, dependiendo de lo que entendemos por "bien conocido" en Knuth de la definición. La respuesta a este problema es que sólo depende de el tamaño de $X$, no en la interpretación de lo que los elementos que podría ser. En un sentido, los problemas de esta manera se puede decir que la escala natural con $n$. Parte de mi pregunta es proporcionar una definición rigurosa de lo que quiero decir con escala natural.
