# Number of 1100 in periodic binary string of length $n$

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.

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$$.
• 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}$. Jun 10, 2020 at 2:43