# Permutation of the word MATTER

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?

• So neither of the Ts can be in the 3rd or 4th position? Commented Oct 15, 2018 at 19:22
• @RushabhMehta yes Commented Oct 15, 2018 at 19:24
• Rather than using formulas for derangements directly., reuse the technique used in finding the formula for derangements in the first place. Temporarily treat the T's as distinct. Apply inclusion-exclusion. Unlike in the original problem of counting derangements, you now have two forbidden positions for each of the T's. After having counted where T's are distinct, take care of the overcounting by recognize you counted each arrangement twice. Commented Oct 15, 2018 at 19:29

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) {
}
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) {
}
}
}
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)) {
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]$$

• Is that the floor function? Because it doesn't work for n = 2(floor(2/2.7) = 0). Commented Oct 16, 2018 at 13:18
• No, it's not the floor function but the nearest integer function: [2/2.7]=1, not 0.
– Saša
Commented Oct 16, 2018 at 13:50
• Thank you! It is fascinating how the number $e$ can pop up just about everywhere in mathematics! Commented Oct 16, 2018 at 15:38
• @Oldboy I have a question, why is the letter T cannot be in the fourth position in 1) and X cannot be in the third position in 2)? Is it because we're factoring in the fact that T and X will be the same letter later on? Commented Oct 17, 2018 at 5:40