6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Geoffrey Critzer Jun 27 '15 at 23:28
  • 1
    $\begingroup$ @GeoffreyCritzer: Yes, you can easily verify that. The first symbol is the multinomial coefficient. $\endgroup$ – Hans Jun 29 '15 at 4:34
1
$\begingroup$

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*}

We finally obtain from (1) \begin{align*} f(s;&z_g,z_r,z_w)\\ &=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\\ &=\frac{1}{1-(z_g+z_r+z_w)s+\frac{z_gz_r(1-(z_g+z_rs))s^2}{1-z_gz_rs}}\\ &=\frac{1-z_gz_rs^2}{1-(z_g+z_r+z_w)s+z_gz_rs^2+z_gz_rz_ws^3}\tag{4}\\ \\ &=1+(z_g+z_r+z_w)s+(z_g^2+z_r^2+z_w^2+2z_gw+2z_rw)s^2\\ &\qquad+(z_g^3+z_r^3+z_w^3+3z_g^2z_w+3z_gz_w^2+3z_r^2z_w+3z_rz_w^2+2z_gz_rz_w)s^3\\ &\qquad+(z_g^4+z_r^4+z_w^4+2z_g^2z_rz_w+6z_gz_rz_w^2+2z_gz_r^2z_w\\ &\qquad\qquad+4z_g^3z_w+6z_g^2z_w^2+4z_gz_w^3+4z_r^3z_w+6z_r^2z_w^2+4z_rz_w^3)s^4+\cdots\tag{5} \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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Hans Sep 14 '16 at 0:14
  • $\begingroup$ @Hans: You're welcome! Enjoy! :-) $\endgroup$ – Markus Scheuer Sep 14 '16 at 6:27
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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}$. $\endgroup$ – Hans Jun 30 '15 at 6:14
  • $\begingroup$ 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). $\endgroup$ – Hans Jun 30 '15 at 6:15
  • $\begingroup$ 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. $\endgroup$ – gar Jun 30 '15 at 14:12
  • $\begingroup$ 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? $\endgroup$ – Hans Jun 30 '15 at 17:02
  • $\begingroup$ 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. $\endgroup$ – gar Jul 1 '15 at 16:57
-1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Hans Jun 30 '15 at 6:06
  • 1
    $\begingroup$ Could you please write out your logic derivation clearly so that people can verify it? $\endgroup$ – Hans Jun 30 '15 at 6:06
  • $\begingroup$ Yes, my apologies. I edited the answer to make it a bit better. I agree that is not a good answer to your question. $\endgroup$ – Geoffrey Critzer Jul 2 '15 at 10:40
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Hans Jul 2 '15 at 16:00
  • 1
    $\begingroup$ 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. $\endgroup$ – Hans Jul 2 '15 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.