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.
I can solve by DP
Great! you can tell me about the solution if you like.
O(n3) DP:
dp[i][c][r][g] is the number of valid combinations uptill index i such that current colour is c , r red balls have been used and g green ones, Obviously number of blue balls remaining can be figured out from the index,number of reds used and number of greens used.
If you place red at current index. dp[i]['r'][r][g] = dp[i - 1]['b'][r - 1][g] + dp[i - 1]['g'][r-1][g]
For blue: dp[i]['b'][r][g] = dp[i - 1]['r'][r][g] + dp[i - 1]['g'][r][g].
Similarly you can derive for green.
Also you only need to declare the array as dp[2][3][n][n] because of state-compression.
Thanks , Nice solution! :) I guess N in the first for loop must be for N=3*n else everything understood.
Yeah N is 3n
Let N = 3n
S — set of all possible strings having n red , n blue and n green balls .
S1 -> set of all possible strings in S such that atleast two red are adjacent.
S2 is for blue and S3 is for green.
So
By inclusion-exclusion
Let's find Si first.
Basically it is the set of all possible strings in which atleast two balls of color i are adjacent .
So lets merge any two i colored balls as a single object and then find the number of permutations possible considering those two i balls as an attached object.
Similarly for finding we first merge any two i color balls as a single object and then merge two j color balls as a single objects .
So
You can figure out similarly for
Obviously |S1| = |S2| = |S3| and also as the number of red,green,blue are same and hold the same constraints.
So the answer can be easily found out now.
For kn balls problem:
Please correct me if I am wrong anywhere.
Just practice DP dude! It's quite easy compared to other DP problems
DP is not the most efficient solution for this problem.
deleted