gkeesh7's blog

Counting Problem
By gkeesh7, history, 9 years ago, In English

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.

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I can solve by DP

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Great! you can tell me about the solution if you like.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 5   Vote: I like it +10 Vote: I do not like it

      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. 

      for(int i = 1 ; i <= N ; ++i){
    for(int r = 0 ; r <= i && r <= n; ++r){
        for(int g = 0 ; g + r <= i && g <= n ; ++g){
            int blue_used = i-(r+g);
            if(blue_used>n){
                //Set the dp to 0 for all colors for the given (i,r,g)
            }
            else{
                //use the relation mentioned in post. 
            }
        }
    }
}
      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks , Nice solution! :) I guess N in the first for loop must be for N=3*n else everything understood.

        → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Just practice DP dude! It's quite easy compared to other DP problems

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    DP is not the most efficient solution for this problem.

    → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

deleted

→ Reply