Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #10 Nov 06 2022 08:35:54
%S 1,2,3,10,16,48,71,268,330,1000,1231,6472,6720,20176,25011,195472,
%T 200832,456300,637336,3419680,3506880,11221136,15481956,126112960,
%U 127885440,262860800,384418176,2000043808
%N Lower bounds for the maximum number of stable matchings in the stable marriage problem based on composing smaller instances.
%C a(n) is from Appendix C of Thurber's 2002 paper, using the maximum from each row. At the time of publication, the bounds were known to be exact up to n=4. A357269 shows that they are also exact for n=5. This sequence is not to be confused with A069156, also from Thurber's Appendix C, which uses only the first column, making for looser bounds for n > 11. a(6), a(8), a(10), a(12), and a(16) are also conjectured to be exact.
%H E. G. Thurber, <a href="https://doi.org/10.1016/S0012-365X(01)00194-7">Concerning the maximum number of stable matchings in the stable marriage problem</a>, Discrete Math., 248 (2002), 195-219.
%Y Cf. A357269, A069156.
%K nonn
%O 1,2
%A _Dan Eilers_, Sep 21 2022