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

 

Logo


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

Table of n, a(n) for n=1..22.

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.

License Agreements, Terms of Use, Privacy Policy. .

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