How can I generate this pattern?

83 Views Asked by At

I've been working on a problem (full problem at the bottom) and as a result I've generated some binary matrices with a peculiar pattern. Here is the pattern for $n=29$ (the largest $n$ before my image editor craps out). A black pixel represents a $1$ and a white pizel represents a $0$.

n = 29

These matrices are generated with the following method.

Given $n$ as input:

First we generate all the collection, $C$, of lists consisting of $2$ and $3$ that sum to $n$ (in dictionary order). For example if $n$ is $8$ then our collection is $[[2,2,2,2],[2,3,3],[3,2,3],[3,3,2]]$.

Or matrix $M(n)$ is then defined as

$$ M(n)_{i,j} = \begin{cases}0 & \exists x,y\in\mathbb{N}: \sum(\mathrm{take}(x)(C_i)) = \sum(\mathrm{take}(y)(C_j))\\1 & \mathrm{otherwise}\end{cases} $$

Here is some Haskell code that generates these matrices:

rowsOf (-1) = [[]]
rowsOf 0 = [[]] : rowsOf (-1)
rowsOf 1 = [] : rowsOf 0
rowsOf n
  | l <- rowsOf $ n-1 = ((map (3:) $ l!!2) ++ (map (2:) $ l!!1)) : l

partialSums = init.tail.scanl(+)0

adjacencyMatrix n = do
  a <- rows
  pure $ do
    b <- rows
    pure $ if all (`notElem` partialSums a) $ partialSums b
             then 1
             else 0
  where
    rows = head $ rowsOf n

Try it online!

From here my question is is this a known pattern? It is rather reminiscent of the Serpinski gasket. Is there a faster way to generate these matrices other than the brute force method shown above?


Original Problem

I saw this challenge on code-golf (based on a now deleted SO question) a little while ago and I have been working on a solution to it using an transformation matrix approach.

The question is as follows:

Given a width $M$ and a height $N$, write a program that outputs how many unique ways an $M\times N$ rectangle can be filled by $2\times 1$ and $3\times 1$ tiles given these constraints.

  1. All tiles stay within their row (ie they are all horizontal).
  2. Between every two adjacent rows tiles should not be aligned, except on the two ends.

In this problem the each row and column represents a way to fill a single size $M$ row. And an element indicates whether those two rows can be places next to each other in the final project without violating rule 2. If I had such a matrix I could use it as a transition matrix and find the desired result very quickly with matrix composition.