At most 4.47^n stable matchings
We improve the upper bound for the maximum possible number of stable matchings among n men and n women from O(131072^n) to O(4.47^n). To establish this bound, we develop a novel formulation of a probabilistic technique that is easy to apply and may be of independent interest in counting other combinatorial objects.
READ FULL TEXT