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

Author

N. J. A. Sloane, Apr 12 2002

Keywords

• nonn
• more

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

• 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

Extensions

Name edited by Dan Eilers, May 16 2025