조건을 만족하는 순열

원문 보기: https://dawoum.duckdns.org/wiki/조건을_만족하는_순열

순열은 서로 다른 \(n\)개 중에 \(k\)개를 선택해서 정렬하는 경우의 수입니다. 만약, 서로 다른 \(n\)개에 대해 일부 조건이 주어진 경우에는 일반적인 순열을 그대로 적용할 수 없습니다.

이웃하는 조건의 순열

서로 다른 책 4권과 서로 다른 공책 2권을 일렬로 세울 때, 공책끼리 이웃하게 세우는 경우의 수는 어떻게 구할까요?

이웃한다는 의미는 옆에 있다는 의미입니다. 그러므로, 이웃하는 것을 우선 한 덩어리로 생각할 수 있습니다. 즉, 서로 다른 책 4권과 공책 덩어리 1개를 일렬로 세운다고 볼 수 있습니다. 그리고, 공책이 서로 다르기 때문에, 덩어리 내부에서 위치를 바꿀 수 있습니다. 다음과 같이 식을 세울 수 있습니다.

\(\quad\)\((4+1)! \times 2!\)

앞의 1은 공책을 하나의 덩어리로 판정하는 것이고, 뒤의 \(2!\)은 공책 덩어리 내부에서 순열을 적용한 것입니다.

이런 상황을 공식으로 만들어 외울 이유는 없지만, 굳이 만들어보자면, 다음과 같습니다.

서로 다른 \(n\)개를 일렬로 세울 때, \(r\; (1\le r \le n)\)개가 이웃하도록 하는 경우의 수

\(\quad\)\((n-r+1)! \times r!\)

이웃하지 않는 조건의 순열

서로 다른 책 4권과 서로 다른 공책 2권을 일렬로 세울 때, 공책끼리 이웃하지 않게 세우는 경우의 수는 어떻게 구할까요?

이때에는 먼저 조건이 없는 것을 책을 먼저 세웁니다. 그리고, 공책은 책들 사이에 끼워 넣어서 세우면 쉽게 해결이 됩니다. 이때, 공책은 맨 앞이나 맨 뒤에도 올 수 있기 때문에, 놓일 수 있는 위치는 책 권수보다 1개 더 많습니다.

\(\quad\)\(4! \times P(5,2)\)

서로 다른 \(n\)개를 일렬로 세울 때, \(r\; (1\le r \le n-r+1)\)개가 이웃하지 않도록 하는 경우의 수

\(\quad\)\(( n - r ) ! \times P ( n - r + 1 , r )\)

한편, 서로 다른 책 4권과 서로 다른 공책 2권을 일렬로 세울 때, 공책끼리 이웃하지 않게 세우는 경우의 수를 다른 방법으로 구할 수도 있습니다. 먼저 이웃하지 않을 공책의 위치를 정합니다. 즉,

\(\quad\)\(1, 2, 3, 4, 5, 6\)

의 위치에 책과 공책을 세울 때, 공책이 이웃하지 않으려면, (1,3), (1,4), (1,5), (1,6), (2,4), (2,5), (2,6), (3,5), (3,6), (4,6)의 위치에 세워야 합니다. 물론 순서가 달라질 수 있습니다. 그리고 나머지 위치에 책을 세웁니다.

\(\quad\)\(10 \times 2! \times 4!\)

이런 방법이 있긴 하지만, 위의 방법보다 조금 더 어렵게 느껴질 수도 있겠습니다. 어쨌든, 수형도를 생각한다면, 이런 방법, 저런 방법으로도 같은 결과가 나오는지 확인해 둘 필요는 있습니다.

간혹 말도 안 되게 서로 다른 4권의 책에 서로 다른 6권의 책을 이웃하게 않게 세우는 경우의 수와 같은 문제를 만나게 됩니다. 물론 정답은 불가능이기 때문에, 0개라고 답해야 합니다.

교란

다른 용어로 완전 순열(complete permutation)을 사용하는 경우도 있지만, 대체적으로 바른 의미의 용어로 보기 힘든지 영문 위키피디아에서는 아에 키워드가 존재하지 않고, 몇 개의 수학 사이트에서는 교란으로 바로 연결됩니다. 용어에서 완전이 완전히 다른을 의미하는 걸까요? 알려주세요!!

교란은 자기 위치에 자기 것이 오지 않는 순열을 의미합니다. 즉, n 명에게 n 개의 자기 물건이 있을 것입니다. 이 n개를 나누어줄 때, n 명 중에 자기 것을 가지는 사람이 없어야 합니다. 당연하게도 n 개의 물건은 서로 구별이 되어야 합니다.

예를 들어, 4명의 학생이 비가 와서 우산을 가지고 학교에 왔다가, 수업이 끝나고 집에 갈 때, 모두 자기 것이 아닌 우산을 가져가는 순열입니다.

고등학교 교과 과정에는 없지만, 꽤 자주 시험에 출제가 되는데, 이를 응용한 문제를 내는 것은 바람직해 보이지는 않습니다.

응용예제

응용예제1

6개의 의자가 일렬로 놓여 있다. 남학생 2명과 여학생 3명이 모두 의자에 앉을 때, 남학생이 이웃하지 않게 앉는 경우의 수는? (단, 두 학생 사이에 빈 의자가 있는 경우는 이웃하지 않는 것으로 한다.)

응용예제2

서로 다른 네 가지 색깔의 구슬이 각각 3개씩 모두 12개 있다. 12개의 구슬을 4×3 모양의 상자에 각각 1개씩 넣으려고 한다. 이때, 모든 가로 방향과 모든 세로 방향에 서로 다른 색깔의 구슬을 배열하는 방법의 수는?

응용예제3

A,B,C,D,E,F,G의 7명을 일렬로 세울 때, A,B,C 세 사람 중 두 사람 또는 세 사람이 서로 이웃하도록 세우는 경우의 수를 \(x\), A와 B는 서로 이웃하고, C와 D는 서로 이웃하고, B와 C는 서로 이웃하지 않을 경우의 수를 \(y\)라 할 때, \(x,y\)의 값을 구하시오.