An n x n matrix is called a Latin Square if each of the integers 1,2,3...n occurs exactly once in each row and column. Find the number of distinct 4 x 4 Latin Square.
Thanks for the help!
Regards,
Hello VedicmathsAccording the to Wikipedia article, Latin square - Wikipedia, the free encyclopedia, there are 576 distinct 4 x 4 Latin Squares, but there's no straightforward formula for calculating the number of different n x n Latin Squares.
So, how do we get 576? One way is as follows:
There are 4! = 24 ways of arranging the numbers in row 1. (That's the easy bit!)
The numbers in row 2 are obviously all in different columns from row 1, but they are different in 2 distinct ways:
- Either (a) they form a pattern with row 1 like this: . In other words, they form two separate pairs: and . Now we can choose the element to go in row 2, column 1 in 3 ways, and, if this 2-pair pattern is to be created, the remaining elements fit in only one way. There are thus 3 ways of creating this pattern in rows 1 and 2.
- Or (b) they do not form a 2-pair pattern, but are arranged instead like this , or something similar. With each of the 3 choices of column 1, row 2, you'll now find that there are 2 possible ways of filling in the remaining 3 columns of row 2. Total 6 ways.
The number of ways of completing row 3 depends upon which pattern (a) or (b) was chosen in rows 1 and 2.
With each of the pattern (a) arrangements for rows 1 and 2, there are 2 ways of choosing the first element in row 3, and then 1 way of placing its 'partner' from the 2-pair pattern. There are then 2 ways of arranging the remaining 2 elements. So the number of ways of arranging row 3 is 2 x 2 = 4.
With a pattern (b) arrangement for rows 1 and 2, there are again 2 choices for the first element in row 3, but the remaining elements can be chosen in only 1 way.
Thus, for rows 2 and 3, there are 3 x 4 + 6 x 2 = 24 possible arrangements altogether.
Obviously, once rows 1 to 3 have been chosen, row 4 can then only be arranged in 1 way.
So the total number altogether = 24 x 24 = 576.
Grandad