The Barcode Sequence

The Barcode Sequence

The broad remit of the UK Mathematics Trust (www.ukmt.org.uk) is ‘to advance the education of children and young people in mathematics’. The main thrust of its activities involves the organisation of mathematical competitions of various kinds together with the selection and training of the British team for the annual International Mathematical Olympiad (IMO). The IMA supports the UKMT’s Mathematical Olympiad activities through its Education Grants.

On 2 December 2016, students sat the Senior Kangaroo paper which ‘allows students in the UK to test themselves on questions set for the best school-aged mathematicians from across Europe and beyond’ (from the rubric). Question 20 caught the eye of the author (see https://www.ukmt.org.uk/pdfs/SK16AllPages.pdf).

the-barcode-sequence-figure-1A barcode of the type shown in the two examples is composed of alternate strips of black and white, where the leftmost and rightmost strips are always black. Each strip (of either colour) has a width of 1 or 2. The total width of the barcode is 12. The barcodes are always read from left to right. How many distinct barcodes are possible?

This was one of 20 questions on the 1-hour long paper and the best of the students might well have found the recurrence formula \eqref{eq:1} below.

Suppose B(n) represents the number of barcodes of width n. A recurrence relation is readily derivable. The black ends can be of three types:

  1. Each of width 2 (1 case).
  2. One of width 2 and the other of width 1 (2 cases).
  3. Each of width 1 (1 case).

In case (a), for example, if we strip away the two (black) bars at the ends then we have barcodes of width 4 less than the original except that these are embraced by two white strips. Simply imagine, now, swapping black with white and white with black. Taking into account (a), (b) and (c), we have

(1)   \begin{equation*} B(n + 4) = B(n) + 2B(n + 1) + B(n + 2). \end{equation*}

If we take B(1) = B(2) = B(3) = 1, B(4) = 3, then B(5) = 4, B(6) = 6, \ldots. Table 1 shows the initial values of the ‘standard’ Fibonacci and barcode sequences. That there is a relationship between B(n) and F(n + 1) is obvious.

the-barcode-sequence-table-1
Table 1

There is a model for generating Fibonacci numbers. Consider any positive integer n + 2 created by adding ones and twos where order is relevant. If F(n + 2) represents the number of ways of doing this then F(n + 2) = F(n + 1) + F(n), since F(n + 2) can be divided into two sets, those ending in a 1 and the others ending in a 2. Clearly F(1) = 1, F(2) = 2. (The model omits the first 1 from the standard sequence. To accommodate this see the adjustment in Table 1.) We now derive an explicit formula for B(n).

The auxiliary equation for (1) is x^4 = x^2 + 2x + 1, so x^2 = \pm (x + 1). Hence x^2 + x + 1 = 0 or x^2 - x - 1 = 0. The first has solutions \omega and 1/\omega, where these represent the complex cube roots of unity. The second has solutions g and (-1/g) where g is the golden mean. So we have

    \[ B(n) = Ag^n + B{\left(\frac{-1}{g}\right)}^n + C\omega^n + D\omega^{-n}. \]

For n = 1,

(2)   \begin{equation*} 1 = Ag - \frac{B}{g} + C\omega + D\omega^2. \end{equation*}

For n = 2,

(3)   \begin{equation*} 1 = Ag^2 + \frac{B}{g^2} + C\omega^2 + D\omega. \end{equation*}

For n = 3,

(4)   \begin{equation*} 1 = Ag^3 - \frac{B}{g^3} + C + D. \end{equation*}

For n = 4,

(5)   \begin{equation*} 3 = Ag^4 + \frac{B}{g^4} + C\omega + D\omega^2. \end{equation*}

Adding (2), (3) and (4),

    \begin{equation*} 3 = A(g + g^2 + g^3) + \frac{B}{g^3}(-g^2 + g - 1) \end{equation*}

and adding (3), (4) and (5,

    \begin{equation*} 5 = A(g^2 + g^3 + g^4) + \frac{B}{g^4}(g^2 - g + 1). \end{equation*}

We leave the somewhat tedious algebra to tease out A and B to the reader. We arrive at

    \[ B(n) = \frac{1}{2\sqrt{5}}\left(g^{n+1} - {\left(\frac{-1}{g}\right)}^{n+1}\right) + C\omega^n + D\omega^{-n}. \]

Now

    \[ 1 = \frac{1}{2\sqrt{5}}\left(g^2 - \frac{1}{g^2}\right) + C\omega + D\omega^2 \]

and

    \[ 1 = \frac{1}{2\sqrt{5}}\left(g^3 + \frac{1}{g^3}\right) + C\omega^2 + D\omega. \]

These give

    \[ D = \frac{1}{2(\omega^2-1)}, \quad C = -\frac{1}{2\omega(\omega^2-1)}. \]

More manipulation gives

    \[ B(n) = \frac{1}{2\sqrt{5}}\left(g^{n+1} - {\left(-\frac{1}{g}\right)}^{n+1}\right) + \frac{1}{\sqrt{3}}\sin\frac{(2n-1)\pi}{3}. \]

The last term takes the values 1/2, 0, -1/2 in a 3-cycle beginning with n = 1, 2, 3. These observations are confirmed by looking at Table 1.

Now

    \[ F(n + 1) = \frac{1}{\sqrt{5}}\left(g^{n+1} -{\left(-\frac{1}{g}\right)}^{n+1}\right). \]

This is Binet’s formula derivable from the auxiliary equation x^2 - x - 1 = 0.

Clearly

    \[ 2B(n) - F(n + 1) = \frac{2}{\sqrt{3}}\sin\frac{(2n-1)\pi}{3}. \]

From this we can deduce the near Fibonacci sequence for B(n), namely

(6)   \begin{equation*} B(n + 2) = B(n + 1) + B(n) - \frac{2}{\sqrt{3}}\sin\frac{2n\pi}{3}. \end{equation*}

Finally (6) can be established by mathematical induction. Start with two cases of (6) for n = k, k + 1 and combine with (1).

Graham Hoare CMath FIMA

Image credit: Barcode by Nico Kaiser / Flickr / CC BY-NC 2.0

Reproduced from Mathematics Today, February 2018

Download the article, The Barcode Sequence (pdf)

Related Posts

Published

© 2024 IMA. All Rights Reserved. Site by Measured Designs.