CODEWITHSUNDEEP
c++algorithmmatrixdynamic-programmingcombinatorics
Love Babbar
Love Babbar

Reputation: 161

Fill the Grid with three colors A and B and C

How to find the numbers of ways to fill a grid (3*n)array, with three colors A, B and C.

Under the following constraints:

1) All the n cells of the same row can't have the same color.

2) All the 3 cells of the same column can't have the same color.

Sample input : if n=2, then output or number of ways = 174.

Please explain the approach for this.

Upvotes: 4

Views: 5659

Answers (2)

Enigma
Enigma

Reputation: 189

This answer given by sam29 on codefores.

We can solve this question using Inclusion-Exclusion principle. So, let's first consider only the first column of the matrix. We can easily deduce that there are 24 different ways to fill that column keeping in mind that we can't have the same letter in the complete column. Now, we can directly say that the total ways to fill the complete matrix will be 24^N (Name this value as X1). In this answer, we have made sure that all the column contains distinct alphabets. But we need to consider the cases a row contains the same letter. So, now we will use inclusion-exclusion principle.

Find the number of cases with one row same. Fix 'A' in the first row. Now, take only the first column and you can deduce that there are 8 distinct ways to fill the 2nd and the 3rd row of the first column keeping in mind we can't have the same letter in the complete column. So, now we can find the total number of ways to fill all the N rows as 8^N. Now, we can do the same thing with 'B' and 'C' in the first row and similarly, we can repeat the process for the 2nd and the 3rd row. So, the total number of ways will be 9*8^N (Name this value as X2).

Find the number of cases with two rows same (Name this value as X3). This is the trickiest part of the question. I'll explain this at last.

Find the number of cases with all the three rows same but we can't have the same letter in a single column. This is pretty easy and is equivalent to the number of ways to fill a single column and 3 rows. So, the answer is 24 for this scenario (Name this value as X4).

Now, the final answer will be X1-X2+X3-X4.

Now, coming back to the answer for 2nd scenario. So, we will try to find the answer for the case when the first row and second row is same and we can repeat that process for the 2nd row and 3rd row AND 1st row and 3rd row. Basically, we can multiply the answer we will calculate now with 3. Okay, now take only the first column. Now, you can see that there will be 2 scenarios, one will be when the first and second row contains the same letter and in that case, we have to place a different letter in the 3rd row because else we will violate our condition of the distinct column. So, the total number of ways in the first scenario will be 3*2^N (I have skipped some part but I have provided the exact reason and a little further thinking and you will get the solution). Now, for the next scene when the first and second row contains different letters. In that case, you can place any letter in the 3rd row. Again try to think a little more and you will get the answer as 6*3^N. So, the total answer will be 3*2^N + 6*3^N. And as I said before we need to multiply it by 3 (Number of ways to choose 2 rows from 3 rows). So, X3 will be 3*(3*2^N + 6*3^N).

The complexity is pretty direct, you can do precomputation or apply exponent function every time.

Thanks.

Upvotes: 3

Ante
Ante

Reputation: 5458

This is combinatorial question, for sure it is better to post questions like this on math.stackexchange.com.

A row can be in two different configurations: having two colors (ABA) and having three colors (ABC). If we have last row of some configuration, lets check possibilities for next row.

A | B B B C C
B | A A C A A
A | B C B B C

A | B B B C
B | A C C A
C | B A B B

Set:

  • A_n : number of dimension n matrices where last row is of ABA configuration,
  • C_n : number of dimension n matrices where last row is of ABC configuration,
  • X_n : number of dimension n matrices = A_n + C_n.

From upper list of possibile next row it holds:

A_n = 3 * A_(n-1) + 2 * C_(n-1) = 2 * X_(n-1) + A_(n-1)
C_n = 2 * A_(n-1) + 2 * C_(n-1) = 2 * X_(n-1)
=>
X_n = 4 * X_(n-1) + A_(n-1)

Result to question is X_n, for which calculation A_n is needed, and initial values are A_1=6, X_1=12.

Update:

Search in OEIS for values 2, 9, 41, 187 (upper sequence if colors are not important, real number divided by 6), produces sequence A020698. Sequence mentions similar problem, and suggests that upper recursion can be stated in simpler manner: 

X_n = 4 * X_(n-1) + A_(n-1)
    = 4 * X_(n-1) + A_(n-1) + X_(n-1) - X_(n-1)
    = 5 * X_(n-1) + 2 * X_(n-2) + A_(n-2) - 4 * X_(n-2) - A_(n-2)
    = 5 * X_(n-1) - 2 * X_(n-2)

Upvotes: 0

Related Questions