把相邻间隔取作变量

解题套路

从 $1,2,\dots,n$ 里取 $k$ 个数，记从小到大是 $a_1<a_2<\cdots<a_k$。换一组变量：

它们全部 $\geqslant0$，而且

这是一一对应：给一组非负整数解，令 $a_1=u_0+1$、$a_{i+1}=a_i+u_i+1$ 就还原出唯一一个取法。于是

「取 $k$ 个数」的方案数 $=$ 方程 $u_0+\cdots+u_k=n-k$ 的非负整数解个数 $=C_{n}^{k}$，

隔板法算出来的正是 $C_{(n-k)+k}^{k}=C_n^k$——先用这条自洽检查确认换元没写错，再往下用。

关键在于，条件全都翻译成了对 $u_i$ 的下界：

下界一律用「预扣」消掉：要求 $u_i\geqslant1$ 就令 $u_i'=u_i-1$，右端的总量相应减 $1$，方程重新变成一个纯粹的非负整数解问题。

用起来是什么样

从 $1\sim9$ 里取 $3$ 个数（$n=9$、$k=3$），$u_0+u_1+u_2+u_3=6$：

• 两两不相邻（$u_1,u_2\geqslant1$）：预扣两个，$u_0+u_1'+u_2'+u_3=4$，解数 $C_{4+3}^{3}=C_7^3=35$。
• 三个连号（$u_1=u_2=0$）：$u_0+u_3=6$，解数 $C_{6+1}^{1}=7$。
• 恰有一处相邻（$u_1$、$u_2$ 恰有一个为 $0$）：两支对称，每支 $u_0+u'+u_3=5$，解数 $C_{5+2}^{2}=21$，共 $42$。

三堆加起来 $35+7+42=84=C_9^3$ ✓——同一个动作做三遍，而不是三种互不相干的技巧。

什么时候想到它

• 条件是相邻 / 不相邻 / 间隔至少几个这一类（它们全是对 $u_i$ 的下界）；
• 要的不是一个数，而是按「有几处相邻」分类的整张表——正面数要分好几类，换元之后是同一套动作；
• 插空法只回答「两两不相邻有几种」，这条路把「恰好有几处相邻」也一并回答了。

边界

• 只对「从一列里按大小取」有效。 取出来还要排顺序的，另乘 $A_k^k$；元素本身有区别（不是位置）的，这条换元无从谈起。
• 两端的 $u_0$、$u_k$ 与中间的 $u_i$ 意义不同：中间那些管相邻，两端那两个只管靠不靠边。别把两端也顺手加上 $\geqslant1$。
• 换元后先做一次自洽检查（无约束时解数必须等于 $C_n^k$）。这一步花不了几秒，却能挡住「右端写成 $n-k+1$」这种最常见的手滑。