2

I came across this problem:

https://plus.maths.org/content/tricky-teacups

Basically how many 4x4 Graeco-Latin squares are there?

I get 6912 - brief description of method below. I can't see this figure anywhere, and wanted to validate my thinking if anyone can help:

Use notation 00,01,02,03,10,... etc.

Then it suffices to count the Graeco-Latin squares where the entries in the top row are: 00,1a,2b,3c and the entries in the left column are 00,1d,2e,3f for some a,b,c,d,e,f.

This is because we can express any Graeco-Latin square in this form by switching rows and columns, and there are 576 ways to do this, i.e. 4! times 4!, so we can count solutions of this form and multiply by 576.

Then by permuting 1,2 and 3 in the second Latin square (i.e. the second coordinate) we can assume that a=1,b=2,c=3. This can be done in 3! ways, so we can count solutions of this form - where the top row is 00,11,22,33 - and multiply by 3!*576=3456.

There are then only two possibilities for the left column:

00,12,23,31 and 00,13,21,32

This gives us 2x3456=6912 permutations.

One can now check that with the top row as described, and the left column in either form described above, there is a unique solution. This is slightly harder to explain but it follows with a bit of logic.

Hence the answer seems to be 6912.

I would welcome any other perspective on this!

RobPratt
  • 45,619
William Gibbons
  • 69
  • Your link indicates "there are a total of 1152 solutions". – Calvin Lin Oct 22 '23 at 21:02
  • 2
    There are indeed 6912 solutions, confirmed with a "brute force" Python program. The number may be reduced if there are additional constraints, i.e. if we give a condition for two solutions to be considered equivalent. – Jean-Claude Arbaut Oct 22 '23 at 21:51
  • 1
    I think the figure of 1152 is wrong in the article; it's actually the answer to a different question, where there are constraints on the diagonals as well. See discussion of it on this wiki page - https://en.wikipedia.org/wiki/Mutually_orthogonal_Latin_squares – William Gibbons Oct 22 '23 at 23:03
  • 1
    Here is the program if you want to check or play with it: https://github.com/jcarbaut/graeco_latin/blob/main/graeco_latin.py – Jean-Claude Arbaut Oct 22 '23 at 23:03
  • Also confirmed by A072377 on OEIS (you have to double the values, as explained in the comments). This question is also related. The number of reduced G-L squares may be found in A266166, and the program also prints the list of reduced squares (and there are indeed 2 of them). – Jean-Claude Arbaut Oct 22 '23 at 23:23

0 Answers0