排队买票找零

把带 5 元的人记为 $+1$（零钱 +1），带 10 元的人记为 $-1$（零钱 -1）。我们要求长度为 $2n$、包含 $n$ 个 $+1$ 与 $n$ 个 $-1$ 的序列，其部分和永不为负。

总序列数为 $\binom{2n}{n}$。

满足“部分和非负”的序列数是 Catalan 型计数：

$$\frac{1}{n+1}\binom{2n}{n}.$$

因此所求概率为

$$\frac{\frac{1}{n+1}\binom{2n}{n}}{\binom{2n}{n}}=\frac{1}{n+1}.$$

---

Original Explanation

Model each $5 payer as $+1$ and each $10 payer as $-1$. We need the partial sums of the sequence of $2n$ steps (with $n$ steps of $+1$ and $n$ steps of $-1$) never to go negative. The total number of such sequences is $$\binom{2n}{n},$$ and the number of “nonnegative partial sum” sequences is the Catalan-type count $$\frac{1}{n+1}\,\binom{2n}{n}.$$ Hence the probability is $$\frac{\frac{1}{n+1}\binom{2n}{n}}{\binom{2n}{n}} = \frac{1}{n+1}.$$