cp's OEIS Frontend

Brendan McKay writes: (Start)

"It would be possible to find the counts for n=9 and n=10 using the method of my paper in JCD [see link below]. For n=10 it is probably a 24-digit number. I'll explain the method I used. See the paper above for terminology.

"Is(L) is the autotopism group. Also define the group RC(L) of all autotopisms for which the symbols component is the identity. For any Latin square L we have:

"The isotopy class containing L contains (n!)^3/|Is(L)| squares.

"The RC-equivalence class containing L contains (n!)^2/|RC(L)| squares.

"If L and L' are isotopic then |RC(L)| = |RC(L')|. Therefore the number of RC-equivalence classes in the isotopy class of L is n!*|RC(L)|/|Is(L)|. I modified an existing program slightly to find |RC(L)|/|Is(L)|. and applied it to one square from each isotopy class. The sum of n!*|RC(L)|/|Is(L)| is the total number of RC-equivalence classes. " (End)

This sequence counts unordered pairs. The number of ordered pairs of MOLS is exactly double this sequence.

Here "type" means an equivalence class of Latin squares under the operations of row permutation, column permutation, symbol permutation and transpose. In the 1-factorizations formulation, these operations are labeling of left side, labeling of right side, permuting the order in which the factors are listed and swapping the left and right sides, respectively. - Brendan McKay

There are 6108088657705958932053657 isomorphism classes of one-factorizations of K_{11,11}. - Petteri Kaski (petteri.kaski(AT)cs.helsinki.fi), Sep 18 2009

The values are calculated recursively, based on the characterization by 2009. The number a(5) was found before (2001 and, independently, later works) by exhaustive computer-aided classification of the objects.

The even and odd subsequences are A036980, A036981.

In the Latin Stable Marriage Problem of order n, the sum of a man and woman's rankings of each other is n+1. This implies that the men's and women's ranking tables are Latin squares. As a subproblem of the Stable Marriage Problem, Latin instances provide lower bounds for the maximum number of stable matchings in the general problem, such as A005154 and A065982. For sizes 1 to 4, Latin instances provide exact bounds; they are conjectured to provide exact bounds for sizes a power of 2; they provide the best lower bounds known for sizes 6, 10, 12, and 24, of 48, 1000, 6472, and 126112960, respectively.

The next term, a(8), is conjectured to be 268, consistent with A005154. The minimum number of stable matchings for Latin instances of order n is n, and is realized for the cyclic group of order n. The average number of stable matchings is 7 for n=4 (cf. A351430 showing an average of about 1.5 for the general problem), and benefits from avoidance of mutual first choices and more generally the lack of overlap between the men's and women's preferred matchings. The Latin squares of A005154 and A065982 can be interpreted as multiplication tables of groups, n-th powers of the cyclic group C2 and n-th dihedral groups, respectively.

The sequence decreases from a(4)=10 to a(5)=9, in contrast to the corresponding sequence for the general problem, which Thurber showed to be strictly increasing. This has motivated the study of less restrictive subproblems, such as pseudo-Latin squares (A069124, A069156), Latin x Latin instances (A344664, A344665, A343697), instances where participants have different first choices (A343475, A343694, A343695), or instances with unspecified/tied/template rankings (A284458 with only first choices specified).

The sequence is empirically derived, originally based on reduced Latin squares (A000315). There are fewer instances to try using RC-equivalent Latin squares (A123234) instead of reduced Latin squares.

a(n) is the number of reduced men's ranking tables in the stable marriage problem of order n. In the SMP (as noted in A351409), relabeling men or women has no effect on the number of stable matchings. So the women can be relabeled to normalize the order of man #1's rankings (with woman #1 as his first choice and woman n as his last choice), and then the men except man #1 can be relabeled to normalize the lexicographic order of those men's rankings. Since man #1's rankings end up fixed in natural order, they do not contribute to the number of possibilities, leaving n! multichoose (n-1) ways to arrange the rankings of the other n-1 men.

The number of unreduced men's ranking tables is given by A036740. Relabeling just the women reduces this to A134366. Alternately, relabeling just the men reduces A036740 to A344690. Relabeling both men and women reduces the men's relabeling reduction, A344690, by a factor of (n!+n-1)/n to a(n).

It might be tempting to try to reduce A344690 by a factor of n!, but that doesn't work because not all of man #1's rankings are equally likely after relabeling all the men to give man #1 the lexicographically least rankings.

There is room for further relabeling reduction from a(n), given by A263921. The reduction from a(n) to A263921 is analogous to the reduction from reduced latin squares, A000315, to A123234.

Each of the a(n) reduced men's ranking tables can be combined with the A036740 possible unreduced women's ranking tables to form complete instances, but these instances have more possibilities than A351409. For example, a(3)*A036740(3)=21*216=4536 > A351409(3)=3888. However, fewer possibilities result from using A263921 in place of a(n), although the men's ranking tables of A263921 may not be as straightforward to generate. With A263921(3)=10, 10*216=2160 < 3888.