The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A344692 Irregular triangle read by rows in which T(n,k) is the number of stable matchings in the stable marriage problem with n men and n women such that there exists a stable matching with an egalitarian cost of k. 1
 0, 1, 0, 0, 0, 2, 8, 8, 0, 0, 0, 0, 0, 384, 2304, 7488, 14592, 18072, 13104, 4380, 0, 0, 0, 0, 0, 0, 0, 40310784, 322486272, 1397440512, 4299816960, 10080681984, 18632540160, 27586068480, 32664453120, 30544625664, 21941452800, 11480334336, 3963617280, 707788800, 0 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,6 COMMENTS The egalitarian cost of a stable matching is the sum of the mutual rankings of the people in couples. Each preference profile with n men and women that has m different stable matchings with an egalitarian cost of k contributes m to T(n,k). The sequence that counts these m matchings as one is A344691. The lowest and, therefore, optimal mutual ranking of two people is 2, which occurs when they rank each other first. Thus, the smallest possible egalitarian cost of a stable matching with n men and n women is 2*n. So, for k < 2*n, T(n,k) = 0. LINKS Table of n, a(n) for n=1..41. EXAMPLE Triangle begins: 0, 1; 0, 0, 0, 2, 8, 8; 0, 0, 0, 0, 0, 384, 2304, 7488, 14592, 18072, 13104, 4380; 0, 0, 0, 0, 0, 0, 0, 40310784, 322486272, 1397440512, ... ; ... The n-th row starts with 2*n-1 zeros. The total number of terms in row 3 and 4 is 12 and 20 respectively. If two people rank each other first, they are called soulmates. Therefore, if the egalitarian cost is 2*n then there are n pairs of soulmates. A343698(n) counts preference profiles with n men and n women that have n pairs of soulmates. Moreover, if we have n pairs of soulmates in a profile, there's only one stable matching with egalitarian cost 2n. Thus, we have T(n,2n) = A343698(n). If n = 2 and k = 4, we have two pairs of soulmates. There are two preference profiles like this. In the first profile, the first man and the first woman are soulmates as well as the second man and the second woman. In the second profile, the first man and the second woman as well as the second man and the first woman are soulmates. Thus T(2,4) = 2. CROSSREFS Cf. A185141, A343698, A344691. Sequence in context: A166539 A344718 A075429 * A256166 A021976 A241294 Adjacent sequences: A344689 A344690 A344691 * A344693 A344694 A344695 KEYWORD nonn,tabf 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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 18 08:45 EDT 2024. Contains 372618 sequences. (Running on oeis4.)