Let's say I have a word AAAB, and I'm trying to permute it so that the lowest number of characters remain in their original places. For this word, the minimum number is $2$ characters, because any other permutation: AAAB, AABA, ABAA, and BAAA keep $2$ characters in their original places. However, if I have a word like ABC, I can just offset it to get BCA, in which the number of characters is $0$. My question is, given a certain word, how can I find the min number of characters? Would I just have to check every single possible permutation?
2026-02-22 23:42:41.1771803761
If I have a certain word, how can I find the lowest number of characters that must remain in their original spots if I permute it?
22 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
If the length of the word is $n$, find the most numerous character. Let there be $k$ of those. Any permutation will have at least $2k-n$ of them in locations that had that character before, so if $k \gt \frac n2$ you will have some matches. In your example of $AAAB$ we have $n=4, k=3, 2k-n=2$, which agrees with your finding that there must be $2\ A$s in positions that had $A$s before. This comes about because there are $n-k$ other characters. You can put them in $n-k$ of the spaces that had the common character before, leaving $2k-n$ common characters in the original locations. None of the other characters contribute at all.