A360213 Number of distinct stable marriage problem instances up to gender exchange.

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.

Links

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

Wikipedia, Stable Marriage Problem

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

Cf. A185141, A036740, A000217, A351409, A343700.

Sequence in context: A203466 A203695 A181017 * A055321 A092300 A048916

Adjacent sequences: A360210 A360211 A360212 * A360214 A360215 A360216

Keyword

nonn

Author

Dan Eilers, Jan 29 2023

Status

approved