Permutation of the word MATTER

Question

In how many ways can the word MATTER be arranged so that none of the letters are in their original positions?

I know I have to use the Derangement formula, but the hardest thing here for me to consider is the 2 Ts in the middle. What would you have to do here?

Answer 1

First, treat all letters as different. For example, replace one T with X and start with the word MATXER. We'll switch 'X' back to 'T' later.

The total number of derangements of word MATXER is !6=265. However, not all derangements are valid:

(1) The letter T must not be in the fourth position. What is the number of such derangements? Actually, the letter T could be in 5 different positions and for each position we have the equal number of derangements, which is one fifth. So we have to eliminate 265/5 = 53 derangements.

(2) The letter X must not be in the third position. By using the same reasoning as in (1) we have to eliminate another 53 derangements.

But in (1) and (2) we are eliminating some derangements twice. These derangements have T in the fourth place and X in the third place. This actually means that letters M,A,E,R are deranged in four remaining positions. So the number of derangements counted twice is !4=9

Taking all this into account it seems that the final result is: 265-53-53+9=168. But it's not! That's the number of derangments of word MATXER with an additional condition that letters T and X are not either in third or fourth position. For example, words TMAERX and XMAERT are both included in the total count of 168. But when you replace X with T, both words become the same: TMAERT.

Actually all of 168 derangments come in pairs with T and X in swapped positions. So the total number of derangements of MATTER is actually 168/2=84.

The following Java code is just a brute force proof that the above result is correct:

import java.util.ArrayList;
import java.util.List;

public class Derange {  
    public static List<String> permutations(String source) {
        List<String> perms = new ArrayList<>();
        if(source.length() == 1) {
            perms.add(source);
        }
        else {
            for(int i = 0; i < source.length(); i++) {
                char c = source.charAt(i);
                String rs = source.substring(0,  i) + source.substring(i + 1);
                List<String> p = permutations(rs);
                for(String s: p) {
                    perms.add(c + s);
                }
            }           
        }
        return perms;
    }

    public static void main(String[] args) {
        List<String> perms = permutations("MATTER");
        List<String> result = new ArrayList<>();
        for(String perm: perms) {
            if(perm.charAt(0) != 'M' && perm.charAt(1) != 'A' && perm.charAt(2) != 'T' && perm.charAt(3) != 'T' && perm.charAt(4) != 'E' && perm.charAt(5) != 'R') {
                if(!result.contains(perm)) {
                    result.add(perm);
                    System.out.println((result.size()< 10? "#0": "#") + (result.size()) + ": " + perm);
                }
            }
        }
    }   
}

The code prints the following list of derangements:

#01: AMERTT
#02: AMRETT
#03: ATMERT
#04: ATMRTE
#05: ATEMRT
#06: ATERMT
#07: ATERTM
#08: ATRMTE
#09: ATREMT
#10: ATRETM
#11: AEMRTT
#12: AERMTT
#13: ARMETT
#14: AREMTT
#15: TMAERT
#16: TMARTE
#17: TMEART
#18: TMERAT
#19: TMERTA
#20: TMRATE
#21: TMREAT
#22: TMRETA
#23: TTMARE
#24: TTMERA
#25: TTMRAE
#26: TTAMRE
#27: TTAERM
#28: TTARME
#29: TTEMRA
#30: TTEARM
#31: TTERMA
#32: TTERAM
#33: TTRMAE
#34: TTRAME
#35: TTREMA
#36: TTREAM
#37: TEMART
#38: TEMRAT
#39: TEMRTA
#40: TEAMRT
#41: TEARMT
#42: TEARTM
#43: TERMAT
#44: TERMTA
#45: TERAMT
#46: TERATM
#47: TRMATE
#48: TRMEAT
#49: TRMETA
#50: TRAMTE
#51: TRAEMT
#52: TRAETM
#53: TREMAT
#54: TREMTA
#55: TREAMT
#56: TREATM
#57: EMARTT
#58: EMRATT
#59: ETMART
#60: ETMRAT
#61: ETMRTA
#62: ETAMRT
#63: ETARMT
#64: ETARTM
#65: ETRMAT
#66: ETRMTA
#67: ETRAMT
#68: ETRATM
#69: ERMATT
#70: ERAMTT
#71: RMAETT
#72: RMEATT
#73: RTMATE
#74: RTMEAT
#75: RTMETA
#76: RTAMTE
#77: RTAEMT
#78: RTAETM
#79: RTEMAT
#80: RTEMTA
#81: RTEAMT
#82: RTEATM
#83: REMATT
#84: REAMTT

BTW, my favorite way to calculate the number of derangements quickly is:

$$!n=\left[\frac{n!}{e}\right]$$