Counting unique permutations of a word using Burnside’s Lemma?

Question

How many unique “words” (not English words, but strings of letters) are there of the word HOMOMORPHISM?

I know that the answer is:

$$ \frac{12!}{2!3!3!} = 6652800 $$

However, I found this by applying the formula given from a stats class I took, and this is for a group theory course. The professor requires us to take a different approach: we must use Burnside’s Lemma to count the number of orbits.

I know that the group $G = S_{12}$ is acting on a set M. But I’m not quite sure what the set M is here.

The question also asks to describe the action the group takes on M, and to find the size of the stabilizer.

I know that $ |G| = |O(m)| * |St(m)| $ so the last part should be easy (I think) once I figure out the number of orbits.

I’m extremely confused about how to apply Burnside’s Lemma to this problem. I’ve previously seen how to apply it to find the number of unique colourings of a polyhedron (and I think I understand that), but I don’t see how to do that here.

Edit: fixed formatting and added clarification.

Answer 1

$M$ is the orbit of $W=HOMOMORPHISM$ under the action (on places, which means on the right) of $S_{12}$. It has a nice (statistical) combinatorial description: it is the set of all words with $$ 2\times H\ ;\ 3\times O\ ;\ 3\times M\ ;\ 1\times R\ ;\ 1\times P\ ;\ 1\times I\ ;\ 1\times S. $$ In general: if you have a word $W$ of length $n$ on an alphabet $X$, you get two actions

• one (of $S_n$) on places (on the right) which reads $$ W.\sigma=(x_1\ldots x_n).\sigma=x_{\sigma(1)}\ldots x_{\sigma(n)} $$
• one (of $S_X$) on letters (on the left) which reads $$ \sigma.(x_1\ldots x_n)=\sigma(x_1)\ldots \sigma(x_n) $$

For example, with $X=\{O,P\}$ the orbit of $POP$ on the right is $$ \{POP,OPP,PPO\} $$ whereas the orbit on the left is $$ \{POP,OPO\} $$ Here, you have one orbit on the right, the stabilizer has cardinal $2!\times 3!\times 3!$, hence the result.

Answer 2

Given an alphabet $\cal A$ a word of length $n$ is a function $$ f:\{1,2,...,n\}\longrightarrow\cal A. $$ The group of permutations ${\cal S}_n$ acts on the set of words of length $n$ as $\sigma\cdot f=f\circ\sigma^{-1}$.

Then the set of anagrams of a word $f$ is just the orbit of $f$ under this action. It is clear that in the example asked about $n=12$ and the stabilizer is a copy of ${\cal S}_2\times{\cal S}_3\times{\cal S}_3$ inside $\cal S_{12}$ (hence the formula).