How many bumps?
In lecture 10 of Professor Blitzstein’s STAT110 course he refers to a Putnam combinatorial problem.
The following extract is this problem:
Professor Blitzstein uses indicator variables to solve this. I found it instructive to think through his exposition and present it here:
To provide illustration I created both a CDF and the quicktime movie below. The number is not application of the formula but brute force counting of the maxima per permutation and then averaging. The inefficiency of this rises dramatically (as expected considering the number of comparisons per permutation). I left it at 6 for both computational convenience as well as ease of display.