Number of ways to color houses with no 2 equal colors next to each other and symmetry constraint

Question

There are n houses along the street, and we need to color every with one of 3 colors but there are 2 constraints:

1. Adjacent houses need to have different colors
2. Symmetric houses cannot have the same color. So 1st and nth , 2nd and n - 1st etc.

N is even and is the only input. Count the number of possible colorings modulo 1e+5.

This is most probably dp but the states proved to be difficult for me. I tried doing dp[i][j][k] where we paint i'th house with j'th color when symmetric color is k, but then the problem becomes quite cyclical and I don't know where to go from there.

N/2 + 1st house has both previous and symmetric houses as N/2, and in general, if we fix the color of any house among first n/2, there are 2^(n/2 - 1) ways to color n/2 houses in total. Then it is still unclear how to progress to further states because even though I could calculate the number of colorings for n/2th + 1st house (2^(n/2 - 1) for any color when n/2th color is fixed), I can't necessarily incorporate constraints on symmetry for further houses.

Another thing I noticed is that if we color both ends of the row of houses (so 1st and nth), then we get restrictions but the problem somewhat reduces to size n - 2 and we again need to color 2nd and n-2th houses etc. So maybe there is some solution based on this state transition.

I also tried inclusion / exclusion, and just the first constraint alone is not hard to calculate: 3 * 2^(n - 1), but then the negation of second constraint is hard to calculate: number of colorings where there is more than 1 house with its symmetric house colored the same way, etc, and it didn't quite lead to anywhere.

Would appreciate any help

Answer 1

O(1) solution: Let k=n/2. paint n=2k houses in 2 * 3^k ways.

Explanation:

Let's say our colors are 1,2,3.

Then, let's think about the patterns, represented by A, B, C, with the understanding that for any valid pattern, there are 3 choices for A and 2 for B so the count of valid paintings is 6x the count of valid patterns.

All patterns will be represented with AB as the central pair.

Let's say p(k) is the count of valid patterns of n = 2k houses.

Then p(1) = 1 as AB is the only valid pattern for 2 houses.

Given p(k), how many choices do we have for p(k+1). Well, we only need to care about the endpoints of the patterns of p(k). Each pattern has two different endpoints. Let's say for p(k+1) we always choose our left endpoint first. If it matches the corresponding p(k) right endpoint then there are 2 possibilities for the p(k+1) right endpoint, otherwise there is 1.

Thus p(k+1) = 3 * p(k).

So in general, p(k) = 3^(k-1).

Then the count of paintings of n=2k houses is 6*p(k) = 6 * 3^(k-1) = 2 * 3^k

E.g. here are patterns for early k. To iterate colorings, set ABC in turn to each of 012, 021, 102, 120, 201, 210)

k=1: patterns = [AB]
k=2: patterns = [BABA, BABC, CABA]
k=3: patterns = BABA => [ABABAB, ABABAC, CBABAB]
                BABC => [ABABCB, CBABCA, CBABCB]
                CABA => [ACABAB, ACABAC, BCABAC]