Combinatorics Inclusion-exclusion principle (1 Viewer)

[Kurosaki]

Hello, I'd like to request some assistance with understanding a worked example from Terry Lee's Fundamental Maths.
Find the number of ways you can arrange A, A, B, B, C, C such that no two identical letters are together.
What he did was calculate total number of ways- 90.
then he calculated:
- ways with 1 pair=90
- ways with 2 pairs= 36
- ways with 3 pairs=6

Then he did 90-(36-6)=60 to find the total number of ways with at least 1 pair.

I'm a bit confused with this leap of logic however.
I understand that there is a bit of overcounting with 2 pairs - obviously we can't have all the arrangements equal to the ones with at least 1 pair, but I'm not sure how to visualise it.

Could someone see if my thought process is correct?
For arrangements with one pair, clearly this also includes 2 pairs and 3 pairs.
Similarly, arrangements with 2 pairs also include 3 pairs.
since the number of arrangements with 3 pairs is 6, then the arrangements with 2 pairs is 36-6=30.
Then we consider an arrangement such as CAABBC, which I think would be double-counted - counted in both the scenarios where, for a single pair, A and B are chosen to be in pairs?
Does the problem of double-counting with arrangements such as CAABBC occur here, and hence that's why we subtract the number of ways for only 2 pairs to occur?


If someone could offer a more intuitive/better explanation, that would also be greatly appreciated , I'm not quite sure of my logic, it feels like I'm fumbling and too contrived haha.

Edit: Actually, could whoever responds to this just explain this from scratch please?

 

[braintic]

Just visualize it with a Venn diagram with 3 circles.

Outside all the circles are the words you are looking for.

One circle contains all the words with the As together, another has the words with the Bs together, and the 3rd has the Cs together.

The overlap between A and B contains all the words that have the As together and the Bs together, and similarly for the other overlap pairs.

The intersection of A, B and C has the words where the As are together, the Bs are together and the Cs are together.

Can you see how the counting works using the Venn diagram?

 

[Kurosaki]

I got something vaguely like the attached diagram- so you're saying essentially that when I'm calculating the arrangements with at least one pair, I'm actually getting everything A + B + C basically, and this results in overcounting, which is why I need to subtract A n B, A n C and B n C?
and it just so happens that the sum of these intersections gives 30, so we subtract that from A + B + C, which is 90, to get A U B U C = 60?

Edit: I get this, but why does A+B+C=90?
Is it because when you let the possibility of having one pair, then you can also have 2 or 3 pairs? Could you please confirm this for me?

 

[braintic]

I get this, but why does A+B+C=90?
Is it because when you let the possibility of having one pair, then you can also have 2 or 3 pairs? Could you please confirm this for me?

Yes, that is correct.

When you arrange [ (AA) B B C C ] in 5!/(2!2!) = 30 ways, there is no guarantee that the B's or C's are separated.
So some of these arrangements are counted again when you arrange A A (BB) C C and also A A B B (CC).

So 3 times 30 = 90 counts the arrangements of [ (AA) (BB) C C ], [ (AA) B B (CC) ] and [ A A (BB) (CC) ] twice.
It also counts the arrangements of [ (AA) (BB) (CC) ] three times.

When you arrange [ (AA) (BB) C C ] in 4!/2! = 12 ways, there is no guarantee that the C's will be separated.
So some arrangements will be counted again when you arrange [ (AA) B B (CC) ] and [ A A (BB) (CC) ].
So 3 times 12 = 36 also counts the arrangements of [ (AA) (BB) (CC) ] three times.

So the count of 90 counted arrangements of [ (AA) (BB) (CC) ] three times, and so did the count of 36.
So when you subtract, you have lost ALL the arrangements of [ (AA) (BB) (CC) ].

So these need to be added back on at the end.

 

[mathing]

Note sure if OP is still interested in this question... the answers above are good. Here is another view of it, if it didn't click for you.

The amount of ways of arranging A,A,B,B,C,C = 6!/(2!2!2!) = 90.

We want all the ways where no pair of letters are together, so we want to minus the amount with at least one pair. To have a pair it will be 5!/2!/2! = 30, but we have 3 letters we could do that with so we get 90 ways. It's too many because each of these 1 pair ways includes 2 pair and 3 pair duplicate counts.

The amount of ways of organizing 2 pairs is 4!/2! = 12 but this is including a 3 pair and the amount of arranging 3 pairs is 3! = 6. So a 2 pair without a 3 pair can happen 6 ways and there are (3 choose 2) letter = 6 combinations of letters for making the 2 pair sets so we get 18 ways for exactly 2 pairs. In the 1 pair calculation we will include 2 pair duplicates. Let's consider when we get the exact 2 pair duplicates e.g. A, B will occur when calculating pairs on A and B but not on C as that would be a 3 pair, so they are counted twice and so they are duplicated once.

The amount of duplicate 3 pairs is easily seen to happen twice.

We minus from 1 pairs (90) the duplicate 2 pairs (18) and the duplicate 3 pairs (2*6 = 12) for a total of 60 arrangements with pairs. Therefore there are 30 arrangements of A A B B C C without any pairs.