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!)
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 man and woman pairs who rank each other first. 1
0, 2, 48, 124416, 9537454080, 243184270049280000, 1390396658530114967961600000, 4352862027490648408300099378983469056000, 11228731998377005106060609036300637077741992056717312000, 36658843398022550531624696117934603340895735930389121945136191766528000000 (list; graph; refs; listen; history; text; internal format)
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.

Wikipedia, Gale-Shapley algorithm.

FORMULA

a(n) = A002860(n)^2/n! * Sum_{i=0...n} [(-1)^i * n!/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

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 26 17:52 EST 2021. Contains 349343 sequences. (Running on oeis4.)