A368433 a(n) is the number of reduced instances in the stable marriage problem of order n that generate the maximum possible number of stable matchings.

1, 1, 91, 1, 176130

Offset: 1

Author

Dan Eilers, Dec 24 2023

Keywords

• nonn
• more
• hard

Comments

Reduced instances (A351409) are fewer than all instances by a factor of n!(n-1)! due to participant-renaming isomorphism, analogous to reduced latin squares.

For n in [1,2,4], a(n) = 1 showing uniqueness up to isomorphism.

Links

• David F. Manlove, Algorithmics of Matching Under Preferences, World Scientific (2013) [Section 2.2.2].

Crossrefs

Cf. A344669 (unreduced), A351430 (order 4), A368419 (order 5), A351409 (total reduced instances), A010790 (reduction factor offset by 1).

Formula

a(n) = A344669(n) / A010790(n-1).

a(4) = A351430(10).

a(5) = A368419(0).