cp's OEIS Frontend

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.

%I A344692 #47 Jan 27 2022 20:40:35
%S A344692 0,1,0,0,0,2,8,8,0,0,0,0,0,384,2304,7488,14592,18072,13104,4380,0,0,0,
%T A344692 0,0,0,0,40310784,322486272,1397440512,4299816960,10080681984,
%U A344692 18632540160,27586068480,32664453120,30544625664,21941452800,11480334336,3963617280,707788800,0
%N 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.
%C A344692 The egalitarian cost of a stable matching is the sum of the mutual rankings of the people in couples.
%C A344692 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.
%C A344692 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.
%e A344692 Triangle begins:
%e A344692   0, 1;
%e A344692   0, 0, 0, 2, 8,   8;
%e A344692   0, 0, 0, 0, 0, 384, 2304,     7488,     14592,      18072, 13104, 4380;
%e A344692   0, 0, 0, 0, 0,   0,    0, 40310784, 322486272, 1397440512, ...        ;
%e A344692   ...
%e A344692 The n-th row starts with 2*n-1 zeros.
%e A344692 The total number of terms in row 3 and 4 is 12 and 20 respectively.
%e A344692 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.
%e A344692 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).
%e A344692 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 A344692 Cf. A185141, A343698, A344691.
%K A344692 nonn,tabf
%O A344692 1,6
%A A344692 _Tanya Khovanova_ and MIT PRIMES STEP Senior group, Jun 22 2021