Question
Six parcels are waiting in a depot, each meant for a different destination. Someone has randomly reassigned the six destination tags, with every one-to-one assignment equally likely. A worker must restore the correct labels.
Following a chain of wrong tags eventually returns to its starting parcel: that chain is a cycle. One sorting tray, costing $12 to prepare, lets the worker correct an entire cycle of length two or more, however long it is. A parcel already carrying its correct tag is a one-parcel cycle and needs no tray. There are no other correction costs.
Before seeing the assignment, how many trays does the depot expect to need, and what is its expected setup bill? Derive the result rather than counting only the number of wrong tags.
Get hint
Hint 1
A permutation splits uniquely into disjoint cycles. Count all cycles first, then subtract the fixed points (already correct parcels).
Check your answer
Solution
Let \(C_n\) be the number of cycles, including singletons, in a uniformly random permutation of \(n\) labels. Starting from a uniform permutation on \(n-1\) labels, insert label \(n\) at one of \(n\) equally likely cycle slots. One slot forms a new one-element cycle; each of the other \(n-1\) inserts \(n\) into an existing cycle. This construction yields a uniform permutation on \(n\) labels, and therefore
\(\mathbb E[C_n]=\mathbb E[C_{n-1}]+1/n\), with \(\mathbb E[C_1]=1\).
Induction gives \(\mathbb E[C_6]=H_6=1+1/2+1/3+1/4+1/5+1/6=49/20\). But a fixed point needs no tray. For each parcel \(i\), the probability that its tag remains correct is exactly \(1/6\); summing the six indicators yields an expected one fixed point, irrespective of dependence between them. Therefore the number of trays \(T\) equals \(C_6\) minus the number of fixed points, and
\(\mathbb E[T]=49/20-1=29/20\).
Since a tray costs \(12\), the expected bill is \(12(29/20)=\boxed{\$17.40}\). For a check, the same construction for \(n=3\) gives one identity permutation with zero trays, three transpositions with one tray, and two 3-cycles with one tray. The average is \(5/6=H_3-1\), as predicted. A long cycle is still only one tray, while a fixed point costs nothing: counting misplaced parcels would charge for the wrong object.
Assumptions
Each of the \(6!\) tag permutations is equally likely.
A cycle of length at least two costs exactly one $12 tray; a fixed point incurs no setup cost.
There are no variable per-parcel costs.
Final Answer
Expected trays: \(\frac{29}{20}=1.45\); expected cost: $17.40.