No Adyacencia Combinatoria Problema a través de la Generación de la Función

Question

Me gustaría encontrar a la generación de la función solución de la siguiente combinatoria/problemas de probabilidad. Tengo una combinatoria de la solución y la generación de la función deducida de los mismos. Pero no puedo entender la interpretación directa de la misma. Me gustaría revertir el actual proceso de resolución de problemas y directamente deducir la siguiente o algunos otros de generación de función, a continuación, obtener el correspondiente coeficiente como la solución.

En una pila de $W$ tarjetas blancas, $G$ verde y tarjetas de $R$ tarjetas rojas, ¿cuál es el número de acuerdo de ninguna tarjeta verde junto a una tarjeta roja?

Una solución es para ver el $W$ tarjetas blancas como divisores y dejando $W+1$ de los espacios entre ellos, junto con los dos extremos. Para cada una de las $r\in \{1,2,\dots,R\}$$g\in\{1,2,\dots, G\}$, designar no overlappingly $r$ ranuras para la colocación de las tarjetas rojas y $g$ ranuras para las tarjetas verdes. Hay ${W+1\choose r,g}$ combinaciones. Para cada una de estas combinaciones, se inserte $R$ tarjetas rojas en los previamente designados $r$ rojo ranuras, y hay ${R-1\choose r-1}$ formas de inserción. Hacer lo mismo para el $g$ tarjetas verdes y hay ${G-1\choose g-1}$ formas de inserción. La multiplicación de ellos y sumando más de $r$$g$, llegamos a la deseada número total de arreglos:

$$\sum_{r=1}^R\sum_{g=1}^G{W+1\choose r,g}{R-1\choose R-r}{G-1\choose G-g}.$$

Pero este es el coeficiente de $x^Ry^G$$(1+x+y)^{W+1}(1+x)^{R-1}(1+y)^{G-1}$.

Ahora ¿cómo puedo deducir de la generación de esta función directamente desde el problema?

Answer 1

(Las notaciones son ligeramente cambiado aquí)

Podemos utilizar un gráfico dirigido por tales patrón de evitar problemas.

Escribir la matriz como

\begin{align*} A = \left(\begin{array}{r|rrr} & W & G & R \\ \hline W & w & g & r \\ G & w & g & 0 \\ R & w & 0 & r \\ \end{array}\right) \end{align*}

$W,G,R$ son los estados para indicar los tres colores y $w,g,r$ son las variables formales para indicar los colores.

Para obtener la fórmula de recurrencia, hallar el polinomio característico,

$$x^{3} - \left(g + r + w\right) x^{2} + g r x + g r w = 0$$

Si nos indique el $F(a,b,c)$ a medida que el número de maneras de organizar las tarjetas, donde a,b,c son el número de blanco, verde y rojo de las tarjetas, respectivamente, entonces $$F(a,b,c) = F(a-1,b,c)+F(a,b-1,c)+F(a,b,c-1)-F(a,b-1,c-1)-F(a-1,b-1,c-1)$$ y establecer las necesarias condiciones de contorno

Para obtener la generación de función, encontrar $$\left(I-x\, A\right)^{-1}$$ Cada entrada tiene un g.f. para que la entrada, y exigimos a la suma de la primera fila, que es

$$G(x) =\frac{1-g\, r\, x^{2}}{1\, -\, {\left(g\, +\, r\, +\, w\right)+\, g\, r\, x^{2}+g\, r\, w\, x^{3}}}$$

Si hay $n=a+b+c$ tarjetas en total, encontrar $[x^n]$ y encontrar el requerido $[w^a\, g^b\, r^c]$

Richard Stanley "la combinatoria Enumerativa" trata de los métodos de transferencia de archivos (matrices)

Answer 2

Esto no es una respuesta a la pregunta, pero parte de esta información puede ayudar. Permite llamar a una permutación de n (blanco, verde o rojo) tarjetas donde no hay tarjeta roja es adyacente a una tarjeta de residencia válida de acuerdo. La bivariante de generación de función b.g.f.) para el número de longitud n válidos los acuerdos que tienen exactamente k tarjetas blancas es : c(x,y) = $-((1 + x)/(-1 + x + x y + x^2 y))$. El coeficiente de y^k*x^n es el número de arreglos que tiene un total de n cartas donde exactamente k de las tarjetas son de color blanco. c(x,y) no nos dice nada acerca de la cantidad de glóbulos rojos y greeen tarjetas en los arreglos (aparte de que el número de red o tarjetas de residencia es n - k).

He resuelto este sistema de ecuaciones: (x, y) == y x a(x, y) + y x b(x, y) y b(x, y) == 1 + x + x b(x, y) + 2 x(x, y). Yo derivados de estas ecuaciones directamente (es decir, mediante el método simbólico) de las propiedades de este tipo de acuerdos. a(x,y) es la b.g.f. por válidas las palabras que empiezan con una tarjeta blanca. b(x,y) cuenta la validez de las palabras que están vacíos o empezar con una tarjeta roja o empezar con una tarjeta verde.La generación de la función c(x,y) = a(x,y) + b(x,y).

Las primeras filas del triángulo son:

1;

2, 1;

2, 4, 1;

2, 8, 6, 1;

2, 12, 18, 8, 1;

2, 16, 38, 32, 10, 1;

2, 20, 66, 88, 50, 12, 1;

Este es Sloane del OEIS A113413.

También es interesante si vamos a W = R = G entonces se obtiene la secuencia que comienza: 2, 12, 92, 780, 7002, 65226, 623576, 6077196,... que es A103882