The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A330250 Unreduced numerator of expected rank of applicant in average rank secretary problem. 0
 1, 3, 10, 45, 246, 1596, 11472, 96768, 905760, 9282240, 104328000, 1285502400, 17030200320, 242650598400, 3685666037760, 60059908823040, 1032474885120000, 18781151090688000, 360710540426880000, 7302919022138880000, 154603891182698496000, 3423234952360194048000 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS a(n) is the numerator of the expected rank of applicant in the secretary problem when minimizing average rank, the denominator is n!. Lim_{n -> infinity} a(n)/n! = A242672 = 3.8695... a(n) can be calculated in linear time by recursively backtracking, the expected value of not selecting the j-th best candidate, seen so far, at step i. REFERENCES Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, Section 5.15, p. 362. LINKS Y. S. Chow, S. Moriguti, H. Robbins and S. M. Samuels, Optimal Selection Based on Relative Rank, 1964. Thomas S. Ferguson, Optimal Stopping and Applications Eric Weisstein's MathWorld, Sultan's Dowry Problem. Wikipedia, Secretary problem. EXAMPLE For a(3) = 10 the optimal strategy is to never accept the 1st applicant, accept the 2nd applicant if there are better (lower ranked) than the 1st applicant otherwise accept the 3rd applicant. This strategy selects the rank 1 applicant when the applicants are ordered 213, 231, 312 the rank 2 applicant from orderings 132, 321 and the rank 3 applicant from ordering 123. The numerator of the average rank is thus 1+1+1+2+2+3 = 10. a(10)/10! = 3223/1260 = 2.558. MATHEMATICA Table[ci = (n + 1)/2; Do[ratio = (i + 1)/(n + 1); si = Floor[ratio*ci]; ci = 1/i*(1/ratio*(si*(si + 1)/2) + (i - si)*ci); , {i, n-1, 1, -1}];  Numerator[ci*n!], {n, 1, 25}] (* Vaclav Kotesovec, Jan 04 2020 *) PROG (Python) from fractions import Fraction from math import factorial def a(n):   c_i = Fraction(n + 1, 2)   for i in reversed(range(1, n)):     ratio = Fraction(i+1, n+1)     s_i = int( ratio * c_i )     c_i = Fraction( (s_i * (s_i + 1) // 2) / ratio + (i - s_i) * c_i, i)   return (c_i*factorial(n)).numerator for n in range(1, 20):     print(a(n)) (PARI) a(n) = {my(ci = (n+1)/2, r, si); forstep(i=n-1, 1, -1, r = (i+1)/(n+1); si = floor(r*ci); ci = ((si * (si + 1)/(2*r) + (i - si) * ci )/i); ); numerator(ci*n!); } for(n=1, 20, print1(a(n), ", ")) \\ Michel Marcus and Vaclav Kotesovec, Jan 04 2020 (Julia) function a(n)     r, c = BigInt(n), BigInt(n + 1) // 2     for i = n-1:-1:1         q = (i + 1) // (n + 1)         s = floor(q * c)         k = (i - s) * c + (s * (s + 1)) // (2 * q)         c = k // i         r *= i     end numerator(r * c) end [a(n) for n in 1:22] |> println # Peter Luschny, Jan 05 2020 CROSSREFS Cf. A054404, A242672. Sequence in context: A028417 A060311 A184947 * A207652 A099237 A006220 Adjacent sequences:  A330247 A330248 A330249 * A330251 A330252 A330253 KEYWORD nonn,frac,easy AUTHOR Seth A. Troisi, Dec 06 2019 STATUS approved

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.

Last modified June 20 11:08 EDT 2021. Contains 345164 sequences. (Running on oeis4.)