

A343697


a(n) is the number of preference profiles in the stable marriage problem with n men and n women such that both the men's and women's profiles form Latin squares.


4



1, 4, 144, 331776, 26011238400, 660727073341440000, 3779719071732351369216000000, 11832225237539469009819996424230666240000, 30522879094287825948996777484664523152536511038095360000, 99649061600109839440372937690884668992908741561885362729330828902400000000
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Equivalently, these are the profiles where each woman is ranked differently by the n men and each man is ranked differently by the women.
The menproposing GaleShapley algorithm on such a set of preferences ends in one round, since every woman receives one proposal in the first round. Similarly, the womenproposing GaleShapley algorithm ends in one round.


LINKS

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


FORMULA

a(n) = A002860(n)^2.


EXAMPLE

There are 12 Latin squares of order 3, where 12 = A002860(3). Thus, for n = 3, there are A002860(3) ways to set up the men's profiles and A002860(3) ways to set up the women's profiles, making A002860(3)^2 = 144 ways to set up all the preference profiles.


CROSSREFS

Cf. A002860, A185141, A343696.
Sequence in context: A203424 A055209 A239350 * A030450 A041629 A278845
Adjacent sequences: A343694 A343695 A343696 * A343698 A343699 A343700


KEYWORD

nonn


AUTHOR

Tanya Khovanova and MIT PRIMES STEP Senior group, May 26 2021


STATUS

approved



