Classical Occupancy Problem

For positive integers and , the classical occupancy problem asks how many of distinguishable boxes are occupied after distinguishable balls are placed into the boxes, with the box choices independent and identically distributed according to the discrete uniform distribution (Feller 1968). It is the basic probabilistic case of the broader occupancy problem and one case of the twelvefold way. If is the number of occupied boxes, then

where is a Stirling number of the second kind and . The factors choose the occupied boxes, form a set partition of the balls into nonempty groups, and assign those groups to the selected boxes.

The expectation value of the number of occupied boxes is

This follows by writing as the sum of indicator functions, one for each box. The related coupon collector's problem asks how long it takes to occupy every box.