1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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\}=:[6]$ is occurring in $s$. The set $K/_\sim$ of equivalence classes is therefore bijectively related to the multisets of cardinality $4$ on $[6]$. 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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Yos Jun 29 '18 at 18:27
  • $\begingroup$ Note that $(5,4,4,4)\not\sim(5,5,4,4)$. $\endgroup$ – Christian Blatter Jun 29 '18 at 18:45
  • $\begingroup$ 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)? $\endgroup$ – Yos Jun 29 '18 at 18:50
  • $\begingroup$ 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. $\endgroup$ – Christian Blatter Jun 29 '18 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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