How many elements are in equivalence class of string $aabc$ if it's in relation with other strings of length $4$ who have the same set of characters?

Question

Let $S$ be the set of all strings of length $4$ composed from $5$ characters $a,b,c,d,e$. Any two strings in $S$ are considered to be equivalent if they share the same set of characters. For example: $aabc$, $abbc$ and $baac$ are equivalent. How many strings in total are possible and how many strings are in the equivalence class of $aabc$?

There're a total of $5^4$ strings.

In general, $3^4$ strings are possible with $3$ unique characters. Then we need to subtract the strings that are made up of only $1$ character: there're $3$ such strings. Also we need to subtract all strings that are made up of only $2$ characters: there're $2^4$ such strings. But there're $3$ strings made up of a single character in $2^4$ strings and we already subtracted those from $3^4$ so we need to add them back.

Therefore there're $3^4-3-{3\choose 2}2^4+3=33$.

Not sure if I got this right.

---

The answer to the second part of the exercise (how many elements in the class of $aabc$) is $3\cdot 4\cdot 3=36$ (which I don't understand).

Answer 1

Let $S$ be the set of all strings of length $4$ composed from $5$ characters $a,b,c,d,e$. Any two strings in $S$ are considered to be equivalent if they share the same set of characters. For example: $aabc$, $abbc$ and $baac$ are equivalent. How many strings in total are possible and how many strings are in the equivalence class of $aabc$?

There are $\Box^\Box$ ways to make 4 independent selections from 5 characters. (Select with replacement).

To count ways to select a,b, and c, to make a string of length four, there is $\binom\Box\Box$ ways to choose which 1 from those 3 letters must be selected twice, and there are $\binom\Box\Box$ ways to arrange a singleton and pair.

Answer 2

I think that the answer $24$ is wrong. But the book says $3\cdot 4\cdot 3$ which is $36$.

We have that the number of anagrams of the word $xxyz$ is $4!/2!=12$, moreover we have $3$ ways to assign a letter in $\{a,b,c\}$ to $x$. Therefore the total is $12 \cdot 3=36$.

In other words, in the equivalence class of $aabc$ we should have the $12$ anagrams of $aabc$, plus the $12$ anagrams of $abbc$, plus the $12$ anagrams of $abcc$. Am I missing something?

Answer 3

The question can be rephrased like this:

1) How many functions $\{1,2,3,4\}\to\{a,b,c,d,e\}$ exists (provided that the cardinality of set $\{a,b,c,d,e\}$ is $5$)?

You are correct in your answer on this: $5^4$

If $f,g$ are such functions then $f\simeq g\iff\mathsf{im}f=\mathsf{im}g$

2) What is the cardinality of $[a,a,b,c]:=\{f\in\{a,b,c,d,e\}^{\{1,2,3,4\}}\mid\mathsf{im}f=\{a,a,b,c\}\}$?

Note that $[a,a,b,c]=[a,b,c]$ because $\{a,a,b,c\}=\{a,b,c\}$.

If $f\in[a,b,c]$ then $\{f^{-1}(\{a\}),f^{-1}(\{b\}),f^{-1}(\{c\})\}$ is a partition of $\{1,2,3,4\}$ that contains $3$ elements, and each of such partitions corresponds with an unordered pair of distinct elements of $\{1,2,3,4\}$.

E.g. pair $\{1,4\}$ corresponds with partition $\{\{1,4\},\{2\},\{3\}\}$. So there are $\binom42=6$ of such partitions. Further there are $3!=6$ ways to link such a partition with the elements $a,b,c$.

For instance $f^{-1}(\{a\})=\{1,4\}$,$f^{-1}(\{b\})=\{2\}$ and $f^{-1}(\{c\})=\{3\}$ is one of them, and the $a,b,c$ can be permuted.

So the answer is $\binom423!=36$.