1
$\begingroup$

A binary string is a sequence of $0$s and $1$s, e.g.,

101101100010111001011000010010011

And by the periodic condition we mean $a_1 = a_{n+1}$, where $n$ is the length of string.

Question: How many numbers of $1100$s are there in all possible strings of length $n$?

I want to write generating function $g(x)$, which will tell me how many $1100$s are there in the periodic binary string (or PBS) of length $n$. The method which I am familiar with is using a transfer matrix.

Method: Let's say I want to count the number of $11$s in PBS. I can write the transfer matrix $$T = \begin{pmatrix} x&1\\ 1 & 1 \end{pmatrix}$$ The largest eigenvalue of the transfer matrix is $$\lambda_+ = \frac{1}{2} \Big(1 + x + \sqrt{5 - 2 x + x^2}\Big)$$

The generating function for a sufficiently large string is simply $$g(x) = n\ln(\lambda_+)$$ From this generating function, we can calculate the number of $11$s in the string. Similarly, we can go for the number of $01$s, $10$s, $00$s. But how to go about finding 1100?

See, I am not particularly interested in the Transfer Matrix Method. But, I will be happy to know if this could be extended.

$\endgroup$
2
$\begingroup$

I think this simple solution works...

For each $k\in \{1,2,\dots,n\}$, count the number of strings $a$ for which $1100$ occurs at position $k$. That is, the number of binary strings for which $(a_k,a_{k+1},a_{k+2},a_{k+3})=(1,1,0,0)$.

If you add up, for each $k$, the number of occurrences of $1100$ at position $k$, then you get the total number of occurrences of $1100$.

$\endgroup$
1
  • 1
    $\begingroup$ Yes, I do not know why I was complicating things! But, from here writing generating function is straight forward, i.e., $g(x) = \sum a_nx^n = \frac{x}{8(1-2x)^2}$ where $a_n = n 2^{n-4}$. $\endgroup$ – Kartik Chhajed Jun 10 '20 at 2:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.