Coupon Collector's Problem

The Coupon Collector's Problem is about how many draws it is expected to take in order to collect all coupons by random draw. ¹

Solution

The solution to the problem is $n * H_n$, where $n$ is the number of coupons to collect and $H_n$ is the $n$-th harmonic number: ¹

$$n * \sum_{k=1}^n \frac 1 k$$

In Haskell: ¹

expected :: Int -> Float
expected n =
  fromIntegral n * sum [ 1.0 / (fromIntegral k) | k <- [1..n] ]