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,3

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

Table of n, a(n) for n=1..5.

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

Formula

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

a(4) = A351430(10).

a(5) = A368419(0).

Crossrefs

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

Sequence in context: A172756 A306304 A175690 * A283896 A284439 A364664

Adjacent sequences: A368430 A368431 A368432 * A368434 A368435 A368436

Keyword

nonn,more,hard

Author

Dan Eilers, Dec 24 2023

Status

approved