How can I identify how many equivalence classes are there? Let $S_n=\{d_1d_2\cdots d_n\mid d_i∈\{0,1\}\text{ for }\,i= 1,2, \dots , n\}$, i.e., the set of binary strings of length $n$.  List (in full) the equivalence classes for each of the following equivalence relations on the given
set.
a) On $S_2$, where $aRb$ if and only if the digit $0$ appears the same number of times in $a$ as in $b$.
b) On $S_3$, where $aRb$ if and only if $a$ is either $b$ written in forwards order or $b$ written in reverse order.
c) On $S_4$, where $aRb$ if and only if the sum of the last three digits in $a$ equals the sum of the last three digits in $b$.
For  case a) I wrote four equivalence classes the $[00] ,[01], [10], [11]$. But I am not sure if having both $[01]$ and $[10]$ makes sense because their elements will be the same and I know equivalence classes can not have the same elements.
Can someone guide me through this question and how to form equivalence classes? For example in case b) do i have to form 8 equivalence classes? We did not go really in depth in class and I am trying to understand how it works and how can I identify how many equivalence classes are there.
 A: $S_n$ has $2^n$ elements.
An equivalence class is a subset of the set of given elements. 
Two elements belong to the same equivalence class iff they are in the given relation.
So, for part a), the equivalence classes are $\{00\},\ \{01,\,10\},\ \{11\}$.
For part b), they are $\{000\},\ \{001,\,100\},\ \{010\},\ \{011,\,110\},\ \{101\},\ \{111\}$.
A: 
a) On $S_2$, where $aRb$ if and only if the digit $0$ appears the same number of times in $a$ as in $b$.

The number of $0$ in the string may be zero, one, or two.  Therefore there are three equivalence classes. $${[11]=\{11\}\\ [10]=\{01, 10\}\\ [00]=\{00\}}$$ 
And indeed, $[01]=[10]$ .

b) On $S_3$, where $aRb$ if and only if $a$ is either $b$ written in forwards order or $b$ written in reverse order.  

There are $2^3$ strings in $S_3$, of which some begin and end in the same digit, and the remainder do not.   The former are palindromes, so are partitioned into equivalence classes of one element (eg $\{010\}$), while the later are partitioned into equivalence classes of two elements (eg $\{011,110\}$).
So count the amount of palindromes, and add half the count of non-palindromes.

c) On $S_4$, where $aRb$ if and only if the sum of the last three digits in $a$ equals the sum of the last three digits in $b$.

Since the digits may only be $0$ or $1$, therefore the sum of the last three digits equals the count of $1$ among those digits.
