不相鄰組合

不相鄰的組合是指從集合A={1,2,...,n}中取出r個不相鄰的數字進行組合（不可重），即不存在相鄰的兩個數j,j+1的組合。

基本介紹

• 中文名：不相鄰組合
• 外文名：non-adjacent combination

定義

不相鄰的組合是指從集合A={1,2,...,n}中取出r個不相鄰的數字進行組合（不可重），即不存在相鄰的兩個數j,j+1的組合。

例： n=6,r=3的不相鄰組合有{1 3 5}{2 4 6}{1 4 6}{1 3 6}。

性質

從A={1,2,…n}中取r個不相鄰的數進行組合，其組合數為C(n-r+1,r)。

證明：設B={b₁,b₂,…,b_r}是一組不相鄰的組合，

假定b₁<b₂,…,<b_r ,令c₁=b₁, c₂= b₂-1,…,c_r=b_r-r+1≤n-r+1,

則c₁<c₂,...,<c_r,{c₁,c₂,…,c_r}為從{1,2,…n-r+1}中取r個進行不可重組合

反之，從{1,2,…,n-r+1}中取r個進行不可重組合構成{d₁,d₂,...,d_r}，

假定d₁<d₂,...,<d_r

· c₁=d₁,c₂=d₂+1,...,c_r=d_r+r-1≤n-r+1+r-1=n

· c₁<c₂,...,<c_r，c_i+1-c_i=(d_i+1+1+i)-(d_i+i-1)=d_i+1+1-d_i+1>1,

故c_i+1和c_i不相鄰。{c₁,c₂,...,c_r}為從{1,2,…n}中取r個不相鄰的數的組合

故從A={1,2,…n}中取r個不相鄰的數進行組合與從(n-r+1)個元素中取r個的無重組合一一對應，

其組合數為C(n-r+1,r)。