不相邻的组合

所谓不相邻的组合是指从 A={1,2,3,…,n} 中选取 m 个不相邻的组合个数，即不存在两个数j和j+1的组合。例如， n=4,m=2 ，有组合 {1,3},{2,4},{1,4} 。

定理：从 A={1,2,3,…,n} 中取 m 个不相邻组合，其组合数为 Cmn−m+1 。

证明：设 B={b1,b2,…,bm} 是一组不相邻的组合，假设 b1<b2<⋯<bm ，令 c1=b1,c2=b2−1,c3=b3−2,…,cm=bm−m+1≤n−m+1 ,则 {c1,c2,…,cm} 即为从 1 到 n−m+1 中取 m 个不允许重复的组合，其中 0≤m≤n−r+1 .
反之，令 A¯={1,2,3,…,n−m+1} ，从 A¯ 中取 m 个不重复的组合 {d1,d2,…,dm} ,其中 d1<d2<⋯<dm .假定
c1=d1,c2=d2+1,…,cm=dm+m−1≤n−m+1+(m−1)=n
则 c1≤c2≤⋯≤cm ，而且
ci+1−ci=(di+1+i)−(di+i−1)=di+1−di+1>1
故 {c1,c2,…,cm} 是从 A={1,2,3…,n} 取的m个不相邻的组合。

参考文献：
组合数学（第四版） 卢开澄 卢华明 著