Relation on $n$-digit binary strings...

Question

Let $X$ be the set of all $7$-digit bit strings

0100011,

and let two elements in $X$ be related if the first and last bit matches. How many equivalence classes are there? Further, how many elements are in each?

Answer 1

There are indeed $2^5$ elements in each equivalence class, but there are four (not two) equivalence classes:

There are $2$ ways to choose the first bit ($B_F$), and $2$ ways to choose the last bit $B_L$, so each and every string belongs to one of $2^2 = 4$ equivalence classes:

$B_F\quad B_L$
$\;1\;\quad \;1\;$
$\;1\;\quad \;0\;$
$\;0\;\quad \;1\;$
$\;0\;\quad \;0\;$

---

Sanity check: $$2^2 \;\text{EC's}\; \cdot 2^5 \;\text{Bits per EC}= 2^7\;\;\text{possible strings of length 7}\quad\text{ Bingo!}$$

(Note that performing this sanity check on your first attempt gives us: $2 \cdot 2^5 = 2^6 \neq 2^7$.)