培玉 · 一试
2015 年河北预赛 · 第 8 题
F3填空题概率
将 10 个小球（5 个黑球和 5 个白球）排成一行，从左边第一个小球开始向右数小球。无论数几个小球，黑球的个数总不少于白球个数的概率为。
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
标准答案：
解析
提示
把黑球记为上升一步、白球记为下降一步，要求所有前缀高度非负。
思路
对第一次跌到负一的坏序列作前缀反射，建立简单的计数双射。
解答
每个含五黑五白的颜色序列等可能，共 个。称某个前缀白球多于黑球的序列为坏序列。
对坏序列，找到第一个白球数比黑球数多一的前缀，并将该前缀中的黑白互换。互换后全序列共有六黑四白。反过来，任一六黑四白序列终点黑球多二，必有第一个黑球比白球多一的前缀；互换该前缀，就唯一恢复一个五黑五白的坏序列。因此坏序列数为 。
合格数为 ，概率为
复核
反射必须截在首次差一的前缀，才能保证正反操作互逆；随意反射一个坏前缀会破坏双射。直接枚举全部 个五黑五白序列，逐前缀检查，也得到 个合格序列。
方法总结
平衡的二元序列附带非负前缀约束时，可用首次越界前缀反射计数坏序列；双射的逆过程是证明计数正确的关键。
为什么评为 F3（会透露解法方向）
把前缀黑球不少于白球写成步型非负限制，对首次越界前缀反射计坏序列；反射的逆过程是计数可靠的关键。
已记下，谢谢！