# How many equivalence classes are over $4$-digit strings from $\{1,2,3,4,5,6\}$ if strings are in relation of they differ in order or are the same?

Let $A=\{1,2,3,4,5,6\}$. Let $K$ be the set of strings of length $4$ which are made up from the elements of $A$. For example, $(3,3,1,5)\in K$.

Let $E$ be a relation over $K$ such that $(x,y)\in E$ iff $x$ and $y$ are either identical or they differ only in the order of their elements. For example $((1,2,3,2),(3,2,2,1)), ((1,4,2,5),(1,4,2,5))\in E$. $E$ is an equivalence relation.

Also we define $S$ to be a "good subset of $K$" if for all $(x,y)\in K$ if $x\in S$ and $(x,y)\in E$ then $y\in S$. For example, $\{(2,2,2,2), (5,4,4,4),(4,5,4,4),(4,4,5,4), (4,4,4,5)\}$ is a good set. How many subsets of $K$ are good sets and how many equivalence classes are in $E$?

To find the equivalence classes we can choose how many repeating digits will be in some $x\in K$. There're $6$ strings whose digits are identical, there're ${6\choose 1}{5\choose 2}$ strings with two identical digits, there're ${6\choose 1}{5\choose 2}$ strings with three identical digits and there're ${6\choose 1}{5\choose 1}{4\choose 1}{3\choose 1}$ strings where all digits are different. So there're: $$6+{6\choose 1}{5\choose 2}+{6\choose 1}{5\choose 2}+{6\choose 1}{5\choose 1}{4\choose 1}{3\choose 1}$$ equivalence classes.

I'm having trouble understanding the second part of the question. If a string has at least two different digits then how many strings of with the same digits should be in a good set? The example shows four such strings composed of digits $5,4$ but there're more strings which are composed of $5,4$ for example $(5,5,5,4)$ but it's not in the good set.

The equivalence class of a string $s \in K$ is determined by the number of times each digit from $\{1,2,3,4,5,6\}=:$ is occurring in $s$. The set $K/_\sim$ of equivalence classes is therefore bijectively related to the multisets of cardinality $4$ on $$. Counting these multisets is a stars and bars problem; the resulting number is ${4+6-1\choose 6-1}={9\choose4}=126$.
A subset $S$ of $K$ is good iff it is a union of full equivalence classes. Since we can decide for each class individually whether we will include it in $S$ there are $2^{126}$ good subsets of $K$.
In your counting of $K/_\sim$ you have way overcounted, so that you arrive at $486$. Indeed we can go through the partitions of $4$, namely $$(4),\quad(3,1),\quad (2,2),\quad (2,1,1),\quad(1,1,1,1),\tag{1}$$ and then compute for each of them the number of different multisets. For the last of the four we then would obtain ${6\choose4}$, while your product of four binomial coefficients does count different orders of the four chosen digits as different. In reality from $(1)$ we obtain $${6\choose1}+{6\choose1}{5\choose1}+{6\choose2}+{6\choose1}{5\choose2}+{6\choose4}=126$$ multisets, as before.
• Thank you for explaining why my counting method does not work. Can you please elaborate more on what is the good set in less formal way? For example, if $\{(2,2,2,2), (5,4,4,4),(4,5,4,4),(4,4,5,4), (4,4,4,5)\}$ is a good set why isn't $(5,5,5,4),(5,5,4,4)$ in it as well? Is that if a digit appears – Yos Jun 29 '18 at 18:27
• Note that $(5,4,4,4)\not\sim(5,5,4,4)$. – Christian Blatter Jun 29 '18 at 18:45
• I don't know what $\not \sim$ is. Can you explain less formally what unites all elements inside a good set? Is it that one digit should appear in all indices (like $5$ does inside fours)? – Yos Jun 29 '18 at 18:50
• It seems that you don't know what $\sim$ is here. Now $\not\sim$ means "not equivalent". I suggest you try to understand what the equivalence classes are. Then everything will fall into place. – Christian Blatter Jun 29 '18 at 19:03