How many permutations are there of M, M, A, A, A, T, T, E, I, K, so that no two consecutive letters are the same?How many strings are there (inclusion exclusion principle)How many permutations of the letters in HURRAH have the first R preceding the first H?How many words can be written with $aabbbccdd$ such that no two equal letters are adjacent?How many words can be formed, given $4$ letters, and in each word there must be at least two letters are the same?Arrangements of a,a,a,b,b,b,c,c,c in which no three consecutive letters are the sameNumber of arrangements with no consecutive letter the sameHow many 4-letter “words” have no two consecutive letters identical - clarification needed on answerHow many arrangements of these letters are there with no pair of consecutive letters the same?Number of ways to arrange $A,A,A,B,C,C$ such that no $2$ consecutive letters are the sameIn how many ways can letters in a word CALCULUS be rearranged
Validating user input
How is the Swiss post e-voting system supposed to work, and how was it wrong?
My adviser wants to be the first author
Why do Australian milk farmers need to protest supermarkets' milk price?
Sword in the Stone story where the sword was held in place by electromagnets
Why did it take so long to abandon sail after steamships were demonstrated?
Why using two cd commands in bash script does not execute the second command
How could a scammer know the apps on my phone / iTunes account?
Theorems like the Lovász Local Lemma?
Can anyone tell me why this program fails?
Do I need life insurance if I can cover my own funeral costs?
PTIJ: Who should pay for Uber rides: the child or the parent?
At what level can a dragon innately cast its spells?
Is it possible that AIC = BIC?
Replacing Windows 7 security updates with anti-virus?
Employee lack of ownership
Should we release the security issues we found in our product as CVE or we can just update those on weekly release notes?
Can hydraulic brake levers get hot when brakes overheat?
How to deal with a cynical class?
What options are left, if Britain cannot decide?
An Accountant Seeks the Help of a Mathematician
Making a sword in the stone, in a medieval world without magic
Possible Leak In Concrete
Can elves maintain concentration in a trance?
How many permutations are there of M, M, A, A, A, T, T, E, I, K, so that no two consecutive letters are the same?
How many strings are there (inclusion exclusion principle)How many permutations of the letters in HURRAH have the first R preceding the first H?How many words can be written with $aabbbccdd$ such that no two equal letters are adjacent?How many words can be formed, given $4$ letters, and in each word there must be at least two letters are the same?Arrangements of a,a,a,b,b,b,c,c,c in which no three consecutive letters are the sameNumber of arrangements with no consecutive letter the sameHow many 4-letter “words” have no two consecutive letters identical - clarification needed on answerHow many arrangements of these letters are there with no pair of consecutive letters the same?Number of ways to arrange $A,A,A,B,C,C$ such that no $2$ consecutive letters are the sameIn how many ways can letters in a word CALCULUS be rearranged
$begingroup$
How many permutations are there of
$$ M, M, A, A, A, T, T, E, I, K $$
so that there are no two consecutive letters are the same?
I would use the Inclusion-exclusion principle where
$$ A_i = texton i-textth text and (i+1)-textth text position, there are two same consecutive letters . $$
So my answer would be
$$ frac10!2!3!2! - 9 cdot left(frac9!3!2! + frac9!3!2! +frac9!2!2!right)+ 8 cdot left(frac8!2!2!right) +8 cdot 7 cdot left(frac8!3! + frac8!2! +frac8!2!right) - 7 cdot 6 cdot 5 cdot 7!$$
combinatorics inclusion-exclusion
$endgroup$
add a comment |
$begingroup$
How many permutations are there of
$$ M, M, A, A, A, T, T, E, I, K $$
so that there are no two consecutive letters are the same?
I would use the Inclusion-exclusion principle where
$$ A_i = texton i-textth text and (i+1)-textth text position, there are two same consecutive letters . $$
So my answer would be
$$ frac10!2!3!2! - 9 cdot left(frac9!3!2! + frac9!3!2! +frac9!2!2!right)+ 8 cdot left(frac8!2!2!right) +8 cdot 7 cdot left(frac8!3! + frac8!2! +frac8!2!right) - 7 cdot 6 cdot 5 cdot 7!$$
combinatorics inclusion-exclusion
$endgroup$
add a comment |
$begingroup$
How many permutations are there of
$$ M, M, A, A, A, T, T, E, I, K $$
so that there are no two consecutive letters are the same?
I would use the Inclusion-exclusion principle where
$$ A_i = texton i-textth text and (i+1)-textth text position, there are two same consecutive letters . $$
So my answer would be
$$ frac10!2!3!2! - 9 cdot left(frac9!3!2! + frac9!3!2! +frac9!2!2!right)+ 8 cdot left(frac8!2!2!right) +8 cdot 7 cdot left(frac8!3! + frac8!2! +frac8!2!right) - 7 cdot 6 cdot 5 cdot 7!$$
combinatorics inclusion-exclusion
$endgroup$
How many permutations are there of
$$ M, M, A, A, A, T, T, E, I, K $$
so that there are no two consecutive letters are the same?
I would use the Inclusion-exclusion principle where
$$ A_i = texton i-textth text and (i+1)-textth text position, there are two same consecutive letters . $$
So my answer would be
$$ frac10!2!3!2! - 9 cdot left(frac9!3!2! + frac9!3!2! +frac9!2!2!right)+ 8 cdot left(frac8!2!2!right) +8 cdot 7 cdot left(frac8!3! + frac8!2! +frac8!2!right) - 7 cdot 6 cdot 5 cdot 7!$$
combinatorics inclusion-exclusion
combinatorics inclusion-exclusion
edited Mar 11 at 16:37
N. F. Taussig
44.7k103358
44.7k103358
asked Mar 11 at 9:24
user15269user15269
388110
388110
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
As you observed, there are $10$ letters, of which $3$ are $A$s, $2$ are $M$s, $2$ are $T$s, $1$ is an $E$, $1$ is an $I$, and $1$ is a $K$.
If there were no restrictions, we would choose three of the ten positions for the $A$s, two of the remaining seven positions for the $M$s, two of the remaining five positions for the $T$s, and arrange the $E$, $I$, $K$ in the remaining three positions in
$$binom103binom72binom523! = frac10!3!7! cdot frac7!2!5! cdot frac5!2!3! cdot 3! = frac10!3!2!2!$$
in agreement with your answer.
From these, we must subtract those arrangements in which or more pairs of identical letters are adjacent.
Arrangements with a pair of adjacent identical letters: We have to consider cases, depending on whether the identical letters are $A$s, $M$s, or $T$s.
A pair of $A$s are adjacent: We have nine objects to arrange: $AA, A, M, M, T, T, E, I, K$. Choose two of the nine positions for the $M$s, two of the remaining seven positions for the $T$s, and then arrange the five distinct objects $AA$, $A$, $E$, $I$, $K$ in the remaining five positions, which can be done in
$$binom92binom725!$$
ways.
A pair of $M$s are adjacent: We have nine objects to arrange: $A, A, A, MM, T, T, E, I, K$. Choose three of the nine positions for the $A$s, two of the remaining six positions for the $T$s, and arrange the four distinct objects $MM, E, I, K$ in the remaining four positions, which can be done in
$$binom93binom624!$$
ways.
A pair of $T$s are adjacent: By symmetry, there are
$$binom93binom624!$$
such arrangements.
Arrangements with two pairs of adjacent identical letters: This can occur in two ways. Either the pairs are disjoint or they overlap.
Two pairs of $A$s are adjacent: This can only occur if the three $A$s are consecutive. Thus, we have eight objects to arrange: $AAA, M, M, T, T, E, I, K$. Choose two of the eight positions for the $M$s, two of the remaining six positions for the $T$s, and arrange the four distinct objects $AAA, E, I, K$ in the remaining four positions, which can be done in
$$binom82binom624!$$
ways.
A pair of $A$s are adjacent and a pair of $M$s are adjacent: We have eight objects to arrange: $AA, A, MM, T, T, E, I, K$. Choose two of the eight positions for the $T$s and arrange the six distinct objects $AA, A, MM, E, I, K$ in the remaining six positions in
$$binom826!$$
ways.
A pair of $A$s are adjacent and a pair of $T$s are adjacent: By symmetry, there are
$$binom826!$$
such arrangements.
A pair of $M$s are adjacent and a pair of $T$s are adjacent: We have eight objects to arrange: $A, A, A, MM, TT, E, I, K$. Choose three of the eight positions for the $A$s and then arrange the remaining five distinct objects $MM, TT, E, I, K$ in the remaining five positions in
$$binom835!$$
ways.
Arrangements with three pairs of adjacent identical letters: We again consider cases.
Two pairs of $A$s are adjacent and a pair of $M$s are adjacent: We have seven objects to arrange, $AAA, MM, T, T, E, I, K$. Choose two of the seven positions for the $T$s and arrange the five distinct objects $AAA, MM, E, I, K$ in the remaining five positions in
$$binom725!$$
ways.
Two pairs of $A$s are adjacent and a pair of $T$s are adjacent: By symmetry, there are
$$binom725!$$
such arrangements.
A pair of $A$s are adjacent, a pair of $M$s are adjacent, and a pair of $T$s are adjacent: We have seven objects to arrange: $AA, A, MM, TT, E, I, K$. Since all the objects are distinct, there are
$$7!$$
such arrangements.
Arrangements containing four pairs of adjacent identical letters: We have six objects to arrange: $AAA, MM, TT, E, I, K$. Since all the objects are distinct, there are
$$6!$$
such arrangements.
By the Inclusion-Exclusion Principle, there are
$$binom103binom72binom523! - binom92binom725! - binom93binom624! - binom93binom624! + binom82binom624! + binom826! + binom826! + binom835! - binom725! - binom725! - 7! + 6!=47760$$
arrangements in which no two adjacent letters are identical.
$endgroup$
1
$begingroup$
I have added the final result, it matches perfectly with my computations. So +1
$endgroup$
– Oldboy
2 days ago
add a comment |
$begingroup$
If I calculated everything correctly, your answer is 446880.
I used the following program to check it:
public class PermutationCounter
public static int[] duplicate(int[] source)
int[] dest = new int[source.length];
System.arraycopy(source, 0, dest, 0, source.length);
return dest;
public static boolean allLettersExhausted(int[] source)
for(int i = 0; i < source.length; i++)
if(source[i] != 0)
return false;
return true;
private char[] letters;
private int[] count;
public PermutationCounter(char[] letters, int[] count)
this.letters = letters;
this.count = count;
public int countPermutations()
return countPermutations(-1, count, "");
private int countPermutations(int last, int[] alphabet, String permutation)
if(allLettersExhausted(alphabet))
System.out.println(permutation);
return 1;
int sum = 0;
for(int i = 0; i < alphabet.length; i++)
if(i != last && alphabet[i] > 0)
int[] alphabetCopy = duplicate(alphabet);
alphabetCopy[i]--;
sum += countPermutations(i, alphabetCopy, permutation + letters[i]);
return sum;
public static void main(String[] args)
char[] letters = new char[] 'M', 'A', 'T', 'E', 'I', 'K';
int[] count = new int[] 2, 3, 2, 1, 1, 1;
PermutationCounter counter = new PermutationCounter(letters, count);
System.out.println("TOTAL PERMUTATIONS: " + counter.countPermutations());
My answer is 47760 (much lower number) and the full list of all permutations can be found here (yes, the word "MATEMATIKA" is also there).
The code starts with two lists. The first contains the list of letters, the second list contains the number of appearances of each letter in the final word. The code is recursive: it tracks the last letter and counts all shorter words starting with a different letter.
I know this is not the answer you were hoping for but it might help you to conclude if your answer is right or wrong.
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3143471%2fhow-many-permutations-are-there-of-m-m-a-a-a-t-t-e-i-k-so-that-no-two%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
As you observed, there are $10$ letters, of which $3$ are $A$s, $2$ are $M$s, $2$ are $T$s, $1$ is an $E$, $1$ is an $I$, and $1$ is a $K$.
If there were no restrictions, we would choose three of the ten positions for the $A$s, two of the remaining seven positions for the $M$s, two of the remaining five positions for the $T$s, and arrange the $E$, $I$, $K$ in the remaining three positions in
$$binom103binom72binom523! = frac10!3!7! cdot frac7!2!5! cdot frac5!2!3! cdot 3! = frac10!3!2!2!$$
in agreement with your answer.
From these, we must subtract those arrangements in which or more pairs of identical letters are adjacent.
Arrangements with a pair of adjacent identical letters: We have to consider cases, depending on whether the identical letters are $A$s, $M$s, or $T$s.
A pair of $A$s are adjacent: We have nine objects to arrange: $AA, A, M, M, T, T, E, I, K$. Choose two of the nine positions for the $M$s, two of the remaining seven positions for the $T$s, and then arrange the five distinct objects $AA$, $A$, $E$, $I$, $K$ in the remaining five positions, which can be done in
$$binom92binom725!$$
ways.
A pair of $M$s are adjacent: We have nine objects to arrange: $A, A, A, MM, T, T, E, I, K$. Choose three of the nine positions for the $A$s, two of the remaining six positions for the $T$s, and arrange the four distinct objects $MM, E, I, K$ in the remaining four positions, which can be done in
$$binom93binom624!$$
ways.
A pair of $T$s are adjacent: By symmetry, there are
$$binom93binom624!$$
such arrangements.
Arrangements with two pairs of adjacent identical letters: This can occur in two ways. Either the pairs are disjoint or they overlap.
Two pairs of $A$s are adjacent: This can only occur if the three $A$s are consecutive. Thus, we have eight objects to arrange: $AAA, M, M, T, T, E, I, K$. Choose two of the eight positions for the $M$s, two of the remaining six positions for the $T$s, and arrange the four distinct objects $AAA, E, I, K$ in the remaining four positions, which can be done in
$$binom82binom624!$$
ways.
A pair of $A$s are adjacent and a pair of $M$s are adjacent: We have eight objects to arrange: $AA, A, MM, T, T, E, I, K$. Choose two of the eight positions for the $T$s and arrange the six distinct objects $AA, A, MM, E, I, K$ in the remaining six positions in
$$binom826!$$
ways.
A pair of $A$s are adjacent and a pair of $T$s are adjacent: By symmetry, there are
$$binom826!$$
such arrangements.
A pair of $M$s are adjacent and a pair of $T$s are adjacent: We have eight objects to arrange: $A, A, A, MM, TT, E, I, K$. Choose three of the eight positions for the $A$s and then arrange the remaining five distinct objects $MM, TT, E, I, K$ in the remaining five positions in
$$binom835!$$
ways.
Arrangements with three pairs of adjacent identical letters: We again consider cases.
Two pairs of $A$s are adjacent and a pair of $M$s are adjacent: We have seven objects to arrange, $AAA, MM, T, T, E, I, K$. Choose two of the seven positions for the $T$s and arrange the five distinct objects $AAA, MM, E, I, K$ in the remaining five positions in
$$binom725!$$
ways.
Two pairs of $A$s are adjacent and a pair of $T$s are adjacent: By symmetry, there are
$$binom725!$$
such arrangements.
A pair of $A$s are adjacent, a pair of $M$s are adjacent, and a pair of $T$s are adjacent: We have seven objects to arrange: $AA, A, MM, TT, E, I, K$. Since all the objects are distinct, there are
$$7!$$
such arrangements.
Arrangements containing four pairs of adjacent identical letters: We have six objects to arrange: $AAA, MM, TT, E, I, K$. Since all the objects are distinct, there are
$$6!$$
such arrangements.
By the Inclusion-Exclusion Principle, there are
$$binom103binom72binom523! - binom92binom725! - binom93binom624! - binom93binom624! + binom82binom624! + binom826! + binom826! + binom835! - binom725! - binom725! - 7! + 6!=47760$$
arrangements in which no two adjacent letters are identical.
$endgroup$
1
$begingroup$
I have added the final result, it matches perfectly with my computations. So +1
$endgroup$
– Oldboy
2 days ago
add a comment |
$begingroup$
As you observed, there are $10$ letters, of which $3$ are $A$s, $2$ are $M$s, $2$ are $T$s, $1$ is an $E$, $1$ is an $I$, and $1$ is a $K$.
If there were no restrictions, we would choose three of the ten positions for the $A$s, two of the remaining seven positions for the $M$s, two of the remaining five positions for the $T$s, and arrange the $E$, $I$, $K$ in the remaining three positions in
$$binom103binom72binom523! = frac10!3!7! cdot frac7!2!5! cdot frac5!2!3! cdot 3! = frac10!3!2!2!$$
in agreement with your answer.
From these, we must subtract those arrangements in which or more pairs of identical letters are adjacent.
Arrangements with a pair of adjacent identical letters: We have to consider cases, depending on whether the identical letters are $A$s, $M$s, or $T$s.
A pair of $A$s are adjacent: We have nine objects to arrange: $AA, A, M, M, T, T, E, I, K$. Choose two of the nine positions for the $M$s, two of the remaining seven positions for the $T$s, and then arrange the five distinct objects $AA$, $A$, $E$, $I$, $K$ in the remaining five positions, which can be done in
$$binom92binom725!$$
ways.
A pair of $M$s are adjacent: We have nine objects to arrange: $A, A, A, MM, T, T, E, I, K$. Choose three of the nine positions for the $A$s, two of the remaining six positions for the $T$s, and arrange the four distinct objects $MM, E, I, K$ in the remaining four positions, which can be done in
$$binom93binom624!$$
ways.
A pair of $T$s are adjacent: By symmetry, there are
$$binom93binom624!$$
such arrangements.
Arrangements with two pairs of adjacent identical letters: This can occur in two ways. Either the pairs are disjoint or they overlap.
Two pairs of $A$s are adjacent: This can only occur if the three $A$s are consecutive. Thus, we have eight objects to arrange: $AAA, M, M, T, T, E, I, K$. Choose two of the eight positions for the $M$s, two of the remaining six positions for the $T$s, and arrange the four distinct objects $AAA, E, I, K$ in the remaining four positions, which can be done in
$$binom82binom624!$$
ways.
A pair of $A$s are adjacent and a pair of $M$s are adjacent: We have eight objects to arrange: $AA, A, MM, T, T, E, I, K$. Choose two of the eight positions for the $T$s and arrange the six distinct objects $AA, A, MM, E, I, K$ in the remaining six positions in
$$binom826!$$
ways.
A pair of $A$s are adjacent and a pair of $T$s are adjacent: By symmetry, there are
$$binom826!$$
such arrangements.
A pair of $M$s are adjacent and a pair of $T$s are adjacent: We have eight objects to arrange: $A, A, A, MM, TT, E, I, K$. Choose three of the eight positions for the $A$s and then arrange the remaining five distinct objects $MM, TT, E, I, K$ in the remaining five positions in
$$binom835!$$
ways.
Arrangements with three pairs of adjacent identical letters: We again consider cases.
Two pairs of $A$s are adjacent and a pair of $M$s are adjacent: We have seven objects to arrange, $AAA, MM, T, T, E, I, K$. Choose two of the seven positions for the $T$s and arrange the five distinct objects $AAA, MM, E, I, K$ in the remaining five positions in
$$binom725!$$
ways.
Two pairs of $A$s are adjacent and a pair of $T$s are adjacent: By symmetry, there are
$$binom725!$$
such arrangements.
A pair of $A$s are adjacent, a pair of $M$s are adjacent, and a pair of $T$s are adjacent: We have seven objects to arrange: $AA, A, MM, TT, E, I, K$. Since all the objects are distinct, there are
$$7!$$
such arrangements.
Arrangements containing four pairs of adjacent identical letters: We have six objects to arrange: $AAA, MM, TT, E, I, K$. Since all the objects are distinct, there are
$$6!$$
such arrangements.
By the Inclusion-Exclusion Principle, there are
$$binom103binom72binom523! - binom92binom725! - binom93binom624! - binom93binom624! + binom82binom624! + binom826! + binom826! + binom835! - binom725! - binom725! - 7! + 6!=47760$$
arrangements in which no two adjacent letters are identical.
$endgroup$
1
$begingroup$
I have added the final result, it matches perfectly with my computations. So +1
$endgroup$
– Oldboy
2 days ago
add a comment |
$begingroup$
As you observed, there are $10$ letters, of which $3$ are $A$s, $2$ are $M$s, $2$ are $T$s, $1$ is an $E$, $1$ is an $I$, and $1$ is a $K$.
If there were no restrictions, we would choose three of the ten positions for the $A$s, two of the remaining seven positions for the $M$s, two of the remaining five positions for the $T$s, and arrange the $E$, $I$, $K$ in the remaining three positions in
$$binom103binom72binom523! = frac10!3!7! cdot frac7!2!5! cdot frac5!2!3! cdot 3! = frac10!3!2!2!$$
in agreement with your answer.
From these, we must subtract those arrangements in which or more pairs of identical letters are adjacent.
Arrangements with a pair of adjacent identical letters: We have to consider cases, depending on whether the identical letters are $A$s, $M$s, or $T$s.
A pair of $A$s are adjacent: We have nine objects to arrange: $AA, A, M, M, T, T, E, I, K$. Choose two of the nine positions for the $M$s, two of the remaining seven positions for the $T$s, and then arrange the five distinct objects $AA$, $A$, $E$, $I$, $K$ in the remaining five positions, which can be done in
$$binom92binom725!$$
ways.
A pair of $M$s are adjacent: We have nine objects to arrange: $A, A, A, MM, T, T, E, I, K$. Choose three of the nine positions for the $A$s, two of the remaining six positions for the $T$s, and arrange the four distinct objects $MM, E, I, K$ in the remaining four positions, which can be done in
$$binom93binom624!$$
ways.
A pair of $T$s are adjacent: By symmetry, there are
$$binom93binom624!$$
such arrangements.
Arrangements with two pairs of adjacent identical letters: This can occur in two ways. Either the pairs are disjoint or they overlap.
Two pairs of $A$s are adjacent: This can only occur if the three $A$s are consecutive. Thus, we have eight objects to arrange: $AAA, M, M, T, T, E, I, K$. Choose two of the eight positions for the $M$s, two of the remaining six positions for the $T$s, and arrange the four distinct objects $AAA, E, I, K$ in the remaining four positions, which can be done in
$$binom82binom624!$$
ways.
A pair of $A$s are adjacent and a pair of $M$s are adjacent: We have eight objects to arrange: $AA, A, MM, T, T, E, I, K$. Choose two of the eight positions for the $T$s and arrange the six distinct objects $AA, A, MM, E, I, K$ in the remaining six positions in
$$binom826!$$
ways.
A pair of $A$s are adjacent and a pair of $T$s are adjacent: By symmetry, there are
$$binom826!$$
such arrangements.
A pair of $M$s are adjacent and a pair of $T$s are adjacent: We have eight objects to arrange: $A, A, A, MM, TT, E, I, K$. Choose three of the eight positions for the $A$s and then arrange the remaining five distinct objects $MM, TT, E, I, K$ in the remaining five positions in
$$binom835!$$
ways.
Arrangements with three pairs of adjacent identical letters: We again consider cases.
Two pairs of $A$s are adjacent and a pair of $M$s are adjacent: We have seven objects to arrange, $AAA, MM, T, T, E, I, K$. Choose two of the seven positions for the $T$s and arrange the five distinct objects $AAA, MM, E, I, K$ in the remaining five positions in
$$binom725!$$
ways.
Two pairs of $A$s are adjacent and a pair of $T$s are adjacent: By symmetry, there are
$$binom725!$$
such arrangements.
A pair of $A$s are adjacent, a pair of $M$s are adjacent, and a pair of $T$s are adjacent: We have seven objects to arrange: $AA, A, MM, TT, E, I, K$. Since all the objects are distinct, there are
$$7!$$
such arrangements.
Arrangements containing four pairs of adjacent identical letters: We have six objects to arrange: $AAA, MM, TT, E, I, K$. Since all the objects are distinct, there are
$$6!$$
such arrangements.
By the Inclusion-Exclusion Principle, there are
$$binom103binom72binom523! - binom92binom725! - binom93binom624! - binom93binom624! + binom82binom624! + binom826! + binom826! + binom835! - binom725! - binom725! - 7! + 6!=47760$$
arrangements in which no two adjacent letters are identical.
$endgroup$
As you observed, there are $10$ letters, of which $3$ are $A$s, $2$ are $M$s, $2$ are $T$s, $1$ is an $E$, $1$ is an $I$, and $1$ is a $K$.
If there were no restrictions, we would choose three of the ten positions for the $A$s, two of the remaining seven positions for the $M$s, two of the remaining five positions for the $T$s, and arrange the $E$, $I$, $K$ in the remaining three positions in
$$binom103binom72binom523! = frac10!3!7! cdot frac7!2!5! cdot frac5!2!3! cdot 3! = frac10!3!2!2!$$
in agreement with your answer.
From these, we must subtract those arrangements in which or more pairs of identical letters are adjacent.
Arrangements with a pair of adjacent identical letters: We have to consider cases, depending on whether the identical letters are $A$s, $M$s, or $T$s.
A pair of $A$s are adjacent: We have nine objects to arrange: $AA, A, M, M, T, T, E, I, K$. Choose two of the nine positions for the $M$s, two of the remaining seven positions for the $T$s, and then arrange the five distinct objects $AA$, $A$, $E$, $I$, $K$ in the remaining five positions, which can be done in
$$binom92binom725!$$
ways.
A pair of $M$s are adjacent: We have nine objects to arrange: $A, A, A, MM, T, T, E, I, K$. Choose three of the nine positions for the $A$s, two of the remaining six positions for the $T$s, and arrange the four distinct objects $MM, E, I, K$ in the remaining four positions, which can be done in
$$binom93binom624!$$
ways.
A pair of $T$s are adjacent: By symmetry, there are
$$binom93binom624!$$
such arrangements.
Arrangements with two pairs of adjacent identical letters: This can occur in two ways. Either the pairs are disjoint or they overlap.
Two pairs of $A$s are adjacent: This can only occur if the three $A$s are consecutive. Thus, we have eight objects to arrange: $AAA, M, M, T, T, E, I, K$. Choose two of the eight positions for the $M$s, two of the remaining six positions for the $T$s, and arrange the four distinct objects $AAA, E, I, K$ in the remaining four positions, which can be done in
$$binom82binom624!$$
ways.
A pair of $A$s are adjacent and a pair of $M$s are adjacent: We have eight objects to arrange: $AA, A, MM, T, T, E, I, K$. Choose two of the eight positions for the $T$s and arrange the six distinct objects $AA, A, MM, E, I, K$ in the remaining six positions in
$$binom826!$$
ways.
A pair of $A$s are adjacent and a pair of $T$s are adjacent: By symmetry, there are
$$binom826!$$
such arrangements.
A pair of $M$s are adjacent and a pair of $T$s are adjacent: We have eight objects to arrange: $A, A, A, MM, TT, E, I, K$. Choose three of the eight positions for the $A$s and then arrange the remaining five distinct objects $MM, TT, E, I, K$ in the remaining five positions in
$$binom835!$$
ways.
Arrangements with three pairs of adjacent identical letters: We again consider cases.
Two pairs of $A$s are adjacent and a pair of $M$s are adjacent: We have seven objects to arrange, $AAA, MM, T, T, E, I, K$. Choose two of the seven positions for the $T$s and arrange the five distinct objects $AAA, MM, E, I, K$ in the remaining five positions in
$$binom725!$$
ways.
Two pairs of $A$s are adjacent and a pair of $T$s are adjacent: By symmetry, there are
$$binom725!$$
such arrangements.
A pair of $A$s are adjacent, a pair of $M$s are adjacent, and a pair of $T$s are adjacent: We have seven objects to arrange: $AA, A, MM, TT, E, I, K$. Since all the objects are distinct, there are
$$7!$$
such arrangements.
Arrangements containing four pairs of adjacent identical letters: We have six objects to arrange: $AAA, MM, TT, E, I, K$. Since all the objects are distinct, there are
$$6!$$
such arrangements.
By the Inclusion-Exclusion Principle, there are
$$binom103binom72binom523! - binom92binom725! - binom93binom624! - binom93binom624! + binom82binom624! + binom826! + binom826! + binom835! - binom725! - binom725! - 7! + 6!=47760$$
arrangements in which no two adjacent letters are identical.
edited 2 days ago
Oldboy
8,67911036
8,67911036
answered Mar 11 at 16:33
N. F. TaussigN. F. Taussig
44.7k103358
44.7k103358
1
$begingroup$
I have added the final result, it matches perfectly with my computations. So +1
$endgroup$
– Oldboy
2 days ago
add a comment |
1
$begingroup$
I have added the final result, it matches perfectly with my computations. So +1
$endgroup$
– Oldboy
2 days ago
1
1
$begingroup$
I have added the final result, it matches perfectly with my computations. So +1
$endgroup$
– Oldboy
2 days ago
$begingroup$
I have added the final result, it matches perfectly with my computations. So +1
$endgroup$
– Oldboy
2 days ago
add a comment |
$begingroup$
If I calculated everything correctly, your answer is 446880.
I used the following program to check it:
public class PermutationCounter
public static int[] duplicate(int[] source)
int[] dest = new int[source.length];
System.arraycopy(source, 0, dest, 0, source.length);
return dest;
public static boolean allLettersExhausted(int[] source)
for(int i = 0; i < source.length; i++)
if(source[i] != 0)
return false;
return true;
private char[] letters;
private int[] count;
public PermutationCounter(char[] letters, int[] count)
this.letters = letters;
this.count = count;
public int countPermutations()
return countPermutations(-1, count, "");
private int countPermutations(int last, int[] alphabet, String permutation)
if(allLettersExhausted(alphabet))
System.out.println(permutation);
return 1;
int sum = 0;
for(int i = 0; i < alphabet.length; i++)
if(i != last && alphabet[i] > 0)
int[] alphabetCopy = duplicate(alphabet);
alphabetCopy[i]--;
sum += countPermutations(i, alphabetCopy, permutation + letters[i]);
return sum;
public static void main(String[] args)
char[] letters = new char[] 'M', 'A', 'T', 'E', 'I', 'K';
int[] count = new int[] 2, 3, 2, 1, 1, 1;
PermutationCounter counter = new PermutationCounter(letters, count);
System.out.println("TOTAL PERMUTATIONS: " + counter.countPermutations());
My answer is 47760 (much lower number) and the full list of all permutations can be found here (yes, the word "MATEMATIKA" is also there).
The code starts with two lists. The first contains the list of letters, the second list contains the number of appearances of each letter in the final word. The code is recursive: it tracks the last letter and counts all shorter words starting with a different letter.
I know this is not the answer you were hoping for but it might help you to conclude if your answer is right or wrong.
$endgroup$
add a comment |
$begingroup$
If I calculated everything correctly, your answer is 446880.
I used the following program to check it:
public class PermutationCounter
public static int[] duplicate(int[] source)
int[] dest = new int[source.length];
System.arraycopy(source, 0, dest, 0, source.length);
return dest;
public static boolean allLettersExhausted(int[] source)
for(int i = 0; i < source.length; i++)
if(source[i] != 0)
return false;
return true;
private char[] letters;
private int[] count;
public PermutationCounter(char[] letters, int[] count)
this.letters = letters;
this.count = count;
public int countPermutations()
return countPermutations(-1, count, "");
private int countPermutations(int last, int[] alphabet, String permutation)
if(allLettersExhausted(alphabet))
System.out.println(permutation);
return 1;
int sum = 0;
for(int i = 0; i < alphabet.length; i++)
if(i != last && alphabet[i] > 0)
int[] alphabetCopy = duplicate(alphabet);
alphabetCopy[i]--;
sum += countPermutations(i, alphabetCopy, permutation + letters[i]);
return sum;
public static void main(String[] args)
char[] letters = new char[] 'M', 'A', 'T', 'E', 'I', 'K';
int[] count = new int[] 2, 3, 2, 1, 1, 1;
PermutationCounter counter = new PermutationCounter(letters, count);
System.out.println("TOTAL PERMUTATIONS: " + counter.countPermutations());
My answer is 47760 (much lower number) and the full list of all permutations can be found here (yes, the word "MATEMATIKA" is also there).
The code starts with two lists. The first contains the list of letters, the second list contains the number of appearances of each letter in the final word. The code is recursive: it tracks the last letter and counts all shorter words starting with a different letter.
I know this is not the answer you were hoping for but it might help you to conclude if your answer is right or wrong.
$endgroup$
add a comment |
$begingroup$
If I calculated everything correctly, your answer is 446880.
I used the following program to check it:
public class PermutationCounter
public static int[] duplicate(int[] source)
int[] dest = new int[source.length];
System.arraycopy(source, 0, dest, 0, source.length);
return dest;
public static boolean allLettersExhausted(int[] source)
for(int i = 0; i < source.length; i++)
if(source[i] != 0)
return false;
return true;
private char[] letters;
private int[] count;
public PermutationCounter(char[] letters, int[] count)
this.letters = letters;
this.count = count;
public int countPermutations()
return countPermutations(-1, count, "");
private int countPermutations(int last, int[] alphabet, String permutation)
if(allLettersExhausted(alphabet))
System.out.println(permutation);
return 1;
int sum = 0;
for(int i = 0; i < alphabet.length; i++)
if(i != last && alphabet[i] > 0)
int[] alphabetCopy = duplicate(alphabet);
alphabetCopy[i]--;
sum += countPermutations(i, alphabetCopy, permutation + letters[i]);
return sum;
public static void main(String[] args)
char[] letters = new char[] 'M', 'A', 'T', 'E', 'I', 'K';
int[] count = new int[] 2, 3, 2, 1, 1, 1;
PermutationCounter counter = new PermutationCounter(letters, count);
System.out.println("TOTAL PERMUTATIONS: " + counter.countPermutations());
My answer is 47760 (much lower number) and the full list of all permutations can be found here (yes, the word "MATEMATIKA" is also there).
The code starts with two lists. The first contains the list of letters, the second list contains the number of appearances of each letter in the final word. The code is recursive: it tracks the last letter and counts all shorter words starting with a different letter.
I know this is not the answer you were hoping for but it might help you to conclude if your answer is right or wrong.
$endgroup$
If I calculated everything correctly, your answer is 446880.
I used the following program to check it:
public class PermutationCounter
public static int[] duplicate(int[] source)
int[] dest = new int[source.length];
System.arraycopy(source, 0, dest, 0, source.length);
return dest;
public static boolean allLettersExhausted(int[] source)
for(int i = 0; i < source.length; i++)
if(source[i] != 0)
return false;
return true;
private char[] letters;
private int[] count;
public PermutationCounter(char[] letters, int[] count)
this.letters = letters;
this.count = count;
public int countPermutations()
return countPermutations(-1, count, "");
private int countPermutations(int last, int[] alphabet, String permutation)
if(allLettersExhausted(alphabet))
System.out.println(permutation);
return 1;
int sum = 0;
for(int i = 0; i < alphabet.length; i++)
if(i != last && alphabet[i] > 0)
int[] alphabetCopy = duplicate(alphabet);
alphabetCopy[i]--;
sum += countPermutations(i, alphabetCopy, permutation + letters[i]);
return sum;
public static void main(String[] args)
char[] letters = new char[] 'M', 'A', 'T', 'E', 'I', 'K';
int[] count = new int[] 2, 3, 2, 1, 1, 1;
PermutationCounter counter = new PermutationCounter(letters, count);
System.out.println("TOTAL PERMUTATIONS: " + counter.countPermutations());
My answer is 47760 (much lower number) and the full list of all permutations can be found here (yes, the word "MATEMATIKA" is also there).
The code starts with two lists. The first contains the list of letters, the second list contains the number of appearances of each letter in the final word. The code is recursive: it tracks the last letter and counts all shorter words starting with a different letter.
I know this is not the answer you were hoping for but it might help you to conclude if your answer is right or wrong.
answered Mar 11 at 15:58
OldboyOldboy
8,67911036
8,67911036
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3143471%2fhow-many-permutations-are-there-of-m-m-a-a-a-t-t-e-i-k-so-that-no-two%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown