Counting Problem

Revision en1, by gkeesh7, 2015-06-21 22:53:37

Greetings Everyone,

I know this sounds pretty much like a homework problem that's why I was hesitant to ask it in the first place. (I could have asked someone through a PM but I have lost faith in such methods lately)

Anyways,

There are 3n balls in total, of 3 different colours , (i.e. n balls of each colour) find the number of ways you can arrange them in a row such that no two balls of the same colour are adjacent

The various approaches which I could google include,

1 ) Principle of Inclusion and Exclusion :- It stated Find the total number of ways of arranging 3n balls with the constraints (i.e. n identical balls of each colour) then subtract from it the number of ways in which atleast two balls of same colour are together. But I couldn't derive a formula from it :( the one I derived was wrong.

2 ) Someone on Quora said to brute force till n=5 and guess the formula.

3 ) Suggestions of O(n^3) DP from a freind. Don't know how to do it.

I still think this is a pretty standard Permutations problem but sorry I guess my googling sucks.

Any Resource / Approach / Formula would be deeply appreciated.

I am sorry if this is a stupid problem, Also if you would like to answer a follow up.

I was thinking of generalizing this problem to kn balls and k different colours. How to do it ?

Thanks in Advance.

Tags counting, math, formula

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English gkeesh7 2015-06-21 22:53:37 1373 Initial revision (published)