SOLUTION: How many ways can we arange the word SOCIOLOGICAL having no consecutive Os?

Question 1205004: How many ways can we arange the word SOCIOLOGICAL having no consecutive Os?

Answer by math_tutor2020(3817) (Show Source): You can put this solution on YOUR website!

There are 12 letters in the word SOCIOLOGICAL

If we could tell all of the letters apart, then we'd have 12! = 12*11*10*9*8*7*6*5*4*3*2*1 = 479,001,600 different permutations.
A little over 479 million.

But we have these repeats: O, C, I and L
O shows up 3 times
C shows up 2 times
I shows up 2 times
L shows up 2 times

In other words we have this frequency chart

Letter	Frequency
S	1
O	3
C	2
I	2
L	2
G	1
A	1

Anything with frequency larger than 1 leads to erroneous over-counting.

We need to divide the previous result by (3!*2!*2!*2!) to correct for that error.

(479,001,600)/(3!*2!*2!*2!)
= (479,001,600)/(6*2*2*2)
= (479,001,600)/(48)
= 9,979,200

That is the number of ways to arrange the letters in SOCIOLOGICAL.

Some of those rearrangements will have the O's together.

Here are the two cases:
(i) Three O's are together (eg: SOOOCILGICAL)
(ii) Two O's are together and the third O is somewhere else (eg: SOOCILOGICAL)

We'll need to find a way to count all of the permutations for each case.

Let's remove all three O's and replace them with X.
Wherever X is, it represents three O's next to each other.
So we go from SOCIOLOGICAL to XSCILGICAL
We drop from 12 letters to 9 letters when removing those O's, but then bump up to 10 letters when introducing X.

We have 10! = 10*9*8*7*6*5*4*3*2*1 = 3,628,800 ways to arrange the letters of XSCILGICAL so all three O's are together.
Let p = 3,628,800 so we can use it later.
This wraps up case (i)

Let's remove X and put the O's back in to get SOCIOLOGICAL again.
This time we'll have Y represent two O's
We will have 12-2+1 = 11 letters to rearrange.
One such permutation could be SYCILOGICAL and another is SYOCILGICAL

The second example SYOCILGICAL is a problem however because we already accounted for this when introducing X earlier.
There are 11! = 39,916,800 ways to rearrange the letters of SYCILOGICAL and 10! = 3,628,800 ways to rearrange the letters of XSCILGICAL
There are 11! - 10! = 39,916,800 - 3,628,800 = 36,288,000 ways to arrange the letters of SYCILOGICAL such that the O and Y are not neighbors.
Let q = 36,288,000 so we can use it later.
This wraps up case (ii)

There are p+q = 3,628,800 + 36,288,000 = 39,916,800 different rearrangements of SOCIOLOGICAL such that either
(i) All three O's are together, or,
(ii) Two O's are together with the third O somewhere else.

Subtract this from 12! = 479,001,600 to finish up the problem.

479,001,600 - 39,916,800 = 439,084,800

There are roughly 439 million different rearrangements of SOCIOLOGICAL such the O's are separated (i.e. we don't have OO or OOO anywhere in the string).

There is probably a much more clever approach to this problem.
I'll let another tutor step in to offer it.

--------------------------------------------------------------------------
--------------------------------------------------------------------------

Answer: 439,084,800 (a little over 439 million permutations).

RELATED QUESTIONS
in how many ways we can arrange the letters in the word 'MISSISIPI' so that all S's come... (answered by Edwin McCravy)

find in how many ways we can arrange the letters in the word 'MISSISIPI' so that all S's... (answered by Edwin McCravy)

In how many ways we can arrange the word 'ENGINEERING' so that all N's come together and... (answered by Edwin McCravy)

How many ways can we arrange two letters from the word computer without repetition (answered by Edwin McCravy)

A library has 3 books from each of 3 different authors. How many ways can the library... (answered by ikleyn)

I don't understand how to solve this question? This is permutarions. How... (answered by Alan3354)

In how many ways can the letters of the word COUPLE be arranged, so that no two vowels... (answered by ewatrrr)

How many ways can you arrange the letters of the word MAMMALIA provided no vowels are put (answered by greenestamps,Edwin McCravy)

how many ways can you arrange the word equal (answered by Alan3354)