不相邻的组合

组合数学 数学

概念

定义 从 $A=\{1,2,\cdots,k\}$ (简记为 $[n]$) 中取 $r$ 个不允许重复, 且不存在 $i,i+1$ 这两个相邻的数同时出现在一个组合中的组合.

定理1 从 $[n]$ 中取 $r$ 个左不相邻的组合, 其方案数为 $C(n-r+1,r)$.

证明 (拉伸压缩技巧) :
设某个不相邻的组合 $b_1,b_2,\cdots,b_r$.
因为不重复, 不相邻,
所以 $b_1<b_2<\cdots<b_k$, 且 $b_{i+1}-b_i \ge 2$,
设 $c_1=b_1,c_2=b_2-1,\cdots,c_i=b_i-i+1$, 则 $c_1<c_2<\cdots<c_r\le n-r+1$,
所以原方案数等于从 $n-r+1$ 个数中取 $r$ 个不允许重复, 允许相邻的数的组合数, 即为 $C(n-r+1,r)$.