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

1, 3, 10, 45, 246, 1596, 11472, 96768, 905760, 9282240, 104328000, 1285502400, 17030200320, 242650598400, 3685666037760, 60059908823040, 1032474885120000, 18781151090688000, 360710540426880000, 7302919022138880000, 154603891182698496000, 3423234952360194048000

Offset: 1

Author

Seth A. Troisi, Dec 06 2019

Keywords

• nonn
• frac
• easy

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.

Examples

			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.
		

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 (the “secretary problem”), Israel J. Math. 2, 81-90 (1964).
• Thomas S. Ferguson, Optimal Stopping and Applications
• Eric Weisstein's MathWorld, Sultan's Dowry Problem.
• Wikipedia, Secretary problem.

Crossrefs

Cf. A054404, A242672.

Programs

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

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

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

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