cp's OEIS Frontend

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

%I A360213 #18 Feb 18 2023 20:50:59
%S A360213 1,10,23436,55037822976,309586821132441600000,
%T A360213 9704204980882671472665034752000000,
%U A360213 3411909590124519376908837990487929799751761920000000,24394862766922609598505096548473341484170343775734092352694570188800000000
%N A360213 Number of distinct stable marriage problem instances up to gender exchange.
%C A360213 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.
%C A360213 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).
%C A360213 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.
%H A360213 Wikipedia, <a href="https://en.wikipedia.org/wiki/Stable_marriage_problem">Stable Marriage Problem</a>
%F A360213 a(n) = A000217(A036740(n)).
%F A360213 a(n) = ((n!)^n) * ((n!)^n + 1) / 2.
%e A360213 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.
%t A360213 Table[((n!)^n) * ((n!)^n + 1) / 2, {n, 1, 8}]
%Y A360213 Cf. A185141, A036740, A000217, A351409, A343700.
%K A360213 nonn
%O A360213 1,2
%A A360213 _Dan Eilers_, Jan 29 2023