# counting the patterns

We're given N, the length of pattern and 3 letters X, Y, Z. We can fill the pattern using anyone of them with repetitions allowed so that the total number of patterns is $3^N$. A pattern is special if there are three consecutive letters from which one is X, one is Y, and one is Z. For example, XYZXYZ is special, while XXYYZ is not. For a given value of $N(N<30)$, how many patterns are not special?

-
Can be done for smallish $N$ by using Inclusion-Exclusion. But that gets unpleasant quickly. – André Nicolas Mar 14 '12 at 17:06

Let $a(n)$ be the number of non-special patterns of length $n$. It’s convenient to divide these into those that end with two copies of the same letter and those that don’t. Let $a_s(n)$ be the number of non-special patterns of length $n$ that end in two copies of the same letter, and let $a_d(n)$ be the number that don’t. Then $a_s(1)=0$ and $a_d(1)=3$. Moreover, it’s easy to see that $a_s$ and $a_d$ satisfy the following recurrences:

\begin{align*}a_s(n+1)&=a_s(n)+a_d(n)\\ a_d(n+1)&=2a_s(n)+a_d(n)\;. \end{align*}\tag{1}

That is, a non-special pattern of length $n+1$ whose last two letters are the same results from doubling the last last letter of any non-special pattern of length $n$. A non-special pattern of length $n+1$ whose last two letters are not the same can be obtained by adding either of the two non-matching letters to a non-special pattern of length $n$ whose last two letters are the same; but if the pattern of length $n$ does not have identical last two letters, the new letter must be a copy of the penultimate letter. (E.g., if the $n$-pattern ends in $XY$, we must add $X$ if we want a non-special pattern whose last two letters are different.)

It follows from the first recurrence of $(1)$ that $a_s(n+1)=a(n)$, and adding the recurrences yields $a(n+1)=2a(n)+a_s(n)$. Combining these, we see that $$a(n+1)=2a(n)+a(n-1)\;,\tag{2}$$ which is a straightforward linear homogeneous recurrence. Its auxiliary equation is $x^2-2x-1=0$, with roots $\frac12(2\pm\sqrt8)=1\pm\sqrt2$, so the general solution of $(2)$ is $$a(n)=A(1+\sqrt2)^n+B(1-\sqrt2)^n\;.\tag{3}$$

You know that $a(1)=3$ and $a(2)=9$, so you can substitute these into $(3)$ and solve for $A$ and $B$ to get the specific solution that you want. Or, since you’re interested only in $n<30$, you can simply use $(2)$ to calculate the values directly.

-
thanks Brian, I was having a hard time in finding these recurrences and I don't have enough reputation to vote up your answer :( – Bharat Kul Ratan Mar 14 '12 at 17:21
@tendua: No problem. By the way, the technique of breaking the things that you’re counting into subcases is quite often useful, though it isn’t always so easy as it was here to put them back together. – Brian M. Scott Mar 14 '12 at 17:23
I tried the same approach, but you were faster ;-) Moreover, my ecurrence was wrong (and yours was right). – dtldarek Mar 14 '12 at 18:13

Let $A_n$ denote the number of non-special patterns starting with $XX$, and $B_n$ the number of non-special patterns starting with $XY$. Then $A_2 = 1$, $B_2 = 1$ and \begin{align*} A_{n+1} &= A_n + 2B_n, \\ B_{n+1} &= A_n + B_n, \end{align*}

with solution (calculated by Mathematica) being: \begin{align*} \delta = 1+\sqrt{2} && \hat\delta = 1-\sqrt{2} \end{align*} \begin{align*} A_n &= \frac{-1 + \sqrt{2}}{2} \delta^n + \frac{-1 - \sqrt{2}}{2}\hat\delta^n \\ B_n &= \ \frac{4 - \sqrt{2}}{4}\delta^n \ + \frac{2 + \sqrt{2}}{4}\hat\delta^n \end{align*}

It is possible to arrive at those formulas by generating functions, or assuming that $A_n = \alpha a^n+\beta b^n$, similairly for $B_n$ and then trying to solve by substitution of small values of $n$.

Your total result is $3B_n + 3A_n$.

Edit: Corrected the formulae (Brian M. Scott was right).

-

Actually Inclusion-Exclusion is not so bad here, start by considering the number of different gaps when $k$ copies of the forbidden pattern XYZ are placed on a row of $n$ cells. There are $k+1$ possible gaps and they have size zero or more, giving the following formula for the number of gaps: $$[z^{n-3k}]\left(\frac{1}{1-z}\right)^{k+1} = {n-3k+k \choose n-3k} = {n-2k\choose n-3k} = {n-2k\choose k}.$$

It now follows by inspection that the count $q_n$ of patterns that are not special is given by $$q_n = 3^n - \sum_{k=1}^{\lfloor n/3 \rfloor} (-1)^{k+1} {n-2k\choose k} 3^{n-3k} = 3^n + \sum_{k=1}^{\lfloor n/3 \rfloor} (-1)^k {n-2k\choose k} 3^{n-3k} \\ = \sum_{k=0}^{\lfloor n/3 \rfloor} (-1)^k {n-2k\choose k} 3^{n-3k}.$$ In order to get a closed form for this sum introduce the ordinary generating function $$f(z) = \sum_{n\ge 0} q_n z^n = \sum_{n\ge 0} \sum_{k=0}^{\lfloor n/3 \rfloor} (-1)^k {n-2k\choose k} 3^{n-3k} z^n = \sum_{k\ge 0} \sum_{\lfloor n/3 \rfloor\ge k} (-1)^k {n-2k\choose k} 3^{n-3k} z^n \\ = \sum_{k\ge 0} (-1)^k 3^{-3k} \sum_{\lfloor n/3 \rfloor\ge k} {n-2k\choose k} 3^n z^n.$$ Now work on the inner sum to get $$\sum_{n\ge 3k} {n-2k\choose k} 3^n z^n = \sum_{n\ge 0} {n+k\choose k} 3^{n+3k} z^{n+3k} \\= 3^{3k} z^{3k} \sum_{n\ge 0} {n+k\choose n} 3^n z^n = 3^{3k} z^{3k} \left(\frac{1}{1-3z}\right)^{k+1}.$$ Substituting this into the outer sum yields $$f(z) = \sum_{k\ge 0} (-1)^k z^{3k} \left(\frac{1}{1-3z}\right)^{k+1} = \frac{1}{1-3z} \frac{1}{1+z^3/(1-3z)} = \frac{1}{z^3-3z+1}.$$ This does not lead to a simple closed form as the roots of $z^3-3z+1$ are represented by rather involved cubic root formulas. But it produces the following sequence of terms: $$1, 3, 9, 26, 75, 216, 622, 1791, 5157, 14849, 42756, 123111, 354484, 1020696, 2938977,\ldots$$ which points us to OEIS A076264, where a host of additional material may be found, including how to get the asymptotics out of the generating function.

Remark. This does not agree with the results from the other responders but I would take the OEIS entry as strong evidence that we have the correct answer.

A similar calculation can be found at this MSE link.

-