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!)
A343694 a(n) is the number of men's preference profiles in the stable marriage problem with n men and n women, such that all men prefer different women as their first choices. 2
1, 2, 48, 31104, 955514880, 2149908480000000, 505542895416115200000000, 16786680128857246009393152000000000, 102199258264429373853760111996211036160000000000, 143679021498505654124337567125614729953051527872512000000000000 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

For such a preference profile, the men-proposing Gale-Shapley algorithm ends in one round since each woman receives exactly one proposal in the first round.

This sequence also counts the preference profiles for n men who rank n women such that all men prefer different women as their i-th choice, for an i between 1 and n, inclusive.

LINKS

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

Wikipedia, Gale-Shapley algorithm.

FORMULA

a(n) = n! * (n-1)!^n.

EXAMPLE

For n=2, there are two ways to pick men's first preferences, and then one way to complete the preference profile, making a total of 2 preference profiles.

MATHEMATICA

Table[n! (n - 1)!^n, {n, 10}]

CROSSREFS

Cf. A001013, A185141, A343474, A343695, A342573, A340890.

Sequence in context: A081960 A123742 A203311 * A295177 A098694 A137592

Adjacent sequences:  A343691 A343692 A343693 * A343695 A343696 A343697

KEYWORD

nonn

AUTHOR

Tanya Khovanova and MIT PRIMES STEP Senior group, May 25 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 28 21:23 EST 2021. Contains 349415 sequences. (Running on oeis4.)