This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A309933 Table read by rows: T(n,k) is the number of stable marriage instances with n men and n+1 women in which some "rejecting" woman receives exactly k proposals. 0
1, 1, 1, 48, 72, 24, 746496, 1347840, 756864, 134784 (list; table; graph; refs; listen; history; text; internal format)



The n-th row (which has n+1 items) concerns stable marriage instances with n men and n+1 women. Over all such instances in which the preference list of one woman is empty (i.e., that woman deems all the men as unacceptable matches) consider running men-proposing differed acceptance (the Gale-Shapley algorithm). The k-th item in the row (k=0,...,n) gives the number of those instances in which the rejecting woman receives exactly k proposals over the course of the algorithm.

Terms computed by brute force enumeration.

Motivation for studying this sequence comes from studying the opportunities for strategic manipulation in bipartite matching markets with more agents on one side than another.

The first element of each row is exactly a 1/(n+1) fraction of the row sum. Proof: the probability that the rejecting woman receives zero proposals is exactly the probability that this woman is unmatched when preferences are uniformly random (i.e., if that woman did not reject). But if preferences are uniform, then each woman is equally likely to be unmatched.

The distribution of each row is statistically dominated by the following type of "coupon collector" random variable: at each time step, and integer between 1 and n+1 is drawn uniformly. The process stops when each integer between 1 and n has been drawn, and the output is the number of times n+1 was drawn. (Proof sketch: the coupon collector random process exactly corresponds to man-proposing differed acceptance where men always select the next woman to propose to uniformly at random (with repetition).)

Using the coupon collector distribution, you can show that the first O(log n) terms of each row comprise at least a (1 - 1/poly(n)) fraction of the row (using a Chernoff bound).


Table of n, a(n) for n=0..9.


Sum_{k=0..n} T(n,k) = ((n+1)!*n!)^n.


The first row corresponds to n=0, where there is a unique instance with 0 men and 1 woman (and the woman gets no proposals).

The second row concerns stable marriage instances with 1 man and 2 women. There are two such instances (the man chooses either of the women as his top choice). In one of them, the rejecting woman gets a proposal (T(1,1) = 1) and in the other she does not (T(1,0) = 1).

The third row has 2 men and 3 women. The men's and the first two women's preference lists are uniform over all permutations of the other side. The final woman has no list and rejects all proposals. Thus there are 6^2*2^2 = 144 total instances. In 48 of these instances, the rejecting woman receives no proposals. In 72, she receives one, and in 24, she receives two (one from each man).

The table begins:

  n |  k = 0        1       2       3


  0 |      1;

  1 |      1,       1;

  2 |     48,      72,     24;

  3 | 746496, 1347840, 756864, 134784;



Sequence in context: A039334 A043937 A173042 * A124309 A112058 A033821

Adjacent sequences:  A309929 A309931 A309932 * A309934 A309935 A309936




Clayton Thomas, Aug 23 2019



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 18 02:02 EST 2019. Contains 329242 sequences. (Running on oeis4.)