You roll a fair n-sided die over and over. Write coupon_collector(n: int) -> Fraction that returns the expected number of rolls until every one of the n faces has appeared at least once, as an exact fractions.Fraction.
coupon_collector(1) # Fraction(1, 1)
coupon_collector(2) # Fraction(3, 1) 1 roll, then a wait of 2 for the other face
coupon_collector(3) # Fraction(11, 2)
Constraints: 1 <= n <= 2000. Return a Fraction (an int result also has to compare equal, but floats are not exact enough).
Simulating is not exact, and tracking which subset of faces has been seen is exponential.
Show hint
Split the process into phases by how many distinct faces you have seen so far. How long, on average, do you wait in each phase, and how do the phases combine?