No Adjacency Combinatorics Problem via Generating Function

Question

I would like to find the generating function solution for the following combinatorics/probability problem. I have a combinatorial solution and the generating function deduced thereof. But I can not fathom the direct interpretation of it. I would like to reverse the current solving process and directly deduce the following or some other generating function, then get the relevant coefficient as the solution.

In a stack of $W$ white cards, $G$ green cards and $R$ red cards, what is the number of arrangement for no green card is next to a red card?

One solution is to view the $W$ white cards as dividers and leaving $W+1$ slots in between them together with both ends. For each $r\in \{1,2,\dots,R\}$ and $g\in\{1,2,\dots, G\}$, designate non-overlappingly $r$ slots for inserting the red cards and $g$ slots for the green cards. There are ${W+1\choose r,g}$ combinations. For each of these combinations, we insert $R$ red cards into the previously designated $r$ red slots, and there are ${R-1\choose r-1}$ ways of insertion. Do the same for the $g$ green cards and there are ${G-1\choose g-1}$ ways of insertion. Multiplying them and summing over $r$ and $g$, we arrive at the desired total number of arrangements:

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

But this is the coefficient of $x^Ry^G$ in $(1+x+y)^{W+1}(1+x)^{R-1}(1+y)^{G-1}$.

Now how do I deduce this generating function directly from the problem?

Answer 1

(The notations are slightly changed here)

We may use a directed graph for such pattern avoiding problems.

Write the matrix as

\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$ are the states to indicate the three colors and $w,g,r$ are the formal variables to indicate the colors.

To obtain the recurrence formula, find the characteristic polynomial,

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

If we indicate $F(a,b,c)$ as the number of ways to arrange the cards, where a,b,c are the number of white, green and red cards respectively, then $$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)$$ and set the necessary boundary conditions

To obtain the generating function, find $$\left(I-x\, A\right)^{-1}$$ Each entry will have a g.f. for that entry, and we require the sum of the first row, which is

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

If there are $n=a+b+c$ cards in total, find $[x^n]$ and find the required $[w^a\, g^b\, r^c]$

Richard Stanley's "Enumerative combinatorics" discusses such methods (transfer matrices)

Answer 2

This is not an answer to the question but some of this information may help. Lets call a permutation of n (white green or red) cards where no red card is adjacent to a green card a valid arrangement. The bivariate generating function (b.g.f.) for the number of length n valid arrangements that have exactly k white cards is : c(x,y) = $-((1 + x)/(-1 + x + x y + x^2 y))$. The coefficient of y^k*x^n is the number of valid arrangements having a total of n cards where exactly k of the cards are white. c(x,y) does not tell us anything about the number of red and greeen cards in the arrangements (other than that the number of red or green cards is n - k).

I solved this system of equations: a(x, y) == y x a(x, y) + y x b(x, y) and b(x, y) == 1 + x + x b(x, y) + 2 x a(x, y). I derived these equations directly (i.e. via the symbolic method) from the properties of such arrangements. a(x,y) is the b.g.f. for valid words that start with a white card. b(x,y) counts the valid words that are empty or start with a red card or start with a green card.The generating function c(x,y) = a(x,y) + b(x,y).

The first few rows of the triangle are:

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;

This is Sloane's OEIS A113413.

Also interesting is if you let W = R = G then you get the sequence that starts: 2, 12, 92, 780, 7002, 65226, 623576, 6077196,... which is A103882