A351409 a(n) = n*(n!)^(2*n-2).

1, 8, 3888, 764411904, 214990848000000000, 224634374557469245440000000000, 1880461634768804771224006806208512000000000000, 240091793104790737576620139562796649430329798636339200000000000000, 813675117804798213250391541747787241264315446434692481270971279693253181440000000000000000

Offset: 1

Author

Dan Eilers, Feb 11 2022

Keywords

• nonn

Comments

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.

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..20
• 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, [Section 7, Symmetries].

Crossrefs

Cf. A185141, A000315, A351413, A344669.

Programs

Mathematica

a[n_] := n*(n!)^(2*n - 2); Table[a[n], {n, 1, 9}] (* Robert P. P. McKone, Feb 12 2022 *)

PARI

a(n) = n*(n!)^(2*n-2) \\ Andrew Howroyd, Feb 12 2022

Formula

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