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.
0, 1, 0, 0, 0, 2, 8, 6, 0, 0, 0, 0, 0, 384, 2304, 7416, 13860, 15912, 10836, 3564, 0, 0, 0, 0, 0, 0, 0, 40310784, 322486272, 1394454528, 4263542784, 9856161792, 17805053952, 25557163776, 29223099648, 26437927680, 18541903680, 9633334320, 3379380192, 626260608, 0
Offset: 1
Examples
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. 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.
Comments