A225177 Numerator of answer to sock-sorting problem with n socks.

1, 5, 35, 311, 3377, 43373, 643475, 10831151, 203961377, 4248732053, 97006864835, 2409006894311, 64645920431057, 1864195055263613, 57489983163699635, 1888035573701458271, 65785247971229129537, 2423878578219411790373, 94161366504933859099235, 3846438440798147117812631

Offset: 1

Author

N. J. A. Sloane, May 01 2013, based on an email from Jerrold Grossman, Apr 27 2013

Keywords

• nonn
• frac

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).

Examples

			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, ...
		

References

• Allan Gottlieb, editor, Problem M/J-2, MIT Technology Review, May-June 2013.

Links

• Paul Tek, Table of n, a(n) for n = 1..300
• 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.
• Paul Tek, PARI program for this sequence

Crossrefs

Cf. A001147.