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.