计票过程中从不落后的情形有多少
题面
一次选举中，候选人 A 恰好得到 票，候选人 B 恰好得到 票。选票按随机顺序一张一张地被唱出。在 种可能的开票顺序中，有多少种使得唱票过程中的**任何时刻** A 都不落后于 B？
- 「从不落后」指每唱完一张票后，A 的票数都至少等于 B 的票数。
- 不同的顺序按 A、B 标签的排列区分，而不区分具体是哪位选民投的票。
想一想
展开提示 1
把顺序编码成一条走了 步的路径：遇到 A 票向右走、遇到 B 票向上走，再找那些始终不越出对角线的路径。
展开提示 2
把「穿过对角线」的路径数出来：把首次穿越之前的那一段作镜像反射。
解答
答案 种，即卡特兰数 。
推导
-
把开票顺序编码为格点路径。
-
翻译题设条件。
-
用反射法数失败的路径。
-
数反射后的路径。
-
相减。
-
认出这是卡特兰数。