# No Adjacency Combinatorics Problem via Generating Function

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?

• I am trying to follow your count. When you say there are (W + 1; r,g) combinations (or ways to designate non-overlappingly r slots for red and g slots for green), does this mean (W + 1,r)*(W + 1 - r,g) Commented Jun 27, 2015 at 23:28
• @GeoffreyCritzer: Yes, you can easily verify that. The first symbol is the multinomial coefficient.
– Hans
Commented Jun 29, 2015 at 4:34

(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)

• This graphical and matrix method looks very intriguing. However, the description has left me puzzled. I understand your recursion equation. However, it is not clear how that figures in the derivation of the generating function. Or are you presenting it as a second method of deriving the generating function or simply a recursion solution? Are you multiplying the recursion by $x^wy^rz^g$ and summing over $(w,r,g)$ to obtain the generating function? But if so, this does not seem to gel with the matrix $A$ and the expansion of $(I-xA)^{-1}$.
– Hans
Commented Jun 30, 2015 at 6:14
• This recursion seems not to figure in the graphical or matrix method. Would you be so kind as to write out the details of the derivation? Thank you very much (for the reference as well).
– Hans
Commented Jun 30, 2015 at 6:15
• The notation in the recurrence is inconsistent, let me modify it. I took w,g and r as formal variables in the matrix. The W indicates that the current card is white, and the next card can be any color. But if it is G or R, the next card can't be R or G, so, the corresponding entries are 0.
– gar
Commented Jun 30, 2015 at 14:12
• The modified notation in recursion equation is better. However, you did not understand my question. I have stated that "I understand your recursion equation". My question is that I do not see the connection between this recursion and the rest of your formulation in graphs and the resolvent of $A$, i.e., $(I-xA)^{-1}$. Could you please write out the derivation of the graphical and matrix representation and the subsequent generating function in details?
– Hans
Commented Jun 30, 2015 at 17:02
• I derived only the matrix. Both the recurrence and the g.f are then obtained from that matrix, for which I used a CAS. What the matrix means is -- if the current card is W and the next card drawn is G, that is allowed, so write 'g'. If the current card is G and the next card drawn is R, it's not allowed, so write 0. Use reasoning along that lines and fill the remaining entries. $I$ is the identity matrix there. I don't have a proof on why that works, but I have found it to be very useful for problems involving patterns.
– gar
Commented Jul 1, 2015 at 16:57

This answer is based upon the Goulden-Jackson Cluster Method.

We consider the set $\mathcal{V}^{\star}$ of words of length $n\geq 0$ built from an alphabet $$\mathcal{V}=\{g,r,w\}$$ and the set $B=\{gr,rg\}$ of bad words, which are not allowed to be part of the words we are looking for. We derive a generating function $f(s)$ with the coefficient of $s^n$ being the number of wanted words of length $n$.

To ease reading we derive at first a generating function $f(s)$ which provides the number of valid words of length $n$ and then we do a refinement and derive a function $f(s;z_g,z_r,z_w)$ which also keeps track of the characters.

Introduction

According to the paper (p.7) the generating function $f(s)$ is \begin{align*} f(s)=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\tag{1} \end{align*} with $d=|\mathcal{V}|=3$, the size of the alphabet and $\mathcal{C}$ the weight-numerator with \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[gr])+\text{weight}(\mathcal{C}[rg])\tag{2} \end{align*}

We calculate according to the paper \begin{align*} \text{weight}(\mathcal{C}[gr])&=-s^2-\text{weight}(\mathcal{C}[rg])s\tag{3}\\ \text{weight}(\mathcal{C}[rg])&=-s^2-\text{weight}(\mathcal{C}[gr])s\\ \end{align*} and get

\begin{align*} \text{weight}(\mathcal{C}[gr])=\text{weight}(\mathcal{C}[rg])=-\frac{s^2}{1+s} \end{align*}

It follows \begin{align*} f(s)&=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\\ &=\frac{1}{1-3s+2\frac{s^2}{1+s}}\\ &=\frac{1+s}{1-2s-s^2}\\ &=1+3s+7s^2+17s^3+41s^4+99s^5\\ &\qquad+239s^6+577s^7+1393s^8+3363s^9+\cdots \end{align*}

We observe e.g. the coefficient of $s^3$ is $17$ giving the number of all valid words of length $3$. This is in accordance with the number $3^3=27$ of all words of length $3$ and the $10$ invalid words \begin{align*} \{ggr,grg,rgg,grr,rgr,rrg,grw,rgw,wgr,wrg\} \end{align*}

Keeping track of characters

We refine the technique above by keeping track of the characters $g,r$ and $w$. We encode the characters with $z_g,z_r$ and $z_w$ and start with a recalculation of the weights.

We obtain according to (3) \begin{align*} \text{weight}(\mathcal{C}[gr])&=-z_gz_rs^2-\text{weight}(\mathcal{C}[gr])z_rs\\ \text{weight}(\mathcal{C}[rg])&=-z_gz_rs^2-\text{weight}(\mathcal{C}[gr])z_gs\\ \end{align*} and get \begin{align*} \text{weight}(\mathcal{C}[gr])&=-\frac{z_gz_r(1-z_rs)s^2}{1-z_gz_rs}\\ \text{weight}(\mathcal{C}[rg])&=-\frac{z_gz_r(1-z_gs)s^2}{1-z_gz_rs} \end{align*}

It follows according to (2)

\begin{align*} \text{weight}(\mathcal{C})&=\text{weight}(\mathcal{C}[gr])+\text{weight}(\mathcal{C}[rg])\\ &=-\frac{z_gz_r(1-z_rs)s^2}{1-z_gz_rs}-\frac{z_gz_r(1-z_gs)s^2}{1-z_gz_rs}\\ &=-\frac{z_gz_r(1-(z_g+z_rs))s^2}{1-z_gz_rs}\\ \end{align*}

The expansion up to $s^4$ was calculated with the help of Wolfram Alpha. When checking e.g. the coefficient of $s^3$ we see the $17$ valid words in detail. The correspondence is \begin{align*} z_g^3&\qquad ggg\\ z_r^3&\qquad rrr\\ z_w^3&\qquad www\\ 3z_g^2z_w&\qquad ggw,gwg,wgg\\ 3z_gz_w^2&\qquad gww,wgw,wwg\\ 3z_r^2z_w&\qquad rrw,rwr,wrr\\ 3z_rz_w^2&\qquad rww,wrw,wwr\\ 2z_gz_rz_w&\qquad gwr,rwg \end{align*}

Note:

• The refined technique of keeping track of letters is presented e.g. in Generalisations of the Goulden-Jackson Cluster Method by E.J. Kupin and D.S. Yuster.

• The generating function $f(s;z_g,z_r,z_w)$ in the representation (4) corresponds with the result $G(x)$ of @gar.

• Wow, super! Thank you very much for the answer and the references. I do not have time now, but will come back to go through the answer and the papers carefully.
– Hans
Commented Sep 14, 2016 at 0:14
• @Hans: You're welcome! Enjoy! :-) Commented Sep 14, 2016 at 6:27

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

• I think I know what you are attempting to do with the system of generating equations. However, your writing makes your answer enigmatic. In the first paragraph, how does the coefficient relate to the combination sought? I suppose the second paragraph is a Mathematica code. It would be better to write the mathematics in LaTeX format that everyone on this site understands. It is confusing to use some specific computer scripting language without even noting what it is. You can always put your code in a block after clearly stating what it is.
– Hans
Commented Jun 30, 2015 at 6:06
• Could you please write out your logic derivation clearly so that people can verify it?
– Hans
Commented Jun 30, 2015 at 6:06
• Yes, my apologies. I edited the answer to make it a bit better. I agree that is not a good answer to your question. Commented Jul 2, 2015 at 10:40
• Thanks for the edit. Are you answering my question or some other question? If it is the latter case, could you please specify what question you are trying to solve? Could you please denote carefully what you mean by "for the number of length n valid arrangements that have exactly k white cards"? Do you mean the total number of cards is $n$ with $k$ white cards within? Are you not going to specify the number of red and green cards? What do you mean by valid? How are there quantities related to the coefficients of your bivariate generating function? Same questions for $a(x,y)$ and $b(x,y)$.
– Hans
Commented Jul 2, 2015 at 16:00
• You say your answer does not answer my question. Could you please state exactly what question you are answering? "The coefficient of y^k*x^n is the number of valid arrangements" is wrong. By your definition of valid arrangement, it is a function of the number of red and green card. Yet you acknowledge "c(x,y) does not tell us anything about the number of red and green cards in the arrangements (other than that the number of red or green cards is n - k). " So obviously you are concluding the number of valid arrangement does NOT depend on the numbers of the red and green cards, without a proof.
– Hans
Commented Jul 2, 2015 at 18:14