A343700 -id:A343700 - cp's OEIS frontend

A343698 a(n) is the number of preference profiles in the stable marriage problem with n men and n women such that there are n pairs of soulmates (people who rank each other first).

1, 2, 384, 40310784, 7608405715845120, 6419592322744320000000000000, 50709051409862934701619019776000000000000000, 6988904507653043786857875068352862005134308147200000000000000000

Offset: 1

Tanya Khovanova and MIT PRIMES STEP Senior group, May 26 2021

nonn

For such profiles, each person has exactly one valid partner: their soulmate. Consequently, there is only one stable matching: where the soulmates are married to each other.
For these profiles, the Gale-Shapley algorithm, whether it is men-proposing or women proposing, ends in one round.
This is a subsequence of A001013.

			For n = 3, there are 3! = 6 ways to pair the men and women into soulmate pairs, then 2! ways to finish each person's preference profile, making 6 * 2!^6 = 384 ways to set up the preference profiles.

Michael De Vlieger, Table of n, a(n) for n = 1..23
Matvey Borodin, Eric Chen, Aidan Duncan, Tanya Khovanova, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, and Michael Voigt, Sequences of the Stable Matching Problem, arXiv:2201.00645 [math.HO], 2021.
Wikipedia, Gale-Shapley algorithm.

Cf. A001013, A185141, A343699, A343700.

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

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

A284458 Number of pairs (f,g) of endofunctions on [n] such that the composite function gf has no fixed point.

Original entry on oeis.org

1, 0, 2, 156, 16920, 2764880, 650696400, 210105425628, 89425255439744, 48588905856409920, 32845298636854828800, 27047610425293718239100, 26664178085975252011318272, 31009985808408471580603417296, 42017027730087624384021945067520

Offset: 0

Robert FERREOL, Mar 27 2017

nonn

Consider n boys and n girls, each boy secretly loving a girl and vice versa. The probability that no couple could be formed is a(n)/n^(2n).
a(n) is the number of pairs of binary matrices n X n (M, N), M having only one 1 per row, N having only one 1 per column, such that M + N has no coefficient equal to 2.
Limit_{n -> infinity} a(n)/n^(2n) = 1/e.

			For two boys A,B and two girls A',B', the a(2) possibilities are:
A loves A' who loves B who loves B' who loves A;
A loves B' who loves B who loves A' who loves A.

Robert Israel, Table of n, a(n) for n = 0..214
Math StackExchange, An unexpected application of non-trivial combinatorics, 2014.
Math StackExchange, Couple Probability, 2014.
Eric Weisstein's MathWorld, Confluent Hypergeometric Function of the Second Kind

Cf. A065440, A350558, A343700.

a:=n->add((-1)^k*binomial(n,k)^2*k!*n^(2*(n-k)),k=0..n):
seq(a(n),n=0..15);

Table[Sum[(-1)^k Binomial[n,k]^2 * k! * n^(2*(n - k)), {k, 0, n}], {n, 1, 15}] (* Indranil Ghosh, Mar 27 2017 *)
Table[HypergeometricU[-n, 1, n^2], {n, 1, 15}] (* Jean-François Alcover, Mar 29 2017 *)

a(n) = sum(k=0, n, (-1)^k * binomial(n,k)^2 * k! * n^(2*(n-k))); \\ Michel Marcus, Apr 04 2017

a(n) = Sum_{k=0..n} (-1)^k * binomial(n,k)^2 * k! * n^(2*(n-k)).

a(n) = A343700(n)/A350558(n). - Dan Eilers, Jan 17 2023

A343699 a(n) is the number of preference profiles in the stable marriage problem with n men and n women with n - 1 pairs of soulmates (people who rank each other first).

Original entry on oeis.org

0, 12, 9216, 2418647040, 913008685901414400, 1348114387776307200000000000000, 17038241273713946059743990644736000000000000000, 3522407871857134068576369034449842450587691306188800000000000000000

Offset: 1

Tanya Khovanova and MIT PRIMES STEP Senior group, May 26 2021

nonn

Such profiles have exactly one stable matching, where soulmates are married to each other.

The men-proposing Gale-Shapley algorithm when used on these preference profiles will end in j rounds if the man in the non-soulmate pair ranks his partner as j-th. A similar statement is true for the women-proposing Gale-Shapley algorithm.

			When n = 2, there are 2 ways to pick the man in the soulmate pair and 2 ways to pick the woman in the soulmate pair. After this, the soulmate's preference profiles are fixed. There are 4 ways to complete the profiles for the other two people, but 1 of the ways creates a second pair of soulmates, which is forbidden. Thus, there are 12 profiles with exactly one pair of soulmates.

Michael De Vlieger, Table of n, a(n) for n = 1..23
Matvey Borodin, Eric Chen, Aidan Duncan, Tanya Khovanova, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, and Michael Voigt, Sequences of the Stable Matching Problem, arXiv:2201.00645 [math.HO], 2021.
Wikipedia, Gale-Shapley algorithm.

Cf. A185141, A343698, A343700.

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

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

A344663 a(n) is the number of preference profiles in the stable marriage problem with n men and n women where the men's preferences form a Latin square when arranged in a matrix, and no man and woman rank each other first.

Original entry on oeis.org

0, 2, 768, 60466176, 1315033086689280, 37924385587200000000000000, 1726298879786383239996474654720000000000, 261072919520121696668385285116754694244904468480000000000, 208836950100011929062766575947297434628338701720339215752571230617600000000000, 1378135848291144955393621267341374054991268978878673434553714544944450408726397427961036800000000000000

Offset: 1

Tanya Khovanova and MIT PRIMES STEP Senior group, May 31 2021

nonn

This sequence is in contrast to A344662: a(n) is the number of preference profiles in the stable marriage problem with n men and n women so that they form n pairs of people of different genders who rank each other first, and so that the men's preferences form a Latin square when arranged in a matrix.
Two people who rank each other first are called soulmates. Thus, the profiles in this sequence have no soulmate pairs.
The number of profiles without soulmates is counted by sequence A343700. The number of profiles such that the men's preferences form a Latin square is counted by A343696. The profiles in this sequence are the intersection of profiles in A343696 and A343700.
The men-proposing Gale-Shapley algorithm on the preference profiles described by this sequence ends in one round.

			For n = 3, there are A002860(3) = 12 ways to set up the men's preference profiles, where A002860(n) is the number of Latin squares of order n. Then, since the women can't rank the men who ranked them first as their first preference, there are 2^3 = 8 ways to set up the women's first preferences, and then 2!^3 = 8 ways to finish the women's profiles. So, A344663(3) = 12 * 8 * 8 = 768 preference profiles.

Matvey Borodin, Eric Chen, Aidan Duncan, Tanya Khovanova, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, and Michael Voigt, Sequences of the Stable Matching Problem, arXiv:2201.00645 [math.HO], 2021.
Wikipedia, Gale-Shapley algorithm.

Cf. A002860, A185141, A343696, A344662, A343700.

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

A350558 a(n) = (n-1)!^(2n).

Original entry on oeis.org

1, 1, 64, 1679616, 63403380965376, 8916100448256000000000000, 10061319724179153710638694400000000000000, 173335925289013982808975076100021379095592960000000000000000, 79317573895713454077105543742169655162315106629579798748776628224000000000000000000

Offset: 1

Dan Eilers, Feb 15 2022

nonn

a(n) is the number of ways to arrange the remaining preferences in the stable marriage problem of order n after the first choice of each participant has been determined. The first choices are often treated separately in order to avoid mutual first choices, or to avoid multiple participants with the same first choice.

Matvey Borodin, Eric Chen, Aidan Duncan, Tanya Khovanova, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, and Michael Voigt, Sequences of the Stable Matching Problem, arXiv:2201.00645 [math.HO], 2021.

Cf. A000142, A284458, A343698, A343699, A343700.

Mathematica
```
Table[(n-1)!^(2n),{n,1,9}]
```

a(n) = (n-1)!^(2n).
a(n) = A343700(n)/A284458(n).
a(n) = A343698(n)/A000142(n).
a(n) = A343699(n)/((n-1)!*n^2*(n^2-1)).
a(n) = A343699(n)/(A000142(n)*n*(n^2-1)).

A360213 Number of distinct stable marriage problem instances up to gender exchange.

Original entry on oeis.org

1, 10, 23436, 55037822976, 309586821132441600000, 9704204980882671472665034752000000, 3411909590124519376908837990487929799751761920000000, 24394862766922609598505096548473341484170343775734092352694570188800000000

Offset: 1

Dan Eilers, Jan 29 2023

nonn

In the Stable Marriage Problem, the men's and women's preference lists can be swapped without affecting the number of blocking pairs or stable matchings, because the definitions of blocking pairs and stable matchings are symmetrical with respect to gender. a(n) is the number of instances in a canonical form where the men's preferences are lexicographically less than or equal to the women's preferences.
The A185141(n) instances of order n can be arranged in a square table with rows and columns indexed respectively by all possible men's and women's preferences in lexical order. The main diagonal of the square would be instances with men's preferences equal to women's preferences. The upper triangular region above the diagonal would contain instances with men's preferences less than women's preferences. The number of rows and columns in the table is given by A036740. The number of elements in the upper triangular region of a square, including the diagonal, is given by A000217. So a(n) composes A000217 with A036740 (performing A036740 first).
This sequence is like A351409 and A343700 in that they all involve means of reducing the search space, applied either individually or in combination, when searching for instances that maximize the number of stable matchings.

			For order 2 we have A185141(2) = 16 instances that can be arranged in a 4 X 4 square with A000217(4) = (4 * 5) / 2 = 10 distinct instances up to gender exchange in the upper triangular region including the diagonal. So a(2) = 10.

Wikipedia, Stable Marriage Problem

Cf. A185141, A036740, A000217, A351409, A343700.

Table[((n!)^n) * ((n!)^n + 1) / 2, {n, 1, 8}]

a(n) = A000217(A036740(n)).

a(n) = ((n!)^n) * ((n!)^n + 1) / 2.

cp's OEIS Frontend

A343698 a(n) is the number of preference profiles in the stable marriage problem with n men and n women such that there are n pairs of soulmates (people who rank each other first).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A284458 Number of pairs (f,g) of endofunctions on [n] such that the composite function gf has no fixed point.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A343699 a(n) is the number of preference profiles in the stable marriage problem with n men and n women with n - 1 pairs of soulmates (people who rank each other first).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A344663 a(n) is the number of preference profiles in the stable marriage problem with n men and n women where the men's preferences form a Latin square when arranged in a matrix, and no man and woman rank each other first.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A350558 a(n) = (n-1)!^(2n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A360213 Number of distinct stable marriage problem instances up to gender exchange.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula