Inspired by this question.
Let's consider the $11$-letter word "$MATHEMATICS$". The general question is to find how many words it is possible to have if we can make $4$ permutations of letters.
Sub-question a)
Each letter has a position in the word, thus when I say $1$ permutation, we exchange the position of $2$ letters. For example, with $1$ permutation it is possible to have "$AMTHEMATICS$", but not "$SMATHEMATIC$".
How much word is it possible to make with $4$ permutations, if …
- a.1) we want exactly $4$ permutations and it is forbidden to have permutation $p$ and its inverse permutation. But it is possible to permute an "$M$" with another "$M$".
- a.2) same as a.1) but it is forbidden to permute "$M$" with the other "$M$".
Sub-question b)
Let's say that by permutations, we mean changing the letters in the word in such a way that $4$ permutations could lead to "$TICSMATHEMA$" (when a letter enter a new position, the other letters are pushed).
How much word is it possible to make with $4$ permutations, if we want exactly $4$ permutations, that means $4$ letters changing positions?
It seems to me that there is no trivial solution. At least I don't see it. Of course, it would be interesting to have a general solution for the case of a word with $n$ letters (possibly not all different) with $k$ permutations.
Best Answer
For $a.1$, there are $$\frac {11*10}{2}=55$$ ways to pick the first permutation. If you just prohibit inverses(the inverse is the same as the swap), there are then $$\frac {55*54*53*52}{24}$$ ways to pick four permutations. But this ignores the fact that you may move the same letter twice. If you want eight letters to move in four swaps, you have $$\frac {55*36*21*10}{24}$$