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).
|
|
|
