- #1

alandberg

- 1

- 0

I have recently come across a problem in my programming exercises that I haven't been able to solve, even after several days of hard thinking and tinkering.

I have found that this problem may be solved by means of permutations using factorials, but there is a specific permutation that I cannot calculate.

The problem statement is that a string of n characters contains 3 types of different characters, e.g. A, B and C, where each character can have duplicates within the string. Calculate the number of different ways the characters in the string can be arranged. No two adjacent characters can be the same, where the first and last character are also adjacent.

For example: ABBA can be arranged in two ways: ABAB and BABA.

So far, I have tried to find a permutation for the string AAABBC. My method is as follows:

Calculate all permutations under consideration of duplicates as 6! / 3! x 2!

Then, subtract all permutations that contain an occurrence of AAA, AA, BB

The issue with this is that each of these three permutations will also include a subset of the other two, which means I will need to add back permutations that contain both AAA and AA, AAA and BB, and AA and BB. Finally I will need to subtract the intersection of all three sets.

This method may not even be correct, I am getting lost in trying to calculate permutations that contain duplicates. Can someone point me to a post / exercises where I can study this? Can someone please give me a hint on how to approach this problem.

Thanks and regards

Andy