login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 men-proposing Gale-Shapley algorithm on such a set of preferences ends in one round, since every woman receives one proposal in the first round. Similarly, the women-proposing Gale-Shapley algorithm ends in one round.

LINKS

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

Wikipedia, Gale-Shapley 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 22 00:08 EST 2022. Contains 350481 sequences. (Running on oeis4.)