Question 941398: What is the number of ways letters in the word KOMBINATOORIKA can be rearranged, such that no two consecutive letters are the same?
(the correct answer should be 710579520, not 100% sure though)
I tried first ordering 5 letters and then placing letters K in 6C2 ways, then A in 8C2 ways...etc, but with O-s it would make it different on when i select the three positions for them(whether 6C3,... or 6C2,8C2,11C3...), because i would need to multiply them at the end.
Also tried applying inclusion-exlcusion, but was unable to make it work.
Found 2 solutions by Edwin McCravy, jiju:
Answer by Edwin McCravy(20056)   (Show Source):
You can put this solution on YOUR website! What is the number of ways letters in the word KOMBINATOORIKA can be rearranged,
Here's my take on it, but I didn't get 710579520, though:
In alphabetical order, the letters are
AABIIKKMNOOORT
Start with the 5 letters which occur only once in AABIIKKMNOOORT,
which are B,M,N,R,T
There are 5! or 120 permutations of BMNRT. In each put a space between each two,
a space before the first, and a space after the last. Like this:
__B__M__N__R__T__
[We will do this after each time e choose spaces to put letters in.]
The above is a good representative of those 120 with the 6 spaces:
__B__M__N__R__T__
For each of the 120 arrangments like that, we can pick 2 of the
6 blanks to put the 2 A's --- in 6C2 = 15 ways. That's 120*15 = 1800.
A good representative of these 1800 is
__A__B__M__N__A__R__T__
For each of the 1800 arrangments like that, we can pick 2 of the
8 blanks to put the 2 I's --- in 8C2 = 28 ways. That's 1800*28 = 50400.
A good representative of these 50400 is
__A__B__M__I__N__A__R__T__I__
For each of the 50400 arrangments like that, we can pick 2 of the
10 blanks to put the 2 K's --- in 10C2 = 45 ways. That's 50400*45 = 2268000.
A good representative of these 2268000 is
__A__B__M__K__I__N__K__A__R__T__I__
For each of the 2268000 arrangments like that, we can pick 3 of the
12 blanks to put the 3 O's --- in 12C3 = 220 ways. That's 2268000*220 = 498960000.
A good representative of these 498960000 is
__O__A__B__O__M__K__I__K__O__N__A__R__T__I__
Now we can drop the spaces and no two adjacent letters are the same.
OABOMKIKONARTI
My answer: 498960000
Edwin
Answer by jiju(1)  (Show Source):
|
|
|
