Permutations of Undertale

Suppose that one of the Es is in the correct place. There are $2$ Es that could be chosen, and there are $d_8 = 14833$ arrangements of the other $8$ letters so that none of these are in the correct place (here $d_n$ is the number of derangements of $n$ symbols).

Suppose that one of the other letters is in the correct place. Then the two Es must go in the places of two different letters again. There are $7$ choices for the letter that will be fixed, and $\binom{6}{2}$ choices for the two letters where the two Es will go. Suppose that, for example, letter D is fixed, and the two Es go in the L and T places. Then we have to arrange the letters L,T,A,R,U,N in the E,E,A,R,U,N places, so that none of A,R,U,N are in their correct place. Let $A_1,A_2,A_3,A_4$ be the number of arrangements with $A,R,U,N$ (respectively) in its correct place. Then $|A_i| = 5!$ for all $1 \le i \le 4$ , $|A_i \cap A_j| = 4!$ for all $1 \le i < j \le 4$ , $|A_i \cap A_j \cap A_k| = 3!$ for all $1 \le i < j < k \le 4$ and $|A_1 \cap A_2 \cap A_3 \cap A_4| = 2!$ . By the Inclusion-Exclusion Principle, we deduce that $|A_1 \cup A_2 \cup A_3 \cup A_4| = 4 \times 5! - 6 \times 4! + 4 \times 3! - 2! \; = \; 358$ and hence there are $6! - 358 = 362$ arrangements of L,T,A,R,U,N in the E,E,A,R,U,N places so that none of A,R,U,N are in the correct place.

Thus there are $2 \times d_8 + 7 \times \binom{6}{2} \times 362 = \boxed{67676}$ rearrangements of UNDERTALE so that exactly one letter is in the correct place.

For everyone who is too lazy to do the calculations:

1
2
3
4
5
6
7
8

from itertools import permutations
def count(word):
    s = set()
    for p in permutations(word):
        if sum([p[i]==word[i] for i in range(len(word))]) == 1:
            s.add(p)
    return len(s)
count('undertale')

67676