cp's OEIS Frontend

A330250 Unreduced numerator of expected rank of applicant in average rank secretary problem.

%I A330250 #40 Apr 26 2025 06:43:06
%S A330250 1,3,10,45,246,1596,11472,96768,905760,9282240,104328000,1285502400,
%T A330250 17030200320,242650598400,3685666037760,60059908823040,
%U A330250 1032474885120000,18781151090688000,360710540426880000,7302919022138880000,154603891182698496000,3423234952360194048000
%N A330250 Unreduced numerator of expected rank of applicant in average rank secretary problem.
%C A330250 a(n) is the numerator of the expected rank of applicant in the secretary problem when minimizing average rank, the denominator is n!.
%C A330250 Lim_{n -> infinity} a(n)/n! = A242672 = 3.8695...
%C A330250 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.
%D A330250 Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, Section 5.15, p. 362.
%H A330250 Y. S. Chow, S. Moriguti, H. Robbins, and S. M. Samuels, <a href="https://doi.org/10.1007/BF02759948">Optimal selection based on relative rank (the “secretary problem”)</a>, Israel J. Math. 2, 81-90 (1964).
%H A330250 Thomas S. Ferguson, <a href="https://www.math.ucla.edu/~tom/Stopping/Contents.html">Optimal Stopping and Applications</a>
%H A330250 Eric Weisstein's MathWorld, <a href="https://mathworld.wolfram.com/SultansDowryProblem.html">Sultan's Dowry Problem</a>.
%H A330250 Wikipedia, <a href="http://en.wikipedia.org/wiki/Secretary_problem">Secretary problem</a>.
%e A330250 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.
%e A330250 a(10)/10! = 3223/1260 = 2.558.
%t A330250 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 *)
%o A330250 (Python) from fractions import Fraction
%o A330250 from math import factorial
%o A330250 def a(n):
%o A330250   c_i = Fraction(n + 1, 2)
%o A330250   for i in reversed(range(1, n)):
%o A330250     ratio = Fraction(i+1, n+1)
%o A330250     s_i = int( ratio * c_i )
%o A330250     c_i = Fraction( (s_i * (s_i + 1) // 2) / ratio + (i - s_i) * c_i, i)
%o A330250   return (c_i*factorial(n)).numerator
%o A330250 for n in range(1, 20):
%o A330250     print(a(n))
%o A330250 (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!);}
%o A330250 for(n=1, 20, print1(a(n), ", ")) \\ _Michel Marcus_ and _Vaclav Kotesovec_, Jan 04 2020
%o A330250 (Julia)
%o A330250 function a(n)
%o A330250     r, c = BigInt(n), BigInt(n + 1) // 2
%o A330250     for i = n-1:-1:1
%o A330250         q = (i + 1) // (n + 1)
%o A330250         s = floor(q * c)
%o A330250         k = (i - s) * c + (s * (s + 1)) // (2 * q)
%o A330250         c = k // i
%o A330250         r *= i
%o A330250     end
%o A330250 numerator(r * c) end
%o A330250 [a(n) for n in 1:22] |> println # _Peter Luschny_, Jan 05 2020
%Y A330250 Cf. A054404, A242672.
%K A330250 nonn,frac,easy
%O A330250 1,2
%A A330250 _Seth A. Troisi_, Dec 06 2019