login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A344664 a(n) is the number of preference profiles in the stable marriage problem with n men and n women where both the men's and the women's preferences form a Latin square when arranged in a matrix. In addition, it is possible to arrange all people into n man-woman couples such that they rank each other first. 1
1, 2, 24, 13824, 216760320, 917676490752000, 749944260264355430400000, 293457967200879687743551498616832000, 84112872283641495670736269523436185936222748672000, 27460610008848610956892895086773773421767179663217968124264448000000 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Two people who rank each other first are called soulmates. Thus, the profiles in this sequence have n pairs of soulmates.

The profiles with n pairs of soulmates are counted by sequence A343698. The profiles such that the men's preferences form a Latin square are counted by A343696. The profiles such that both men's and women's preferences form a Latin square are counted by A343697. The profiles in this sequence are the intersection of profiles in A343698 and A343697.

Both the men- and the women-proposing Gale-Shapley algorithm on the preference profiles described by this sequence end in one round.

LINKS

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

Wikipedia, Gale-Shapley algorithm.

FORMULA

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

a(n) = A000479(n) * A002860(n).

EXAMPLE

For n = 3, there are A002860(3) = 12 Latin squares of order 3. Thus, there are A002860(3) = 12 ways to set up the men's preference profiles. After that, the women's preference profiles form a Latin square with a fixed first column, as the first column is uniquely defined to generate 3 pairs of soulmates. Thus, there are A002860(3)/3! = 12/6 = 2 ways to set up the women's preference profiles, making a(3) = 12 * 2 = 24 preference profiles.

CROSSREFS

Cf. A000479, A002860, A185141, A343696, A343697, A343698, A344665.

Sequence in context: A066120 A152687 A062716 * A137888 A229333 A338152

Adjacent sequences:  A344661 A344662 A344663 * A344665 A344666 A344667

KEYWORD

nonn

AUTHOR

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

EXTENSIONS

Corrected by Tanya Khovanova, Aug 17 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 November 27 20:49 EST 2021. Contains 349395 sequences. (Running on oeis4.)