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

1, 10, 23436, 55037822976, 309586821132441600000, 9704204980882671472665034752000000, 3411909590124519376908837990487929799751761920000000, 24394862766922609598505096548473341484170343775734092352694570188800000000

Offset: 1

Author

Dan Eilers, Jan 29 2023

Keywords

• nonn

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.

Examples

			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.
		

Links

• Wikipedia, Stable Marriage Problem

Crossrefs

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

Programs

Mathematica

Table[((n!)^n) * ((n!)^n + 1) / 2, {n, 1, 8}]

Formula

a(n) = A000217(A036740(n)).

a(n) = ((n!)^n) * ((n!)^n + 1) / 2.