This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A357269 #30 May 16 2025 00:53:10 %S A357269 1,2,3,10,16 %N A357269 Maximum number of stable matchings in the stable marriage problem of order n. %C A357269 Finding a(n) (denoted f(n) in the literature) is a research problem posed by Knuth in 1976 and reiterated by Gusfield and Irving in 1989. %C A357269 a(5)=16 was found by Eilers using a MiniZinc constraint satisfaction model, showing previous lower bound of Eilers reported by Thurber to be exact. %C A357269 A357271 gives lower bounds for a(n) reported by Thurber, previously known to be exact up to n=4, which is not to be confused with A069156 which gives looser lower bounds for n > 11. %C A357269 Thurber proved a(n) to be strictly increasing. %C A357269 There are 176130 reduced instances of order 5 with 16 stable matchings, and 498320 reduced instances with 15 stable matchings, compared with A351430 for order 4, and A369597 for order 3. %C A357269 The total number of reduced instances for order n is A351409(n), which is 214990848000000000 for order 5, so about one in 1.22*10^12 such instances are maximal. %C A357269 The maximum number of stable matchings for order 5, where the men's (or women's, respectively) ranking table is a latin square, is 14, with 300 such reduced instances, making order 5 the first order not containing any maximal instances where the men's ranking table is a Latin square. %D A357269 C. Converse, Lower bounds for the maximum number of stable pairings for the general marriage problem based on the latin marriage problem, Ph. D. Thesis, Claremont Graduate School, Claremont, CA (1992). %D A357269 D. R. Eilers, "The Maximum Number of Stable Matchings in the Stable Marriage Problem of Order 5 is 16". In preparation. %D A357269 D. Gusfield and R. W. Irving, The Stable Marriage Problem: Structure and Algorithms. MIT Press, 1989, (Open Problem #1). %H A357269 A. T. Benjamin, C. Converse, and H. A. Krieger, <a href="https://doi.org/10.1016/0166-218X(95)80006-P">Note. How do I marry thee? Let me count the ways</a>, Discrete Appl. Math. 59 (1995) 285-292. %H A357269 Matvey Borodin, Eric Chen, Aidan Duncan, Tanya Khovanova, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, and Michael Voigt, <a href="https://arxiv.org/abs/2201.00645">Sequences of the Stable Matching Problem</a>, arXiv:2201.00645 [math.HO], 2021, [Section 5, Distribution for the number of stable matchings]. %H A357269 D. E. Knuth, <a href="https://www-cs-faculty.stanford.edu/~knuth/ms.html">Mariages Stables</a>, Presses Univ. de Montréal, 1976 (Research Problem #5). %H A357269 E. G. Thurber, <a href="https://doi.org/10.1016/S0012-365X(01)00194-7">Concerning the maximum number of stable matchings in the stable marriage problem</a>, Discrete Math., 248 (2002), 195-219. %Y A357269 Cf. A357271 and A069156 (lower bound of 16 for a(5)). %Y A357269 Cf. A351430 (order 4), A369597 (order 3). %Y A357269 Cf. A351409 (total number of reduced instances). %K A357269 nonn,more %O A357269 1,2 %A A357269 _Dan Eilers_, Sep 21 2022