¿Existen diagramas que muestran la estructura de problemas combinatorios?

Question

De acuerdo a los Principios y Técnicas de Combinatoria, cualquier recuento problema siempre puede descomponerse en sub-problemas que pueden ser resueltos por la suma o multiplicación de los principios.

Esto se vuelve bastante obvio como ejemplos de aumento. Un problema que puede ser dividido en distintos casos hay que añadir los resultados de esos casos, y un problema que puede ser integrado en ordenadas los acontecimientos, las necesidades de multiplicar el número de maneras en las que cada evento puede ocurrir.

Para algunos de los problemas más complicados, la visualización de esta estructura se vuelve difícil. Me estoy imaginando una especie de estructura de tabla o diagrama de árbol. He paginar a través de un par de mis combinatoria de los libros, y no veo nada parecido a lo que estoy pensando.

Hay un método existente de diagramación de la estructura de un recuento problema?

Answer 1

La generación de funciones de codificación el aditivo y el multiplicativo de los principios de uso de la adición y de la multiplicación de los signos. Un $G.F.$ o $e.g.f.$ es -sin duda - un diagrama y no una "función", incluso podemos hacer algo de álgebra a su alrededor. Podemos dibujar los términos en forma vertical utilizando un elogio, o podemos dibujar en un círculo, como lo harían las moléculas de un gas.

Sin embargo :

• Sólo la adición y la multiplicación no es suficiente. Por ejemplo, cuando se cuentan las secuencias binarias que evitar 110, tenemos un $Lin(X+Y-X.X.Y)$ fórmula, donde el signo $-$ tiene una combinatoria significado, es decir, la exclusión de algunos más que no se cuentan las cadenas. También hay una división, algo como $\frac{\{x,x,x,x,x \}}{\{x,x,x\}} = {\{x,x\}}$. También hay una composición y así sucesivamente.

• No es necesariamente más fácil de leer/escribir (exponencial) funciones de generación que acaba de resolver el problema. Los diagramas de obtener torpe muy rápidamente y la combinatoria glamour se desvanece... la lógica Combinatoria no se venden bien.

• Finalmente, la combinatoria de suma y de producto, se revelan con raíces en un (bien dicho antes) desagradable inframundo de los ciclos, permutaciones y grupos de permutaciones.

AGREGAR gracias Gustavo por retroalimentación; la manzana-pera-plátano diagrama es una cita de Kenneth Bogart, 2004, profesor en la Universidad de Dartmouth, quien fue inspirado por Polya. La idea de que GF son diagramas no sólo polinomios es nuevamente inspirada por Polya :