3
$\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} = \{ \text{on} \ i-\text{th} \text{ and }(i+1)-\text{th} \text{ position, there are two same consecutive letters} \}. $$ So my answer would be $$ \frac{10!}{2!3!2!} - 9 \cdot \left(\frac{9!}{3!2!} + \frac{9!}{3!2!} +\frac{9!}{2!2!}\right)+ 8 \cdot \left(\frac{8!}{2!2!}\right) +8 \cdot 7 \cdot \left(\frac{8!}{3!} + \frac{8!}{2!} +\frac{8!}{2!}\right) - 7 \cdot 6 \cdot 5 \cdot 7!$$

$\endgroup$
3
$\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 $$\binom{10}{3}\binom{7}{2}\binom{5}{2}3! = \frac{10!}{3!7!} \cdot \frac{7!}{2!5!} \cdot \frac{5!}{2!3!} \cdot 3! = \frac{10!}{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 $$\binom{9}{2}\binom{7}{2}5!$$ 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 $$\binom{9}{3}\binom{6}{2}4!$$ ways.

A pair of $T$s are adjacent: By symmetry, there are $$\binom{9}{3}\binom{6}{2}4!$$ 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 $$\binom{8}{2}\binom{6}{2}4!$$ 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 $$\binom{8}{2}6!$$ ways.

A pair of $A$s are adjacent and a pair of $T$s are adjacent: By symmetry, there are $$\binom{8}{2}6!$$ 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 $$\binom{8}{3}5!$$ 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 $$\binom{7}{2}5!$$ ways.

Two pairs of $A$s are adjacent and a pair of $T$s are adjacent: By symmetry, there are $$\binom{7}{2}5!$$ 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 $$\binom{10}{3}\binom{7}{2}\binom{5}{2}3! - \binom{9}{2}\binom{7}{2}5! - \binom{9}{3}\binom{6}{2}4! - \binom{9}{3}\binom{6}{2}4! + \binom{8}{2}\binom{6}{2}4! + \binom{8}{2}6! + \binom{8}{2}6! + \binom{8}{3}5! - \binom{7}{2}5! - \binom{7}{2}5! - 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 Mar 12 at 9:30
1
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.