CSP-S 提高级 · CSP 2021 提高级第一轮 第 13 题

有 $8$ 个苹果从左到右排成一排，你要从中挑选至少一个苹果，并且不能同时挑选相邻的两个苹果，一共有（ ）种方案。

这道题考的是不相邻组合计数。拿到题先想：选k个不相邻苹果，相当于把k个苹果插进剩下的空位，公式是C(9-k, k)。因为题目要求至少选一个，所以k从1到4分别算再求和，别把不选的情况加进去。

最容易踩的两个坑：一是忘记“至少一个”这个限制，把k=0（不选任何苹果）的那一种情况也算进去，结果就会多算1变成55；二是直接套用普通组合C(8,k)，完全忽略了“不能相邻”这个核心条件，那样算出来的数会大得多。另外，有些同学会死磕递推公式f(n)=f(n-1)+f(n-2)+1，但初始值设错或者忘记最后要加1（代表全选或不选的情况），也很容易算偏。

考察知识点

本题核心是排列组合基础中的不相邻组合问题，属于计数原理的典型应用，也是历年CSP提高级初赛的高频考点。

概念拆解

什么叫“不相邻组合”？简单说就是从一排元素里挑几个，挑出来的任意两个都不能挨着。解决这类问题的神器是隔板法的一个变种：把k个要选的苹果先拿出来，它们之间必须至少隔1个没选的苹果，所以相当于在剩下的位置里插空。