|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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.
|
|
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
|
|
|
KEYWORD
|
nonn,frac
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|