A069124 Number of stable matchings in a certain form of Pseudo-Latin squares of order n based on Latin subsquares.

1, 2, 3, 10, 12, 32, 42, 268, 288, 656, 924, 4360, 3816, 11336, 13536, 195472, 200832, 423104, 618576, 2404960, 2506464, 6994784, 8820864, 85524160, 60669696, 145981952, 194348448, 1073479840

Offset

1,2

Comments

a(n) is from Table 1 of Thurber's linked paper. The particular form of Pseudo-Latin squares is based on upper-left subsquares of the power-of-2 Latin squares of A005154, defined as G(n) in Section 3 of Thurber's paper. - Dan Eilers, May 16 2025

There is a possibility that some of the terms in this sequence from a(7) onward are incorrect. See A371810 for an alternative. - Sean A. Irvine, Apr 16 2024

a(7)=42 verified using MiniZinc, see linked file with details. - Dan Eilers, May 14 2025

Links

Table of n, a(n) for n=1..28.

Matvey Borodin, Eric Chen, Aidan Duncan, Tanya Khovanova, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, and Michael Voigt, The Stable Matching Problem and Sudoku, arXiv:2108.02654 [math.HO], 2021.

Matvey Borodin, Eric Chen, Aidan Duncan, Tanya Khovanova, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, and Michael Voigt, Sequences of the Stable Matching Problem, arXiv:2201.00645 [math.HO], 2021.

Matvey Borodin, Eric Chen, Aidan Duncan, Tanya Khovanova, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, and Michael Voigt, The Stable Marriage Problem and Sudoku, College Math. J. (2023).

Dan Eilers, Response to Sean A. Irvine comment regarding a(7)=42, 2025.

Peter J. Stuckey, Kim Marriott, and Guido Tack, The MiniZinc Handbook, Listing 2.2.12, stable-marriage.mzn, Version 2.9.2, 6 March 2025.

E. G. Thurber, Concerning the maximum number of stable matchings in the stable marriage problem, Discrete Math., 248 (2002), 195-219.

Crossrefs

Cf. A371810.

Cf. A005154 (power-of-2 Latin squares used as basis for subsquares). - Dan Eilers, May 16 2025

Sequence in context: A004679 A168060 A306076 * A371810 A218028 A067769

Adjacent sequences: A069121 A069122 A069123 * A069125 A069126 A069127

Keyword

nonn,more

Author

N. J. A. Sloane, Apr 12 2002

Extensions

Name edited by Dan Eilers, May 16 2025

Status

approved