The frog's single leftward hop

HardProbability Combinatorics~9m

A frog starts on lily pad $1$ of pads labelled $1$ – $8$ left to right. Each turn it hops to a pad it has not visited yet, chosen uniformly at random among the unvisited pads, until all pads are visited. What is the probability that exactly one of its hops is a leftward hop (to a lower-numbered pad)? The probability is $\tfrac1M$ for an integer $M$ ; find $M$ .

Show hints (2)+

"Uniform among unvisited" means the tour is a uniformly random permutation starting at $1$ . A leftward hop is a descent.
Count permutations of $\{1,\dots,8\}$ that start with $1$ and have exactly one descent ( $=120$ ), over $7!=5040$ .

Answer

Reveal answer →

Want the full step-by-step worked solution? It's part of Premium - along with a worked solution for every question in the bank.

Practise free Unlock solutions

Asked at: Jane Street, Citadel

The frog's single leftward hop

Answer

Related questions