1
$\begingroup$

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$?

$\endgroup$

1 Answer 1

4
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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