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.