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.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A344691 Irregular triangle T(n,k) read by rows, where T(n,k) is the number of preference profiles 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

%I #24 Sep 02 2021 17:41:16

%S 0,1,0,0,0,2,8,6,0,0,0,0,0,384,2304,7416,13860,15912,10836,3564,0,0,0,

%T 0,0,0,0,40310784,322486272,1394454528,4263542784,9856161792,

%U 17805053952,25557163776,29223099648,26437927680,18541903680,9633334320,3379380192,626260608,0

%N Irregular triangle T(n,k) read by rows, where T(n,k) is the number of preference profiles in the stable marriage problem with n men and n women such that there exists a stable matching with an egalitarian cost of k.

%C The egalitarian cost of a stable matching is the sum of the mutual rankings of the people in couples.

%C 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 2n. So for k < 2n, T(n,k) = 0.

%C Sequence A344692 counts the profiles with multiplicity equal to the number of different stable matchings with an egalitarian cost of k.

%e The first row is 0, 1. The second row is 0, 0, 0, 2, 8, 6. The n-th row starts with 2n-1 zeros. The numbers of terms in rows 3 and 4 are 12 and 20 respectively.

%e If two people rank each other first, they are called soulmates. Therefore, if the egalitarian cost is 2n, then there are n pairs of soulmates. Sequence A343698(n,2n) counts the preference profiles with n men and n women that have n pairs of soulmates. 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.

%Y Cf. A185141, A343698, A344692.

%K nonn,tabf

%O 1,6

%A _Tanya Khovanova_ and MIT PRIMES STEP Senior group, Jun 22 2021

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 15 02:53 EDT 2024. Contains 373402 sequences. (Running on oeis4.)