## Zimin Words and Bifixes

One of the earliest contributions to the On-Line Encyclopedia of Integer Sequences (OEIS) was a family sequences counting the number of words that begin (or don’t begin) with a palindrome:

• Let $$f_k(n)$$ be the number of strings of length $$n$$ over a $$k$$-letter alphabet that begin with a nontrivial palindrome” for various values of $$k$$.
• Let $$g_k(n)$$ be the number of strings of length n over a $$k$$-letter alphabet that do not begin with a nontrivial palindrome.
• Number of binary strings of length $$n$$ that begin with an odd-length palindrome. (A254128)

(If I had known better, I would have published fewer sequences in favor of a table, and I would have requested contiguous blocks of A-numbers.)

I must have written some Python code to compute some small terms of this sequence, and I knew that $$g_k(n) = k^n – f_k(n)$$, but I remember being at in my friend Q’s bedroom when the recursion hit me for $$f_k(n)$$: $$f_k(n) = kf_k(n-1) + k^{\lceil n/2 \rceil} – f_k\big(\lceil \frac n 2 \rceil \big)$$

## “Bifix-free” words

One sequence that I didn’t add to the OEIS was the “Number of binary strings of length n that begin with an even-length palindrome”—that’s because this was already in the Encyclopedia under a different name:

A094536: Number of binary words of length n that are not “bifix-free”.

0, 0, 2, 4, 10, 20, 44, 88, 182, 364, 740, 1480, 2980, 5960, …

A “bifix” is a shared prefix and suffix, so a “bifix-free” word is one such that all prefixes are different from all suffixes. More concretely, if the word is $$\alpha_1\alpha_2 \dots \alpha_n$$, then $$(\alpha_1, \alpha_2, \dots, \alpha_k) \neq (\alpha_{n-k+1},\alpha_{n-k+2},\dots,\alpha_n)$$ for all $$k \geq 1$$.

The reason why the number of binary words of length $$n$$ that begin with an even length palindrome is equal to the number of binary words of length $$n$$ that have a bifix is because we have a bijection between the two sets. In particular, find the shortest palindromic prefix, cut it in half, and stick the first half at the end of the word, backward. I’ve asked for a better bijection on Math Stack Exchange, so if you have any ideas, please share them with me!

In 2019–2020, Daniel Gabric, Jeffrey Shallit wrote a paper closely related to this called Borders, Palindrome Prefixes, and Square Prefixes.

## Zimin words

A Zimin word can be defined recursively, but I think it’s most suggestive to see some examples:

• $$Z_1 = A$$
• $$Z_2 = ABA$$
• $$Z_3 = ABACABA$$
• $$Z_4 = ABACABADABACABA$$
• $$Z_n = Z_{n-1} X Z_{n-1}$$

All Zimin words $$Z_n$$ are examples of “unavoidable patterns”, because every sufficiently long string with letters in any finite alphabet contains a substring that matches the $$Z_n$$ pattern.

For example the word $$0100010010111000100111000111001$$ contains a substring that matches the Zimin word $$Z_3$$. Namely, let $$A = 100$$, $$B = 0$$, and $$C = 1011$$, visualized here with each $$A$$ emboldened: $$0(\mathbf{100}\,0\,\mathbf{100}\,1011\,\mathbf{100}\,0\,\mathbf{100})111000111001$$.

I’ve written a Ruby script that generates a random string of length 29 and uses a regular expression to find the first instance of a substring matching the pattern $$Z_3 = ABACABA$$. You can run it on TIO, the impressive (and free!) tool from Dennis Mitchell.

# Randomly generates a binary string of length 29.
random_string = 29.times.map { [0,1].sample }.join("")
p random_string
# Finds the first Zimin word ABACABA
p random_string.scan(/(.+)(.+)\1(.+)\1\2\1/)[0]
# Pattern:             A   B   A C   A B A


Why 29? Because all binary words of length 29 contain the pattern $$Z_3 = ABACABA$$. However, Joshua Cooper and Danny Rorabaugh’s paper provides 48 words of length 28 that avoid that pattern (these and their reversals):

1100000010010011011011111100
1100000010010011111101101100
1100000010101100110011111100
1100000010101111110011001100
1100000011001100101011111100
1100000011001100111111010100
1100000011011010010011111100
1100000011011011111100100100
1100000011111100100101101100
1100000011111100110011010100
1100000011111101010011001100
1100000011111101101100100100

1100100100000011011011111100
1100100100000011111101101100
1100100101101100000011111100
1100110011000000101011111100
1100110011000000111111010100
1100110011010100000011111100
1101010000001100110011111100
1101010000001111110011001100
1101010011001100000011111100
1101101100000010010011111100
1101101100000011111100100100
1101101100100100000011111100

## The Zimin Word $$Z_2 = ABA$$ and Bifixes

The number of Zimin words of length $$n$$ that match the pattern ABA is equal to the number of of words that begin with an odd-length palindrome. Analogously, the number of words with a bifix is equal to the number of words that begin with an even-length palindrome. The number of these agree when $$n$$ is odd.

I’ve added OEIS sequences A342510A342512 which relate to how numbers viewed as binary strings avoid—or fail to avoid—Zimin words. I asked users to implement this on Code Golf Stack Exchange.

## My Favorite Sequences: A263135

This is the fourth in my installment of My Favorite Sequences. This post discusses sequence A263135 which counts penny-to-penny connections among $$n$$ pennies on the vertices of a hexagonal grid. I published this sequence in October 2015 when I was thinking about hexagonal-grid analogs to the “Not Equal” grid. The square-grid analog of this sequence is A123663.

## A263135: Placing Pennies

The sequences A047932 and A263135 are about placing pennies on a hexagonal grid in such a way that maximizes the number of penny-to-penny contacts, which occurs when you place the pennies in a spiral. A047932, counts the contacts when the pennies are placed on the faces of the grid; A263135 counts the contacts with the pennies placed on the vertices.

While spiral shapes maximize the number of penny-to-penny contacts, there are sometimes non-spiral shapes that have the same number of contacts. For example, in the case of the square grid, there are $$A100092(n)$$ such ways to lay down $$n$$ pennies on the square grid with the maximum number of connections. Problem 108 in my Open Problems Collection asks about generalizing this OEIS sequence to other settings such as the hexagonal grid.

#### Comparing contacts

Notice that the “face” pennies in A047932 can have a maximum of six neighbors, while the “vertex” pennies in A263135 can have a maximum of three. In the limit, most pennies are “interior” pennies with the maximum number of contacts, so $$A047932(n) \sim 3n$$ and $$A263135(n) \sim \frac32n$$.

Looking at the comparative growth rates, it is natural to ask how the number of connections of $$n$$ face pennies compares to the number of connections of $$2n$$ vertex pennies. In October 2015 I made a conjecture on the OEIS that this difference grew like sequence A216256.

Conjecture: For $$n > 0$$, $A263135(2n) – A047932(n) = \lceil\sqrt{3n – 3/4} – 1/2\rceil = A216256(n).$

I believe that the sequence A216256 on the right hand side appears to be the same as the sequence “n appears $$\displaystyle\left\lfloor \frac{2n+1}{3} \right\rfloor$$ times,” but I’d have to crack open my Concrete Mathematics book to prove it.

## Polygons on a “centered $$n$$-gon”

I asked a question on Math Stack Exchange, “When is it possible to find a regular $$k$$-gon in a centered $$n$$-gon“—where “centered $$n$$-gon” refers to the diagram that you get when illustrating central polygonal numbers. These diagrams are one of many possible generalizations of the triangular, square, and centered hexagonal grids. (Although it’s worth noting that the centered triangular grid is different from the ordinary triangular grid.)

## A catalog of polytopes and grids

On my OEIS wiki page, I’ve created some tables that show different kinds of polytopes in different kinds of grids. There are quite a number of combinations of polygons/polyhedra and grids that either don’t have an OEIS sequence or that I have been unable to find.

If you’re interested in working on filling in some of the gaps in this table, I’d love it if you let me now! And if you’d like to collaborate or could use help getting started, send me a message on Twitter!

## Parity Bitmaps from the OEIS

My friend Alec Jones and I wrote a Python script that takes a two-dimensional sequence in the On-Line Encyclopedia of Integer Sequences and uses it to create a one-bit-per-pixel (1BPP) “parity bitmaps“. The program is simple: it colors a given pixel is black or white depending on whether the corresponding value is even or odd.

### An Unexpected Fractal

We’ve now run the script on over a thousand sequences, but we still both agree on our favorite: the fractal generated by OEIS sequence A279212.

Fill an array by antidiagonals upwards; in the top left cell enter $$a(0)=1$$; thereafter, in the $$n$$-th cell, enter the sum of the entries of those earlier cells that can be “seen” from that cell.

Notice that in the images below, increasing the rows and columns by a factor of $$2^n$$ seems to increase the “resolution”, because the parity bitmap is self similar at 2x the scale. We still don’t have a good explanation for why we’d expect these images are fractals. If you know, please answer our question about it on Math Stack Exchange. (Alec and I have generated these images up to 16384 × 32768 resolution, roughly 536 megapixels.)

#### The Construction of the Sequence

The sequence is built up by “antidiagonals”, as shown in the GIF below. In the definition, “seen” means every direction a chess queen can move that already has numbers written down (i.e. north, west, northwest, or southwest). That is, look at all of the positions you can move to, add them all up, write that number in your square, move to the next square, and repeat. (The number in cell $$C$$ also counts the number of paths a queen can make from $$C$$ to the northwest corner using only N, NW, W, SW moves.)

(Interestingly, but only tangentially related: Code Golf Stack Exchange User flawr noticed that the number of north/west rook walks is related to the number of ways of partitioning a $$1 \times n$$ grid into triangles.)

## Parity Bitmaps for Other Sequences

It’s worth noting that many sequences are all black, consist of simple repeating patterns, or look like static. However, chess-type constructions, as illustrated by the GIF above, the one above yield images that look like the Sierpiński triangle. (See A132439 and A334017 below, and look at A334016 and A334745 via their OEIS entries.) Look below for a couple other sequences with interesting images too.

I ordered a poster-sized print of the A279212 fractal for Alec, and he framed it in his office.

Some ideas for further exploration: