1. ## Inclusion–exclusion principle

Hi,
Im trying to solve this problem, but kinda stuck..

Question:
In how many ways can you arrange the string AAABBCCDD
if AAA, BB, CC, DD sequences are not allowed. (AA sequence can appear)

how can I know how many arrangement for a string when a certain sequence is not allowed?

2. ## Re: Inclusion–exclusion principle

1) Calculate the number of different arrangements of AAABBCCDD.

2) Calculate the number of arrangements that do include AAA or BB or CC or DD.

3) Subtract (2) from (1).

3. ## Re: Inclusion–exclusion principle

Originally Posted by HallsofIvy
1) Calculate the number of different arrangements of AAABBCCDD.

2) Calculate the number of arrangements that do include AAA or BB or CC or DD.

3) Subtract (2) from (1).
How do i calculate the number of arrangements that include AAA,BB,CC,DD?
that's the part that I struggle with

4. ## Re: Inclusion–exclusion principle

Let event $E_{\text{subsequence}}$ be the event that a permutation of $AAABBCCDD$ contains a particular subsequence. (This is not standard notation, just convenient)

Example:
$|E|=\dfrac{9!}{3!2!2!2!}$
$|E_{AAA}|=\dfrac{7!}{1!2!2!2!}$
$|E_{BB}|=\dfrac{8!}{3!1!2!2!}$
$|E_{AAA}\cap E_{BB}|=\dfrac{6!}{1!1!2!2!}$

Basically, treat the subsequence as one character and find the number of ways to permute it.

5. ## Re: Inclusion–exclusion principle

Originally Posted by SlipEternal
Let event $E_{\text{subsequence}}$ be the event that a permutation of $AAABBCCDD$ contains a particular subsequence. (This is not standard notation, just convenient)

Example:
$|E|=\dfrac{9!}{3!2!2!2!}$
$|E_{AAA}|=\dfrac{7!}{1!2!2!2!}$
$|E_{BB}|=\dfrac{8!}{3!1!2!2!}$
$|E_{AAA}\cap E_{BB}|=\dfrac{6!}{1!1!2!2!}$

Basically, treat the subsequence as one character and find the number of ways to permute it.
now I get it
thanks!