HOW MANY STRUCTURALLY DIFFERENT LATIN SQUARES ORDER 5 DO EXIST?

a Solatino-made Latin square
a Solatino-made Latin square
a mix of Solatino cards
a mix of Solatino cards

Abstract.

In this paper (first edition July 2015) is explained how, with help of my home-made Solatino puzzle and some secondary school mathematical insight, I figured out that the number of structurally different (distinct) Latin squares of order 5 is 192. The  tables 1, 2, and 3 (link 2, 5, and 8 in the text) describe them – indirectly, but in an unambiguous way – and prove that the number is correct with respect to the fact that the found  squares together yield exactly the 1344 squares when putting them in the 12345-mode. For the convenience of the reader May 2017 a table 4 has been added in which the 192 squares concerned are shown directly by means of one example each.

author: Willem Barink, Amsterdam, the Netherlands

1. Introduction

Eight years ago I developed my puzzle game Solatino. The aim of the game is  construction of Latin squares of order 5. Unfortunately publishers were not impressed, so I restricted myself to produce the puzzle in small amounts, and sometimes I gave a sample away as a present to interested friends, Latin square hobbyists, and business relations.
The puzzle is not only a puzzle game, it also has some mathematical significance because it gives an answer to the question of how many structurally different Latin squares of order 5 do exist?

With structurally different  ( = structurally distinct) I mean: the squares cannot be made identical by means of rotation, reflection, and/or permutation of the symbols (see elucidation with some examples in paragraph 3).

Up to now (July 2015) I did not find any answer to the above question on Internet and in relevant scientific papers. The quite exhaustive website of Yp de Haan (latinsquares.nl) answers to the analogous question for latin squares of order 4 (the reported and correct number is 12) , but concerning order 5 the item is carefully avoided. Discussions with Yp made me conclude that in the relevant literature up to now the problem is not dealt with, and/or the answer is not yet known.
Nevertheless, for more than 5 years already the answer is reported in the manual of my puzzle game Solatino as a casual information: 192 structurally different squares. This paper describes how I found that number.

2. Solatino

What does my home-made puzzle look like? The manual of the game gives some insight. Also see the two photographs at the top of the paper.

See and read link 1,  Manual Solatino.

With link 2 (table 1)  this paper gives the schematic description of the in the manual mentioned 60 cards: 23 structurally different patterns, numbered 1 to 23, and included the amounts and colors in which they are present in the set. With this scheme every addicted and industrious Latin-square-hobbyist can construct his own set of Solatino cards, the necessary requisites can be found in any stationery. (It would certainly help for a better understanding of Latin squares, and this paper!)

See link 2, table 1,  the 23 Solatino patterns

In my approach the 12 black dotted cards play a crucial role in the determination, classification and enumeration of order 5 squares because of the fact that they all contain a central dot, and a central dot does not change place when the square is rotated and/or reflected.

There are 7 structurally different black patterns:
– the patterns 1, 2, 3, and 4, twofold symmetrical, each pattern one card;
– the patterns 5 and 6, singularly symmetrical, both patterns two cards;
– pattern 7, no symmetry, four cards.

The colored cards have no dot in the center. The patterns 8 up to 15 are singularly symmetrical, and occur two cards per pattern, the patterns 16 up to 23 have no symmetry, and occur four cards per pattern. Of course, the distribution of the colors over the different patterns is not chosen arbitrarily; the correctness of the chosen distribution follows directly from the elucidation in link 7, permutations (see there).

The 60 cards form a two-dimensional representation of the 5! = 120 permutations of the row of numbers 1 2 3 4 5. This assertion is further elucidated at the rear of table 1.

3. Structurally different versus structurally identical

For a better understanding of the term structurally different go to link 3, structurally different , where some examples are shown. Keep in mind that every latin square of order 5 can be decomposed in 5 Solatino patterns, and that two squares are necessarily structurally different when their pattern compositions are different. The opposite is not necessarily true (also shown with an example in the linked page).

4. Two problems

4.1. The first problem with investigating the number of structurally different squares of order 5 is: How do I know, after having found 170 squares, that there must be more? Or after having found 212 that I must have made a mistake somewhere?

Therefore you must be acquainted with the in relevant literature well-known number 1344 that represents the number of possibilities to complete a square when the upper row (or any other row or column, my addition WB) has already been filled up as for example 1 2 3 4 5.  (In the further text I call this the 12345-mode)

Note again: For understanding this paper it is important to emphasize that the mentioning of the upper row, such as is done above, is not crucial: Also when I start constructing a square with 1 2 3 4 5  in e.g. the third row,  I have 1344 possibilities to complete the square.

How the number 1344 is arrived at, is described satisfactorily in the relevant literature.

So, the following question may arise: When I have constructed a certain square of order 5, in how many ways can I write this square in the 12345-mode? It is evident that this is 8 at most: Write down  the square in figures starting with filling up the upper row as 1 2 3 4 5, then rotate 90° clockwise and write down again, rotate and write down again, ….. and again, then reflect the square (with Solatino, because of the transparency of the cards: square upside down) , and do the same. So, generally 8 different 12345 notations for one square. But sometimes a square gives  4, or even only 2 different notations, depending on its symmetry.  Read carefully link 4, an example of figuring out the contribution of a square to the 12345-mode. The contribution of a square to the 12345-mode is the crucial control factor in above posed question.

In the square demonstrated in the Solatino manual not any symmetry can be discovered, and therefore the square contributes 8 squares to the 12345-mode. Finding the control factor of a square constructed with Solatino (transparent cards!) goes quite fast. By far most arbitrarily made squares contribute 8 squares to the 12345-mode.

Conclusion: the answer to the above question How do I know ……  is:  If the sum of all control factors of all found structurally different squares is 1344 (and if no mistakes have been made), all possible structurally different squares have been found. 

In link 5, table 2: All 192 structurally different latin squares…,

more profoundly handled further on in the text, the 12345-mode contribution for any square is given in the cf-column (cf = control factor). Generally it is quite easy to find the control factor. For example, when in a square a certain asymmetrical pattern occurs singularly (as for example always pattern 7 does), then the control factor is necessarily  8. When a certain asymmetrical pattern occurs twice in a square (as can occur with patterns 16 up to 23), or sometimes even fourfold ( as can occur with patterns 16, 17, 20 and 21), then the control factor may be 4, or even 2. In case of doubt always follow the safe procedure demonstrated in the above given example (link 4).

4.2. The second problem: I can randomly construct hundreds, or even a thousand of squares, and classify them in table 2 when new, but after having found the far greater part, the chance of finding another new one will diminish to the very frustrating 0, and the list of squares (the growing table 2) will not be complete in many years.

The Solatino puzzle gives a practical solution for the problem because of the possibility of confined, restricted searching. As already stated, the patterns with a central dot are all black, and are numbered 1 to 7. Moreover these 7 patterns can only occur singular in a square. This means that the squares can be classified in 7 groups, according to the black pattern which occurs in the square. And so I did: Found squares with pattern 1 got a 1-number, fore example 101, 102, etc.., squares with pattern 2 got a 2-number, e.g. 201, 202, squares with pattern 3 a 3-number, and so on. See table 2 again (and fancy that the table is not yet complete).

Now I do a crucial assertion: per black oriented pattern the total contribution of squares to the well-known number of 1344 must be equal. And I elucidate this with the very important link 6,  assertion. See there and read the explanation.

The assertion leads immediately to the conclusion  that group 1 contributes 1344/12 = 112 squares to the 12345-mode, as does also group 2, 3, and 4. And also that group 5 and 6 contribute 224 squares, and that group 7 contributes 448 squares.

5.  Confined searching squares restricted to the 1-group

Now, with the above conclusion in mind, we can start trying to find all possible, structurally different squares with pattern 1 in the center. (Of course, we can start with pattern 2, 3, or 4 as well, but why not pattern 1? Anyway, it is better than start with pattern 5, or 6, or even 7, because of the larger amounts of squares in those groups to be found).
With the Solatino cards the searching is quite a pleasant puzzling. It can easily be seen that pattern 1 does not combine with pattern 11, 12, 17 , and 21, so only 12 patterns are left to combine with. To check this see again table 1, the 23 Solatino patterns  , if necessary.
After some nights some hours of pleasant puzzling I had found 19 structurally different squares, of which the total 12345-mode contribution was 112 indeed. So I did not search any further. In table 2 the squares have been numbered LS101 up to LS 119.

For the 2-group  I could have followed the same way of confined searching, and then the 3-group, etc…, but I did not. There is a faster method.

6. Permutations

That method is: systematical permutation acts with the 19 found squares of group 1. Starting with a randomly chosen square of the 1-group I can generate 11 new squares by means of systematical permutations of rows (or columns); 1 belonging to the 2-group, 1 belonging to the 3-group, 1 belonging to the 4-group, 2 belonging to the 5-group, 2 belonging to the 6-group, and 4 belonging to the 7-group. See link 7,  permutations ,  in which I perform the permutation act with LS103 (composition 1, 8, 14, 18, 18), and in which I maintain the third row on its place. And read carefully the explanation.

I performed the permutation act two times per square: as shown in the linked page, and after that with the square rotated 90°. For LS103 the second permutation act yields the same squares as the first, but in a different sequence. Nearly all squares with control factor 2 or 4 do so. Exceptions are LS 119 and LS318. Nearly all squares with control factor 8 give two different rows of squares. Exceptions: LS 530, LS627.

After having executed 2 x 19 = 38 times the permutation act, and having investigated and tabled the yielded squares in table 2 (if new) and in

link 8, table 3: permutation rows ,

I concluded that my work was finished. Because all structurally different squares were found,  as the sum of the control factors of all found squares was 1344.  And the number is, see again table 2: 19 + 20 +18 +17 +31 + 31 + 56 = 192. And indeed, the results of my work were completely in accordance with my assertion done in paragraph 4.2

In  table 3  the results of my permutation acts have been given in a systematical way.  All 192 squares of table 2 have a place in it, a few occur four or three times, the greater part occurs  two, or one time. The red numbers reflect the squares that give a second permutation row containing the same squares as in the first, but in a different sequence. (So, only one row is given.) The other coloured  numbers are squares that have an identical pattern composition, but are nevertheless differently structured. For example LS751, 752 and 753 consist of the patterns 7, 17, 19, 21, and 22, but can be assembled in even three different ways (see table 2 and 3).

7. Conclusion

Table 1, 2 and 3 together demonstrate  that the number of structurally different latin squares of order 5 is 192.  With given tables each square is defined unambiguously, and is ready for construction, taken in account that there are four collections of 5 patterns that can be assembled in two structurally different ways, and one that can be assembled  in three.  The puzzle game Solatino was very helpful in the investigation.

Addendum May 2017

On request of some interested readers I transformed table 2 into a more  accessible table 4, in which all 192 squares concerned are shown directly by means of one example each.  None of the shown squares can be made identical with another one by means of rotation, reflection,and/or permutation of the symbols (digits).

 

 

Acknowledgements.

I thank Yp de Haan for the inspiring discussions with me, and for his exhaustive and instructive website http://www.latinsquares.nl.  And Egbert Nijeboer for his help to make this paper published.

Willem Barink, Amsterdam, July 26, 2015

for contact and/or comments: hw.barink@upcmail.nl or see down under.

Advertisements