Permutations without repetition pattern (algorithm)

Question

Disclaimer: I haven't done math in a decade. Sorry if this is not very scientific

Hello,

I am writing a computer program, that is supposed to return the number of all permutations of an input string, excluding the permutations where a letter is repeated consecutively. Ex. : Input is "aabc", valid permutations are "abac", "abca" invalid "baac", "bcaa".

My calculation looks like this:

1. Take all permutations: 4!
2. Take all permutations where "a" is repeated, treating the repeated character as one group. ex. [aa]bc, b[aa]c. In this case it's 3! - (length of string - group length + 1)
3. Take all permutations of the letters within the group. ex. [a1a2]bc, [a2a1]bc. In this case 2! (group length)!

So the formula is 4! - (3! * 2!).

This seems to work as long as there is only one repeated character. However as soon as there is more than one, if I repeat the algorithm for all characters, I will discount some permutations twice (the ones that have both character repeated). Ex. input is: "aabbcd" "abbacd" is discounted once. "cdaabb" is discounted twice.

So I need an additional correction where I take the union of the results of the two algorithms and add it back.

Essentially: Out of all permutations of the string "aabbcd", what is the number of strings that have both "aa" and "bb" in them?

Answer 1

In $#3$ of your calculations, permuting the two $a's$ is incorrect, since they are indistinguishable. The correct formula would just be $4!-3!$.

For "valid" permutations of $aabbcd$, applying inclusion-exclusion, $[ 6!- 2*5! + 4! ]$

Edit

With the clarifications given in your answer, you will need to internally permute the identical letters, so $[6! - 2*5!*2! + 4!*2!*2!]$

Answer 2

@true blue anil

from the program's standpoint, the two a's are not treated as indistinguishable. ex. input: "aab"

a1a2b - invalid

a1ba2 - valid

a2a1b - invalid

a2ba1 - valid

ba1a2 - invlaid

ba2a1 - invalid

result should be 2.