login
A225177
Numerator of answer to sock-sorting problem with n socks.
1
1, 5, 35, 311, 3377, 43373, 643475, 10831151, 203961377, 4248732053, 97006864835, 2409006894311, 64645920431057, 1864195055263613, 57489983163699635, 1888035573701458271, 65785247971229129537, 2423878578219411790373, 94161366504933859099235, 3846438440798147117812631
OFFSET
1,2
COMMENTS
Here is the problem as presented in Technology Review.
"... Fred Tydeman owns N pairs of socks, each pair a different color, which he washes when all of them are dirty. When the washing and drying are complete, he uses the following algorithm for sorting and storing the socks. Tydeman first brings the entire basket of clean socks up to the bedroom, removes one sock, and lays it on the bed. He then removes another sock at random. If the new sock matches any on the bed (initially there is only one there), he folds the pair and places it in a drawer. If there is no match, the new sock is placed on the bed and another sock is taken from the basket, again at random. Tydeman repeats the procedure until all the socks are matched and records the maximum number of unmatched socks on the bed. He would like to know the expected value of this maximum in terms of N...."
It appears that the expectation can be written as a(n)/b(n), where b(n) = A001147(n) is the product of the first n odd numbers. (This is certainly true for n <= 10.) The sequence gives the values of a(n).
REFERENCES
Allan Gottlieb, editor, Problem M/J-2, MIT Technology Review, May-June 2013.
LINKS
Milton Eisner, Problem 216, The Two-Year College Mathematics Journal, Vol. 13, No. 3, Jun., 1982, page 206.
Wenbo V. Li, Geoffrey Pritchard, A central limit theorem for the sock-sorting problem, In "High Dimensional Probability" (Oberwolfach, 1996), 245-248, Progr. Probab., 43, Birkhäuser, Basel, 1998.
David Steinsaltz, Random time changes for sock-sorting and other stochastic process limit theorems, Electron. J. Probab. 4 (1999), no. 14, 25 pp.
EXAMPLE
The expectations in lowest terms are 1, 5/3, 7/3, 311/105, 3377/945, 3943/945, 18385/3861, 10831151/2027025, 203961377/34459425, 4248732053/654729075, ...
CROSSREFS
Cf. A001147.
Sequence in context: A109253 A052797 A371540 * A151344 A015683 A000357
KEYWORD
nonn,frac
AUTHOR
N. J. A. Sloane, May 01 2013, based on an email from Jerrold Grossman, Apr 27 2013
STATUS
approved