So the original problem is:
$N$ cars, each having a different speed, are going along a one-lane road, so no passing is possible. Eventually, the cars will accumulate in packets, with the "fast" cars tailgating the "slow" ones. E.g., if the initial order was $1,5,2,4,3$ ($1$ being the slowest, $5$ being the fastest), we will end up with $3$ packets: $\{1\}$, $\{5,2\}$ and $\{4,3\}$. Find the average number of packets as a function of $N$.
(see: Probability problem: cars on the road)
The answer should be the $N$-th harmonic number, but I'm not getting that when I try $N=3$. There are $6$ permutations of $(1,2,3)$:
- $(1,2,3)$, which has $3$ packets,
- $(1,3,2)$, which has $2$ packets,
- $(2,3,1)$, which has $2$ packets,
- $(2,1,3)$, which has $2$ packets,
- $(3,1,2)$, which has $2$ packets,
- $(3,2,1)$, which has $1$ packet.
So the expected value for $3$ cars would be $$\frac{3+2+2+2+2+1}{6}=\frac{12}{6}=2,$$ but the $3$rd harmonic number is $1+\frac{1}{2}+\frac{1}{3}=\frac{11}{6}$. What am I doing wrong?
(2,3,1) is only one packet because the slowest car is in front.