Given a $3 \times N$ matrix and three colors $a$, $b$ and $c$. In how many ways can all the cells be colored such that no row and no column contains all the cells of same color ?
I could not reach to any logical approach to the problem .
[Math] Find the no. of ways to color the matrix..
combinatorics
Related Solutions
The exact number of latin squares of order n is known only up to n = 11, and these counts are reflected in the OEIS and Wikipedia entries already linked in the Comments.
For counting "diagonal" latin squares I could not find any ready online reference, so I wrote a quick Prolog program that provides solutions for the smaller orders.
Note that for the sake of counting we may assume a particular first row of the latin square, so that if the first row is $(1,2,...,n)$ it is in partially reduced form (reduced form having also the first column in standard order).
For n = 1 there is the one (trivial) case.
For n = 2,3 one quickly finds there are no diagonal latin squares.
For n = 4 there are two cases in partially reduced form. Therefore the total count is 2*4! = 48.
For n = 5 there are eight cases in partially reduced form, for a total count of 8*5! = 960.
My code is not optimized for speed but is clear, so the next step is to refactor and impose constraints in a more efficient manner to make some higher orders feasible.
Added:
For n = 6 there are 128 cases in partially reduced form, for a total count of 128*6! = 92160. This result was confirmed by a computation using a different normalization, see discussion below.
For n = 7 my preliminary result is a total count of 171200*7! = 862,848,000 solutions.
Using the partially reduced form (first row in standard order) the n = 6 case was enumerated in 6.3 seconds. Analyzing the time consumed in building stages of the search space suggested that normalizing the main diagonal (in standard order) would be better. I posted a Question here, Counting some special derangements, motivated by how this constrains the choice of anti-diagonals. Another feature of this approach is cutting the enumeration in half via the action of matrix transpose.
These efficiencies reduced the computation time for n = 6 to 1.5 seconds. Despite their use in the n = 7 case, the increased size of the search space led to a running time of 1776 seconds, nearly half an hour.
Such a three-order of magnitude increase in running time suggests that the n = 8 case will not be easily solved on a single CPU, even if the code were compiled instead of interpreted. [Update: For the n = 8 case there are 7450228224*8! = 300,393,201,991,680 diagonal latin squares. This was computed on a single CPU through a combination of speeding up the code that searches on a single main diagonal/anti-diagonal assignment and reducing the number of such assignments by equivalences. The code now runs such a single assignment in 1-2 hours. Given normalization of the main diagonal to the identity sequence $1,2,..,8$, there are 4,752 possibilities (µ-derangements) for the anti-diagonal. A first reduction to 630 equivalences classes is made by using orbits under a dihedral group action. A further reduction to 114 enlarged equivalence classes results from taking "orbits of orbits" under a group isomorphic to $(\mathbb{Z}/2\mathbb{Z})^4$ acting by conjugation. Finally it appears we actually need only count 18 distinct cases due to equivalences of a more contingent nature than those group symmetries. Similar results should apply to solving n = 9, though searching each given µ-derangement will take more time.]
While seeking citations for counts of diagonal latin squares I came across this interesting 2009 paper by Zhang and Ma, Counting solutions for the N-queens and Latin-square problems by Monte Carlo simulations, which is freely available through NIH's Pub Med Central. Perhaps their technique could be adapted for estimating counts of diagonal latin squares of "large" orders. More recently (2017) a report Using Volunteer Computing to Study Some Features of Diagonal Latin Squares describes tactics to count them up to order $n=8$.
The number of ways to color the shoes so that three pairs are odd-colored is $$ N = \text{(number of ways to pick three pairs)} * \text{(number of ways to color each odd pair)}^3 * \text{(number of ways to color the one remaining pair)} $$ which is $$ N = C(4,3) * (12)^3 * 4 = 4 * 12^3 * 4. $$ It looks like you forgot the fact that the remaining pair (whose shoes are the same color) can have any one of four colors.
Combined with the case where all four pairs are odd-colored, the answer then works out to be $28 * 12^3 = 48384$.
Best Answer
For $i=1,2,3$ let $R_i$ denote the set of colourings such that the cells in row $i$ get the same color.
For $j=1,\dots,N$ let $C_j$ denote the set of colourings such that the cells in column $j$ get the same color.
Then to be found is: $$3^{3N}-|R_1\cup R_2\cup R_3\cup C_1\cup\cdots\cup C_N|\tag1$$ For this we use inclusion/exclusion combined with symmetry. First an oversight of the terms that will show up in $(1)$
$\begin{array}{cccc} \text{term in }\left(1\right) & & & \text{coefficient in (1)}\\ \left|C_{1}\cap\cdots\cap C_{k}\right|=3^{3N-2k} & \text{for }k=1,\dots,N & & \binom{N}{k}\binom{3}{0}\left(-1\right)^{k}\\ \left|R_{1}\cap C_{1}\cap\cdots\cap C_{k}\right|=3^{2N-2k+1} & \text{for }k=1,\dots,N & & \binom{N}{k}\binom{3}{1}\left(-1\right)^{k+1}\\ \left|R_{1}\cap R_{2}\cap C_{1}\cap\cdots\cap C_{k}\right|=3^{N-k+1} & \text{for }k=1,\dots,N & & \binom{N}{k}\binom{3}{2}\left(-1\right)^{k+2}\\ \left|R_{1}\cap R_{2}\cap R_{3}\cap C_{1}\cap\cdots\cap C_{k}\right|=3 & \text{for }k=1,\dots,N & & \binom{N}{k}\binom{3}{3}\left(-1\right)^{k+3}\\ \left|R_{1}\right|=3^{2N+1} & & & \binom{N}{0}\binom{3}{1}\left(-1\right)^{1}\\ \left|R_{1}\cap R_{2}\right|=3^{N+2} & & & \binom{N}{0}\binom{3}{2}\left(-1\right)^{2}\\ \left|R_{1}\cap R_{2}\cap R_{3}\right|=27 & & & \binom{N}{0}\binom{3}{3}\left(-1\right)^{3} \end{array}$
Working this out we finally end up with:$$18\cdot3^N+24^N-9\cdot8^N+9\cdot2^N-24\tag2$$
possibilities. Note that $(2)$ gives $0$ for $N=1$ and gives $174$ for $N=2$.