A344665 a(n) is the number of preference profiles in the stable marriage problem with n men and n women, where both the men's preferences and women's preferences form a Latin square when arranged in a matrix, with no paired man and woman who rank each other first.

0, 2, 48, 124416, 9537454080, 243184270049280000, 1390396658530114967961600000, 4352862027490648408300099378983469056000, 11228731998377005106060609036300637077741992056717312000, 36658843398022550531624696117934603340895735930389121945136191766528000000

Offset

1,2

Comments

The profiles in this sequence are the intersection of the profiles in A343696 and A343697. The Gale-Shapley algorithm on such a set of preference profiles ends in one round.

Links

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

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.

Wikipedia, Gale-Shapley algorithm.

Formula

a(n) = A002860(n)^2 * Sum_{i=0..n} (-1)^i/i! = A344664(n) * A000166(n).

Example

For n = 2, there are A002860(2) = 2 ways to set up the men's profiles. Since the women don't want to rank the man who ranked them first as first, there is exactly 1 way to set up the women's profiles. So, there are 2 * 1 = 2 preference profiles for n = 2.

Crossrefs

Cf. A002860, A185141, A343696, A343697, A344664.

Sequence in context: A203778 A203305 A191954 * A212170 A057527 A166475

Adjacent sequences: A344662 A344663 A344664 * A344666 A344667 A344668

Keyword

nonn

Author

Tanya Khovanova and MIT PRIMES STEP Senior group, Jun 22 2021

Status

approved