There are 161,280 Latin squares of dimension 5. I am trying to reduce this number to the number of essentially different grids — for enumerating the Japanese puzzle Futoshiki. To preserve the uniqueness of each puzzle, I am considering grids essentially the same if they can be reached from one another through the operations of rotating the grid or flipping the grid.
In order to consider the operation of flipping (or reflecting) the grid across the diagonal which runs from the top-left to the bottom-right, I am thinking about symmetric Latin squares. That is, Latin squares for which the $ij^{th}$ entry is equal to the $ji^{th}$ entry for all $1\leq i,j\leq n$.
How many of the 161,280 $5\times5$ Latin squares are symmetric?
My first crack at answering it gave me $5!\times4!\times3!\times2!=34560$ — but I'm fairly certain this is incorrect and just a very naive way of trying to solve the problem.
Any help will be greatly appreciated.
Best Answer
You are right to assume that your count is too high. Here is the problem. Suppose that your first row is 12345. Then the first element of the second row is forced to 2 and the remaining elements are some permutation of 1345. But 1345 itself duplicates the 3 in the third column (among other things) when paired with the 12345 you put in the first row, and similarly there are other permutations you have to reject. Only 11 permutations of 1345 actually work (and some of those fail later on when you try to add the remaining rows), so you cannot just put in a factor of 4!=24 for the second row.
The proper method starts with putting a fixed ordering, 12345, in the first row and fixing the first column accordingly. You then have a choice of 56 reduced Latin squares given here (you should think of each number in the referenced site as increased by 1 to match my nomenclature). Count the number of these reduced squares which are symmetric (not all of them are), then since you can freely permute the first row multiply that result by 5!=120.