Concerning the maximum number of stable matchings in the stable marriage problem (Q1598825): Difference between revisions

Let us take \(n\) men and \(n\) women. Each man ranks the women in order of preference from \(1\) to \(n\). Similarly, each woman ranks the men in order of preference form \(1\) and \(n\). A matching consists of \(n\) ordered pairs \((i_r,j_r)\) where \(i_r\) is in the set of men, \(j_r\) is in the set of women. A matching is stable if it does not contain a man \(i_s\) and a woman \(j_t\) where \(i_s\) prefers \(j_t\) to \(j_s\) and \(j_t\) prefers \(i_s\) to \(i_t\). The function \(f(n)\) denotes the number of stable matchings possible in an instance of size \(n\). The author proves that \(f(n)\) is strictly increasing, and derives lower bounds for \(f(n)\).