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!)
A343475 a(n) is the number of preference profiles for n men and n women, where men prefer distinct women as their first choice. 1
1, 8, 10368, 10319560704, 23776267862016000000, 299512499409958993920000000000000, 41761084325232750832975432403386368000000000000000, 117254360528268768669572531322770730078331396796134195200000000000000000, 11151031424792655208856660513601075282865340493496475667265971777832723603783680000000000000000000 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

This sequence is the number of preference profiles for the Stable Marriage Problem such that the male-proposing Gale-Shapley algorithm terminates in one iteration.

This is the same number of preference profiles as when all men rank the different women at the i-th place, where i can be anywhere from 1 to n.

Note this is the same as the number of preference profiles for n men and n women where the women prefer distinct men as their first choice.

LINKS

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

Wikipedia, Gale-Shapley algorithm

FORMULA

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

EXAMPLE

When n = 3, there are 3! = 6 ways to order the women as first preferences for the men, 2!^3 = 8 ways to finish the mens' profiles, and then 3!^3 = 216 ways to complete the womens' profiles, making a total of 6 * 8 * 216 = 10368 preference profiles.

MATHEMATICA

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

CROSSREFS

Cf. A001013, A185141, A342573, A340890.

Sequence in context: A188890 A175881 A165429 * A242852 A079235 A134373

Adjacent sequences:  A343472 A343473 A343474 * A343476 A343477 A343478

KEYWORD

nonn

AUTHOR

Tanya Khovanova and MIT PRIMES STEP Senior group, Apr 16 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 October 18 23:35 EDT 2021. Contains 348071 sequences. (Running on oeis4.)