About Warm-ups Problems News

Problem 5

Posted 04/02/2015 and updated 06/20/2015
Refresh the webpage if formulas are not shown correctly.
----------------------
Previous    Next
----------------------

In this problem, we consider the set of all the binary matrices of size `2\times n`, denoted by `\mathcal B_{2,n}`. Suppose `M\in\mathcal B_{2,n}` and `P\in \mathcal B_{2,2}`, we define `mch(P,M)` as the number of occurences of `P` as blocks in `M`. If `mch(P,M)=0`, we say `M` avoids `P`.

For example, `P=[[0,1],[1,1]]\in \mathcal B_{2,2}` and `M=[[0,0,1,1,0,1,0,1],[1,1,1,0,1,1,1,0]]\in \mathcal B_{2,8}`.

We see there are two occurences of `P`: at the second column and fifth column and hence `mch(P,M)=2`.

`a(n)` is the number of elements in `\mathcal B_{2,n}` avoiding `P=[[0,1],[1,1]]`.

For example, `a(1)=4`, `a(2)=15`.

Find `a(n)`.



A more general question is as follows,

`m(n,k)` is the number of elements in `\mathcal B_{2,n}` having exact `k` occurences of `P`, where `P` could be any matrix in `\mathcal B_{2,2}`. It's easy to see `m(n,0)=a(n)`.

Find `m(n,k)` or the generating function of `m(n,k)`.



----------------------

Updated 06/20/2015 solved by Ran Pan and Sittipong Thamrongpairoj (Kuang)

It is clear that we can formulate this problem as an exact consecutive pattern matching problem in words. This problem is equivalent to consecutive 01 matching in words over alphabet `\{0,1,2,3\}`.

Suppose the generating function `f_P(x,t)` is defined as

`f_P(x,t)=1+\sum_{n\ge 1}t^n\sum_{M\in \mathcal B_{2,n}}x^{mch(P,M)}`.
Based on Goulden-Jackson cluster method, the only cluster here is `P` itself. Then we could get the generating function easily.

`f_P(x,t)=\frac{1}{1-4t-(x-1)t^2}`.

The generating function of `a(n)` is `f_P(0,t)`. `a(n)` is A001353 on OEIS.
Number of matrices in `\mathcal B_{2,n}` for `n\ge 1` that has pattern `P` occuring only once is `0, 1, 8, 46, 232,1091,4912, 21468`...


Back to top