심화 연속하지 않게 나열하는 경우의 수

＊조합으로 풀기

일렬로 놓인 $\displaystyle n$개의 자리 중 $\displaystyle r$개를 골라 표시하되, 표시한 두 자리가 서로 이웃하지 않게 하자.같은 종류의 물건은 서로 구별하지 않는다. 여기서는 $\displaystyle r\ge1$, $\displaystyle n\ge2r-1$이라 한다.$\displaystyle r=0$이면 아무것도 표시하지 않는 한 가지이고, $\displaystyle n<2r-1$이면 불가능하다.

＊빈틈에 넣기

표시하지 않을 자리 $\displaystyle n-r$개를 먼저 나열한다.양 끝을 포함한 빈틈은 $\displaystyle n-r+1$개이다.표시할 자리끼리 이웃하지 않으려면 빈틈 하나에 하나씩만 넣어야 하므로,이 빈틈 중 $\displaystyle r$개를 고르면 된다.$\displaystyle {}_{n-r+1}\mathrm{C}_r$

＊자리 번호를 줄이기

고른 자리의 번호를 $\displaystyle a_1<a_2<\cdots<a_r$라 하면,이웃하지 않는 조건은 $\displaystyle a_{i+1}\ge a_i+2$이다.$\displaystyle b_i=a_i-(i-1)$로 놓으면$\displaystyle 1\le b_1<b_2<\cdots<b_r\le n-r+1$이다. 역으로 $\displaystyle a_i=b_i+(i-1)$로 복원되므로,$\displaystyle n-r+1$개 중 $\displaystyle r$개를 고르는 보통 조합과 일대일로 대응한다.

＊서로 다른 물건을 나열할 때

자리만 고르는 것과 물건의 순서를 정하는 것은 구분한다.표시할 물건 $\displaystyle r$개가 서로 다르면 고른 자리에 놓는 방법 $\displaystyle r!$을 곱한다.나머지 물건 $\displaystyle n-r$개도 서로 다르면 그 순서까지 정해야 하므로$\displaystyle {}_{n-r+1}\mathrm{C}_r\,r!\,(n-r)!$이다. 일렬로 나열하는 경우이며, 원형으로 나열할 때에는 양 끝의 이웃 관계를 따로 확인한다.

＊중복조합으로 풀기

표시한 자리의 앞뒤와 사이에 있는 빈자리 수를 차례로 $\displaystyle x_0,x_1,\ldots,x_r$라 하면$\displaystyle x_0+x_1+\cdots+x_r=n-r$이다. 양 끝은 비어 있어도 되지만, 표시한 자리 사이에는 적어도 한 칸이 필요하므로$\displaystyle x_0,x_r\ge0,\qquad x_1,\ldots,x_{r-1}\ge1$이다.

＊필수 빈자리를 먼저 빼기

사이의 $\displaystyle r-1$곳에서 한 칸씩 미리 빼고,$\displaystyle y_0=x_0$, $\displaystyle y_r=x_r$, $\displaystyle y_i=x_i-1\ (1\le i\le r-1)$로 놓으면$\displaystyle y_0+y_1+\cdots+y_r=n-2r+1,\qquad y_i\ge0$이다. 남은 빈자리 $\displaystyle n-2r+1$개를 $\displaystyle r+1$곳에 중복을 허용하여 분배하므로$\displaystyle {}_{r+1}\mathrm{H}_{n-2r+1}={}_{n-r+1}\mathrm{C}_r$이다. 빈틈에 표시할 자리를 고르는 조합 풀이와 같은 결과를 얻는다.

＊사이에 여러 칸이 필요할 때

표시한 두 자리 사이에 적어도 $\displaystyle k$개의 빈자리가 필요하면,사이의 $\displaystyle r-1$곳에 $\displaystyle k$개씩 먼저 둔다.남은 빈자리는 $\displaystyle n-r-k(r-1)$개이므로$\displaystyle {}_{r+1}\mathrm{H}_{n-r-k(r-1)}={}_{n-k(r-1)}\mathrm{C}_r$이다. 단, $\displaystyle n-r\ge k(r-1)$이어야 한다.양 끝이나 사이에 필요한 최소 칸 수가 다를 때에도, 각 곳의 필수 칸 수를 먼저 빼면 된다.

＊점화식으로 풀기

＊표시할 개수가 정해진 경우

일렬로 놓인 $\displaystyle n$개의 자리 중 서로 이웃하지 않는 $\displaystyle r$개를 고르는 경우의 수를 $\displaystyle A_{n,r}$라 하자.마지막 자리를 고르는지에 따라 나누면,고르지 않을 때에는 앞의 $\displaystyle n-1$자리에서 $\displaystyle r$개를 고르므로 $\displaystyle A_{n-1,r}$가지이다.고를 때에는 바로 앞자리를 고를 수 없으므로 $\displaystyle n-2$자리에서 $\displaystyle r-1$개를 고르는 $\displaystyle A_{n-2,r-1}$가지이다.따라서$\displaystyle A_{n,r}=A_{n-1,r}+A_{n-2,r-1}\qquad(n\ge2,\ r\ge1)$

초깃값은 $\displaystyle A_{0,0}=1$, $\displaystyle A_{1,0}=A_{1,1}=1$이다.또한 $\displaystyle A_{n,0}=1$이고, $\displaystyle r<0$이거나 $\displaystyle r>\lceil n/2\rceil$이면 $\displaystyle A_{n,r}=0$으로 둔다.조합으로 얻은 $\displaystyle A_{n,r}={}_{n-r+1}\mathrm{C}_r$를 대입하면 이 점화식은 파스칼의 항등식과 연결된다.

＊표시할 개수도 자유로운 경우

표시할 개수의 제한 없이, 이웃한 두 자리가 모두 표시되지 않는 배열의 수를 $\displaystyle B_n$이라 하자.아무 자리도 표시하지 않는 경우도 포함한다.마지막 자리를 표시하지 않으면 $\displaystyle B_{n-1}$가지,표시하면 바로 앞자리는 비워야 하므로 $\displaystyle B_{n-2}$가지이다.따라서$\displaystyle B_n=B_{n-1}+B_{n-2}\qquad(n\ge2)$이고, $\displaystyle B_0=1$, $\displaystyle B_1=2$이다. 피보나치 수열과 같은 점화식을 갖는다.