cp's OEIS Frontend

a(n) is the number of reduced Stable Marriage Problem instances of order n. In the SMP, relabeling men or women has no effect on the number of stable matchings. So the men and women can be relabeled to normalize the order of man #1's rankings (with woman #1 as his first choice and woman n as his last choice), and to similarly normalize the order of woman #1's rankings, except for her ranking of man #1. This reduces the number of possible instances by a factor of n!(n-1)! (A010790 with shifted offset), from (n!)^(2n) (A185141) to a(n). This reduction is directly analogous to the identical reduction from latin squares (A002860) to reduced latin squares (A000315), and can be directly applied to the Latin Stable Marriage Problem (A351413). As with reduced latin squares, some further reduction is possible analogous to row/column reduced latin squares (A123234).

It is tempting to aim for a reduction of (n!)^2 by simultaneously normalizing all of man #1 and woman #1's preferences, but that isn't possible unless man #1 and woman #1 happen to be mutual first choices.

Applying this reduction to A344669 reduces A344669(2) and A344669(4) to 1, demonstrating that these maximal instances arising in A005154 are unique up to participant relabeling. It raises the question of which other values of n make A344669(n) reducible to 1.

A185141(n) is the total number of preference profiles for n men and n women.

A185141(4) = 110075314176 is the sum of the terms of this sequence.

For 2 men and 2 women, the total number of preference profiles is 16, where 14 profiles have 1 stable matching, and 2 profiles have 2 stable matchings.

For 3 men and 3 women, the total number of preference profiles is 46656, where the number of possible stable matchings ranges from 1 to 3. The distribution is provided by sequence A344666(n).

A185141(n) is the total number of preference profiles for n men and n women.

A185141(3) = 46656 is the sum of the terms of this sequence.

For 2 men and 2 women, the total number of preference profiles is 16, where 14 profiles have 1 stable matching, and 2 profiles have 2 stable matchings.

For 4 men and 4 women, the total number of preference profiles is 110075314176, where the number of possible stable matchings ranges from 1 to 10, excluding 9. The distribution is provided by sequence A344667(n).

A069124(n) provides the lower bound for the maximum number of stable matchings with n men and n women. It is exact for n below 5.

"Reduced" instances are counted, as in A351430 for order 4.

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

The counts are listed in reverse order from A351430 so that the known terms appear first. The first term gives the number of maximal instances (with 16 stable matchings, per A357269).

The total number of reduced instances for order 5 is 214990848000000000, given by A351409(5).

The corresponding sequence for order 3 is [91,957,2840], with 91 maximal instances.

a(0) = A368433(5) = A344669(5) / (5! * 4!).

Results were obtained using the MiniZinc constraint modeling language, by extending the "Model for the Stable Marriage Problem" given in the MiniZinc Handbook, Section 2.2.6.

The first two terms were obtained on a PC with 12GB RAM; the next three terms on a PC with 64GB RAM.

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.