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 →

Create a free account to see the full worked solution and track your progress.

Create a free account

Interview format: Market Maker, Hedge Fund Quant

The frog's single leftward hop

Answer

Related questions