Occupancy Exactly k Empty Boxes

Problem

Balls are thrown independently and uniformly into boxes. Return the probability that exactly empty boxes stay empty:

P = C(boxes, empty) * Surj(balls, boxes - empty) / boxes^balls

where Surj(m) = sum over j of (-1)^j * C(m, j) * (m - j)^balls counts the surjections onto m boxes. Return 1.0 when balls = 0 and empty = boxes; return 0.0 for invalid arguments or when balls are fewer than the occupied boxes.

Hint

Choose which boxes are empty, then count surjections onto the rest.

Test cases

case 1

in: [2,2,0]

expected: 0.5

case 2

in: [2,2,1]

expected: 0.5

case 3

in: [3,3,0]

expected: 0.2222222222222222

case 4

in: [2,1,1]

expected: 1

case 5

in: [3,0,3]

expected: 1

Starter codePython

import math


def occupancy_exactly_k_empty(boxes, balls, empty):
    # Your code here
    pass

5 test cases · run your code against them in the editor