A344671 a(n) is the total number of stable matchings for all possible preference profiles in the stable marriage problem with n men and n women such that there exists a married couple where the woman and the man rank each other last.

1, 4, 4608, 5317484544

Offset: 1

Author

Tanya Khovanova and MIT PRIMES STEP Senior group, Jun 05 2021

Keywords

• nonn
• more

Comments

A man and a woman who rank each other last and end up in a marriage are called a hell-couple. A stable matching cannot have more than one hell-couple.

Given a profile, if there exists a stable matching with a hell-couple, then all the stable matchings for this profile have the same hell-couple.

The Gale-Shapley algorithm (both men-proposing and women-proposing) for such a profile needs at least n rounds to terminate.

A344670(n) is the number of preference profiles such that there exists a stable matching with a hell-couple.

This sequence is distinct from A344670 because in this sequence profiles are counted with their respective multiplicity if they yield multiple stable matchings with a hell-couple.

Examples

			For n = 2, each preference profile that has a hell-couple has exactly one stable matching, thus a(2) = A344670(2) = 4. For n > 2, this is no longer the case and a(n) > A344670(n).
		

Links

• 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.
• Wikipedia, Gale-Shapley algorithm.

Crossrefs

Cf. A185141, A344670.