A344690
a(n) is the number of multisets of size n consisting of permutations of n elements.
Original entry on oeis.org
1, 3, 56, 17550, 225150024, 197554684517400, 16458566311785642529680, 173358539198065045263504881415600, 300709637734376436340098187751948137677075840, 109112041481912234203213339867180762753584908387010487351680
Offset: 1
Consider n = 3. If all three permutations are the same then there are 6 possibilities from which permutation to choose. If two permutations are the same (6 possibilities for each) and the third permutation is different (5 permutations left), then the number of possibilities is 30. If all three permutations are different, then the number of ways to choose them is 6 * 5 * 4/6 = 20. Thus, a(3) = 20 + 30 + 6 = 56.
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.
Original entry on oeis.org
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
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.
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.
Original entry on oeis.org
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
Offset: 1
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.
A344693
a(n) is the number of joint preference profiles in a stable marriage problem with n men and n women.
Original entry on oeis.org
1, 4, 72, 13824, 19353600, 585252864000, 309856276316160000, 4385849628750224818176000, 2004821822925413274697731145728000, 36224269774123479086515914989912457216000000, 31014029806101314488308034499720939299674343342080000000
Offset: 1
For n=2, there are two types of joint profiles. In the first type, the mutual rankings are (1,1) and (2,2). In the second type, the mutual rankings are (1,2) and (2,1). For each type, the profile is uniquely defined after choosing the woman to be the first choice for the first man (there are two ways to do it). Therefore, a(2) = 4.
A351580
a(n) is the number of multisets of size n-1 consisting of permutations of n elements.
Original entry on oeis.org
1, 2, 21, 2600, 9078630, 1634935320144, 22831938997720867560, 34390564970975286088924022400, 7457911916650283082000186530740981347120, 300682790088737748950725540713718365319268411170195200, 2830053444386286847574443631356044745870287426798365860653876609636480
Offset: 1
Starting with the following men's ranking table of order 3, where row k represents man k's rankings, the 1 in the 2nd position of row 3 means that man #3 ranks woman #2 as his 1st choice.
213
321
213
Step 1: reorder columns so row 1 is in natural order:
123
231
123
Step 2: reorder rows 2 to n so rows are in lexical order:
123
123
231
a(3)=21 because there are 1+2+3+4+5+6 = 21 possibilities for the last two rows in lexical order, with 3!=6 possible permutations for each row.
The 21 tables for a(3) are the following:
123 123 123 123 123 123 123
123 123 123 123 123 123 132
123 132 213 231 312 321 132
.
123 123 123 123 123 123 123
132 132 132 132 213 213 213
213 231 312 321 213 231 312
.
123 123 123 123 123 123 123
213 231 231 231 312 312 321
321 231 312 321 312 321 321
A345679
a(n) is the number of disjoint preference profiles in the stable marriage problem with n men and n women.
Original entry on oeis.org
1, 12, 8784, 1031049216
Offset: 1
For n=2, there are 16 preference profiles. Each profile is either a disjoint profile or a joint profile. The number of joint profiles is A344693(2) = 4. Thus, the number of disjoint profiles is 12.
- Matvey Borodin, Eric Chen, Aidan Duncan, Tanya Khovanova, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, and Michael Voigt, The Stable Matching Problem and Sudoku, arXiv:2108.02654 [math.HO], 2021.
A358648
Number of preference profiles of the stable roommates problem with 2n participants.
Original entry on oeis.org
1, 1296, 2985984000000, 416336312719673760153600000000, 39594086612242519324387557078266845776303882240000000000, 16363214235219603423192858350259453436046713251360764276842772299776000000000000000000000000
Offset: 1
Cf.
A356584 (up to isomorphism),
A185141 (Stable Marriage profiles),
A001147 (possible roommate pairings).
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
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.
Comments