login
A360213
Number of distinct stable marriage problem instances up to gender exchange.
0
1, 10, 23436, 55037822976, 309586821132441600000, 9704204980882671472665034752000000, 3411909590124519376908837990487929799751761920000000, 24394862766922609598505096548473341484170343775734092352694570188800000000
OFFSET
1,2
COMMENTS
In the Stable Marriage Problem, the men's and women's preference lists can be swapped without affecting the number of blocking pairs or stable matchings, because the definitions of blocking pairs and stable matchings are symmetrical with respect to gender. a(n) is the number of instances in a canonical form where the men's preferences are lexicographically less than or equal to the women's preferences.
The A185141(n) instances of order n can be arranged in a square table with rows and columns indexed respectively by all possible men's and women's preferences in lexical order. The main diagonal of the square would be instances with men's preferences equal to women's preferences. The upper triangular region above the diagonal would contain instances with men's preferences less than women's preferences. The number of rows and columns in the table is given by A036740. The number of elements in the upper triangular region of a square, including the diagonal, is given by A000217. So a(n) composes A000217 with A036740 (performing A036740 first).
This sequence is like A351409 and A343700 in that they all involve means of reducing the search space, applied either individually or in combination, when searching for instances that maximize the number of stable matchings.
FORMULA
a(n) = A000217(A036740(n)).
a(n) = ((n!)^n) * ((n!)^n + 1) / 2.
EXAMPLE
For order 2 we have A185141(2) = 16 instances that can be arranged in a 4 X 4 square with A000217(4) = (4 * 5) / 2 = 10 distinct instances up to gender exchange in the upper triangular region including the diagonal. So a(2) = 10.
MATHEMATICA
Table[((n!)^n) * ((n!)^n + 1) / 2, {n, 1, 8}]
CROSSREFS
KEYWORD
nonn
AUTHOR
Dan Eilers, Jan 29 2023
STATUS
approved