# How many codes are possible?

The line - codes we are looking at consist of black and red lines. These lines can have width 1 or 2. Black and red lines are taking turns, black line, red line, black line, ... The code ends and begins with a black line (width 1 or 2). The width of the full code is 14.

Question:

How many codes are possible ? Give a proof.

Example:

• This is just a normal combinatorics problem. It belongs on math.stackexchange.com, not here. – BlueRaja - Danny Pflughoeft Jun 22 '19 at 20:39

Let $$R(n)$$ be the number of codes of total width $$n$$, so the question asks for $$R(14)$$.

Consider any code that contains at least $$3$$ stripes. You can strip off the last two stripes, and still have a valid code that begins and ends in a black stripe, and conversely any valid code can be extended by appending a red and a black stripe to it. The two stripes can be of width $$\color{red}{1}+1$$, $$\color{red}{1}+2$$, $$\color{red}{2}+1$$, or $$\color{red}{2}+2$$. This means that the $$R(n)$$ satisfies the recurrence relation: $$R(n)=R(n-2)+2R(n-3)+R(n-4)$$ It is fairly obvious that $$R(0)=0\\R(1)=1\\R(2)=1\\R(3)=1\\R(4)=3$$ We can simply extend the sequence by applying the recurrence relation: $$0, 1, 1, 1, 3, 4, 6, 11, 17, 27, 45, 72, 116, 189, 305, 493, 799, ...$$ So $$R(14)=305$$.

Some additional maths: If there were no colours, so that the codes could have any number of stripes, then the sequence would be the Fibonacci numbers. In this case you almost have a Fibonacci sequence too, as each term is at most one away from being the sum of the previous two terms. In fact, $$R(n)=R(n-1)+R(n-2)+c_n$$ where $$c_n$$ is $$-1$$, $$1$$, or $$0$$, when $$n$$ is $$0$$, $$1$$, $$2$$ modulo $$3$$ respectively.
The ratio of successive terms is the golden ratio, just like Fibonacci. If you look at the associated polynomial, $$x^4=x^2+2x+1$$, it has the roots $$\phi$$, $$1/\phi$$, (like Fibonacci) but also the complex roots $$\omega$$ and $$\omega^2$$ which causes those offsets of $$-1$$, $$0$$, and $$1$$.

• Note that the polynomial reduces to (x^2)^2 = (x+1)^2. If the code has n colors in sequence, the characteristic polynomial becomes (x^2)^n = (x+1)^n, providing additional roots. – AxiomaticSystem Jun 30 '19 at 14:11

There are:

$$305$$ ways to do this.

Proof:

Each code belongs to one of the following generating functions.
$$\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}$$ $$\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}$$ $$\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}$$ $$\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}$$

Now:

Each generating function must contain a certain number of $$x^2$$ (regardless of color) to hit a code length of $$14$$. Hence the answer is:
$$\binom{7}{7}+\binom{9}{5}+\binom{11}{3}+\binom{13}{1}=1+126+165+13=305$$

• I have an other solution with a little bit more codes. – Matti Jun 22 '19 at 10:58
• 9; 5 = 126 not 105, if you sum that up correctly then you get the same result as Jaap Scherphuis. – Bodo Thiesen Jun 22 '19 at 14:08