专题地图 › 经典的计数模型
八个位置从左至右各填黑或白,要求每个前缀中黑的数量都不少于白。不同的串有多少条?
分数写 a/b,根号写 √ 或 sqrt,π 写 pi 也可以。
按最终净高度分类,用首次负高度反射。
黑作+1,白作-1。终高为2j时,合法数为 (4−j8)−(3−j8),j=0至4,约定越界组合数为0。按首次负高度反射得到被减项。求和望远镜消去,只余 (48)=70。 所求为 70。
终点可以黑多于白,不仅计黑白各四个的卡特兰串。
核心工具:路径计数与反射原理、裂项相消
专题卡:先解每种步的次数,再排路径;越界另扣
反馈先保存在这台设备上,在「我的学习」页可以一起复制给老师。
已记下,谢谢!