|
|
|
|
| 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.
(history;
published version)
|
|
|
|
|
#10 by Michael De Vlieger at Fri Feb 11 11:52:44 EST 2022
|
|
|
|
|
|
|
|
#9 by Michel Marcus at Fri Feb 11 11:52:04 EST 2022
|
|
|
|
|
|
|
|
#8 by Michael De Vlieger at Fri Feb 11 11:40:55 EST 2022
|
|
|
|
|
|
|
|
#7 by Michael De Vlieger at Fri Feb 11 11:40:53 EST 2022
|
|
| LINKS
|
Matvey Borodin, Eric Chen, Aidan Duncan, Tanya Khovanova, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, and Michael Voigt, <a href="https://arxiv.org/abs/2201.00645">Sequences of the Stable Matching Problem</a>, arXiv:2201.00645 [math.HO], 2021.
|
|
| STATUS
|
approved
editing
|
|
|
|
|
|
|
#6 by N. J. A. Sloane at Mon May 31 21:26:19 EDT 2021
|
|
|
|
|
|
|
|
#5 by Jon E. Schoenfield at Thu May 27 00:39:37 EDT 2021
|
|
|
|
|
|
|
|
#4 by Jon E. Schoenfield at Thu May 27 00:39:23 EDT 2021
|
|
| 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.
|
|
| AUTHOR
|
__Tanya Khovanova_ and MIT PRIMES STEP Senior group, May 26 2021
|
|
| STATUS
|
proposed
editing
|
|
|
|
|
Discussion
|
| Thu May 27
| 00:39
| Jon E. Schoenfield: non-ASCII characters replaced with ASCII characters
|
|
|
|
|
|
|
#3 by Tanya Khovanova at Wed May 26 09:49:35 EDT 2021
|
|
|
|
|
|
|
|
#2 by Tanya Khovanova at Wed May 26 09:49:18 EDT 2021
|
|
| NAME
|
allocateda(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 forform TanyaLatin Khovanovasquares.
|
|
| DATA
|
1, 4, 144, 331776, 26011238400, 660727073341440000, 3779719071732351369216000000, 11832225237539469009819996424230666240000, 30522879094287825948996777484664523152536511038095360000, 99649061600109839440372937690884668992908741561885362729330828902400000000
|
|
| 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
|
Wikipedia, <a href="https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm">Gale-Shapley algorithm</a>.
|
|
| 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.
|
|
| KEYWORD
|
allocated
nonn
|
|
| AUTHOR
|
Tanya Khovanova and MIT PRIMES STEP Senior group, May 26 2021
|
|
| STATUS
|
approved
editing
|
|
|
|
|
|
|
#1 by Tanya Khovanova at Mon Apr 26 13:34:08 EDT 2021
|
|
| NAME
|
allocated for Tanya Khovanova
|
|
| KEYWORD
|
allocated
|
|
| STATUS
|
approved
|
|
|
|
|
|
