培玉 · 一试
一试训练题
F2填空题经典的计数模型
一列8个编号位置中选3个，端点1、8不得选；不许相邻两位置同选，且任意连续4个位置至少选1个。共有多少选位集合？
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
标准答案：
解析
思路
用四段空位长度编码。
解答
令首尾空位数g0,g3及两内部空位数g1,g2。总空位5；四段都至少1，且连续4个不空要求每段至多3。四个正整数和5只有将某一段从1增到2的4种，均满足上限。故4个集合。 所求为 。
复核
这里只选位置，未给三个物品不同标签，不额外乘3!。
方法总结
用四段空位长度编码。
为什么评为 F2（会透露解法方向）
用四段空位长度编码。
已记下，谢谢！