Recibiendo el nombre de problemas combinatorios

Question

Voy a menudo me encuentro con algún problema combinatorio que, obviamente, se ha estudiado antes. Por ejemplo, "Encontrar el conjunto más pequeño(s) de enteros positivos tal que cada número entero de 1 a n es la suma de dos elementos del conjunto." Sin ser un experto en la combinatoria, ¿hay alguna manera de averiguar el nombre de un problema que pasa en la literatura, por ejemplo en una especie de catálogo? Googlear y tácticas similares, no parecen ser muy útil aquí, como la mayoría de las preguntas de este tipo constan de las palabras ", más pequeño, de tal manera que, ..." en varias ocasiones -- generalmente no hay una única palabra o frase a aferrarse a la. Por ejemplo, cuando traté de Google el problema anterior, recibí el subconjunto suma problema (dado un conjunto, determinar si algún subconjunto de sumas a cero) y el problema de la mochila (dado un conjunto de objetos con pesos específicos y valores, encontrar el más valioso subconjunto debajo de un determinado peso total), que no tienen nada que ver con lo que realmente estaba buscando.

Yo no estoy buscando el nombre de el problema anterior, en particular (aunque no estaría mal si alguien lo sabe), sino que algunos limpio manera de ver las cosas por mi misma. Hace un catálogo de existir?

EDIT: Mi idea básica aquí es que un gran número de problemas de combinatoria caer en algunas básica, MADLIBS-patrones de estilo, por ejemplo:

Opciones de $m$ elementos de ___, (con|sin) de repetición, (con|sin) ordenar, la satisfacción de la restricción adicional de ____.

(Rutas o circuitos) a través de un (dirigido|grafo), (vértice|edge) grafo ponderado, que visita cada uno (edge|vertex), de tal manera que el peso total es de (máxima|mínima), y tal que _.

Un índice en el que se enumeran las cosas de esta manera podrían ser útiles para los no expertos.

Answer 1

Una forma es calcular los términos pequeño $n$ (en tu ejemplo el tamaño del conjunto más pequeño con su propiedad deseada) y luego estos buscar en la Enciclopedia on-line de secuencias de enteros

Answer 2

No es el doce veces la forma, que es una clasificación de varios de los más comunes problemas de combinatoria a lo largo de las líneas que se preguntan acerca de la edición. Si usted tiene $n$ bolas para colocar en el $x$ cajas, usted puede tener las bolas marcadas o no, las casillas marcadas o no, y si la asignación de pelotas, cajas, no tiene restricciones (la elección de las cajas "con el reemplazo," en algunos contextos), es inyectiva (no más de un balón por la caja, o la elección de las cajas "sin reemplazo," en algunos contextos), o es surjective (al menos una bola por caja). Teniendo en cuenta todas estas posibilidades le da las doce opciones en el nombre de la clasificación.

Véase también Richard Stanley Combinatoria Enumerativa, Vol. I, donde se analiza en detalle.

---

Añadido (en respuesta a la OP de la solicitud para la generalización): p. 88 de Stanley texto (que se puede descargar directamente desde su sitio utilizando el enlace de arriba) dice, "Hay muchas posibles generalizaciones de la Twelvefold Manera y cada una de sus entradas". Entonces va a hablar de uno de ellos. En las notas (p. 107) en el capítulo en el que el Twelvefold Manera que parece Stanley también se dice, "Una extensión de la Twelvefold Manera de un 'Treinta Manera (y la sugerencia de incluso más entradas) se debe a R. Proctor." Seguimiento de la referencia conduce a Proctor en su artículo "Vamos a Ampliar la Rota Twelvefold Manera De Contar las Particiones!", el que no estoy familiarizado con, pero que sin duda parece ser el tipo de cosa que usted está pidiendo.

Answer 3

El nombre que usted no está buscando es "El sello de correos problema", C12 en el Hombre, los Problemas sin resolver En la Teoría de números. "Una forma popular de se refiere al diseño de un conjunto de enteros denominaciones de estampilla, $A_k=\lbrace\,a_1,\dots,a_k\,\rbrace$ $1=a_1\lt a_2\lt\cdots\lt a_k$ a ser utilizadas en los sobres con capacidad para la mayoría de las $h$ sellos, para que todo el entero de las cantidades de los gastos de envío hasta un determinado obligado puede ser colocado. [...] En primer lugar el interés principal estaba en el problema global: dado $h$$k$, encontramos un extremal base $A_k'$ con mayor $h$-rango", es decir, uno que maximiza el entero más pequeño que no puede conseguir. Su problema es el caso de $h=2$. Hay mucha información sobre esto (y muchas, muchas otras combinatoria, teoría de números problemas) en el libro.