wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Permutation Combination 1
        
(Message started by: navdeep1771 on Jun 17^th, 2018, 12:06am)

Title: Permutation Combination 1
Post by navdeep1771 on Jun 17^th, 2018, 12:06am

In how many ways letters of the word 'ARRANGE' can be arranged such that "no two R's are together and no two A's are together"?

Title: Re: Permutation Combination 1
Post by towr on Jun 17^th, 2018, 12:26pm

[hide]I think it's 7!-5!*2!*2!=4560
7! ways to rearrange 7 letters, minus 5! ways to rearrange the 5 distinct letters multiplied by twice 2 ways to arrange duplicate letters next to each other.
That's assuming the duplicate letters are distinguishable. (Otherwise divide by 4)[/hide]

Title: Re: Permutation Combination 1
Post by dudiobugtron on Jun 18^th, 2018, 12:10am

[hide]There are 5! ways to arrange ARNGE. Then for each of those, there are 4 places to put the second A, and then 5 places you can put the second R. So 5! x 5 x 4 = 2400 ways to arrange ARRANGE like that.[/hide]

This is different from towr's solution. I think this is because:
[hide]towr's solution only subtracted the results with AA *and* RR, so for eg AARANGER would not have been subtracted.[/hide]

Title: Re: Permutation Combination 1
Post by towr on Jun 18^th, 2018, 8:53am

Well, we can't both be right, but we can both be wrong.

[hide]Counting them with a script says it should be 2640

There are 5 places to put the second A, because you can put the second R between the two A's if they're adjacent.[/hide]

Title: Re: Permutation Combination 1
Post by towr on Jun 18^th, 2018, 10:03am

Fixing the mistake that dudiobugtron spotted: [hide]7! - (2 * 6!*2! - 5!*2!*2!) = 2640[/hide]

Title: Re: Permutation Combination 1
Post by navdeep1771 on Jun 18^th, 2018, 9:03pm

Duplicate letters are not distinguishable.

Title: Re: Permutation Combination 1
Post by towr on Jun 18^th, 2018, 10:14pm

well, [hide]660[/hide], then

Title: Re: Permutation Combination 1
Post by navdeep1771 on Jun 19^th, 2018, 1:59am

Yup. We have to divide by [hide] 2!.2!=4
And 660 is absolutely correct. [/hide]

Title: Re: Permutation Combination 1
Post by dudiobugtron on Jun 19^th, 2018, 11:58pm

on 06/18/18 at 08:53:32, towr wrote:

Well, we can't both be right, but we can both be wrong.

lol. Thank you for the correction.

Title: Re: Permutation Combination 1
Post by Grimbal on Jun 21^st, 2018, 1:43pm

I had no time to write the solution at that time but this I quickly came up with an elegant solution:
[hide]
There are 7! permutations of the letters. There are 6! that contain 'AA' (just think of AA as a single symbol). Likewise, there are 6! permutations containing 'RR'. If you take 7! - 6! - 6! you remove all the wrong permutations, but you remove twice the combinations containing 'AA' and 'RR'. So you have to add that number back. It's 5!.
So, the final result is 7! - 6! - 6! + 5! = 3720. Divide by 4 if letters are indistinguishable.
3720/4 = 930.
Tadaaaa! ... er....

OK, the mistake is that 7! must be divided by 4 to take into account the duplicates. But 6! must be divided by 2. 5! counts no duplicates.
So I get: 7!/4 - 6!/2 - 6!/2 + 5! = 660
[/hide]