Consider a binary sequence $\mathbf{a}_n$ consisting of 1s and 0s. Let us denote by $f(\mathbf{a}_n)$ the number of $(1, 1)$ and $(0, 0)$ in $\mathbf{a}_n$; I am not sure whether there is a formal name for $f(\mathbf{a}_n)$. Is there a closed expression for the number of $\mathbf{a}_n$'s such that $f(\mathbf{a}_n) = i$ for $i = 0, 1, \dotsc, n - 1$?
1 Answer
Consider the related binary sequence $\widetilde{a_n}$ of length $n-1$ defined by $\widetilde{a_n}(k) := (a_n(k+1)-a_n(k))\text{ mod }2$ for $k = 0\ldots n-2$; the number of 0's in $\widetilde{a_n}$ is exactly the number of $(0,0)'s$ and $(1,1)'s$ in $a_n$. Now, the number of binary sequences of length $(n-1)$ which have exactly $i$ 0's is just $\binom{n-1}{i}$, and each $\widetilde{a_n}$ arises from two distinct $a_n$'s (one with $a_n(0) = 0$ and one with $a_n(0) = 1$), so it follows that $\left|\{a_n|f(a_n) = i\}\right| = 2\binom{n-1}{i}$.