login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

a(n) is the number of preference profiles in the stable marriage problem with n men and n women that generate the maximum possible number of stable matchings.
6

%I #27 Jan 01 2024 13:30:58

%S 1,2,1092,144,507254400

%N a(n) is the number of preference profiles in the stable marriage problem with n men and n women that generate the maximum possible number of stable matchings.

%C From _Dan Eilers_, Dec 23 2023: (Start)

%C A357271 provides the best known lower bounds for the maximum number of stable matchings of order n.

%C A357269 provides exact results. (End)

%H 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.

%F a(n) = A368433(n) * A010790(n-1). - _Dan Eilers_, Dec 24 2023

%e For n=2, there are 16 possible preference profiles: 14 of them generate one stable matching and 2 of them generate two stable matchings. Thus, a(2) = 2.

%Y Cf. A069124, A185141, A344666, A344667, A344668, A357269, A357271, A368433.

%K nonn,bref,more

%O 1,2

%A _Tanya Khovanova_ and MIT PRIMES STEP Senior group, May 27 2021

%E a(5) from _Dan Eilers_, Dec 23 2023