1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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}$$

$\endgroup$

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.