중복순열·중복조합

핵심 정리

서로 다른 n개에서 중복을 허락하여 r개를 뽑아 일렬로 나열하는 방법을 중복순열이라 한다. 각 자리마다 n가지를 고를 수 있고 자리끼리 영향을 주지 않으므로 곱의 법칙에 따라 그 수는 n^r이다.

중복을 허락하되 순서를 세지 않고 뽑는 방법을 중복조합이라 하며, 기호는 {}_n\mathrm H_r이다. 이 값은 n+r-1개 중 r개를 고르는 수와 같아 {}_n\mathrm H_r={}_{n+r-1}\mathrm C_r이다.

방정식으로 옮기면 세기가 쉬워진다. x_1+x_2+\cdots+x_n=r의 음이 아닌 정수해의 개수는 {}_n\mathrm H_r이다. 모든 x_i\ge1인 양의 정수해의 개수는 {}_{r-1}\mathrm C_{n-1}이다.

자세히

중복순열은 자리마다 같은 n개 중에서 다시 고를 수 있다는 점에서 순열과 다르다. 순열에서는 한 번 쓴 것을 빼므로 자리가 하나씩 줄어 n(n-1)\cdots로 세지만, 중복순열에서는 매번 n이 그대로 남는다. 두 문자 a, b에서 중복을 허락하여 세 개를 골라 나열하면 aaa, aab, aba, abb, baa, bab, bba, bbb의 여덟 가지이고 이는 2^3=8과 같다. 네 문자에서 같은 방식으로 세 개를 나열하면 4^3=64가지가 되며, 기출에서도 같은 방식으로 경우의 수를 계산했다.

중복조합은 순서를 세지 않으므로 고른 결과를 개수만으로 적는다. 두 문자 a, b에서 중복을 허락하여 세 개를 고르면 aaa, aab, abb, bbb의 네 가지뿐이고, 이는 {}_2\mathrm H_3={}_4\mathrm C_3=4와 같다. 일반적으로 n개 항목에 r개를 나눠 주는 방법은 r개의 동그라미와 n-1개의 칸막이를 한 줄로 세우는 방법과 같다. 전체 n+r-1자리 가운데 동그라미 r자리를 고르면 되므로 {}_{n+r-1}\mathrm C_r이 된다.

경우의 수를 방정식의 해 개수로 바꾸었다면 각 변수의 최솟값 조건부터 확인한다. 하한이 1이면 각 변수에서 1을 먼저 빼 음이 아닌 정수 조건으로 바꾼다. c\ge d 같은 부등식이 있으면 c'=c-d로 치환해 같은 꼴을 만든 뒤 중복조합으로 센다. 이 순서가 기출 풀이에 반복해서 나온다.

순서와 중복 허용 여부에 따른 네 가지 계산법을 비교하면 다음과 같다.

순서를 세는지와 같은 것을 여러 번 허용하는지를 함께 봐야 식이 정해진다.

계산은 네 단계로 한다. 첫째, 같은 것을 여러 번 쓸 수 있는지 확인한다. 둘째, 순서를 세는지 확인한다. 셋째, 조건이 있으면 그 조건을 먼저 처리한다. 넷째, 남은 것을 n^r 또는 {}_n\mathrm H_r로 센다. 같은 것이 섞여 있는 나열은 {}_n\mathrm P_r을 쓰지 않고 같은 것의 팩토리얼로 나눈다를 적용한다.

나눠 주기 문제에서 각 사람이 한 개 이상 받아야 하면 먼저 한 개씩 나눠 준 뒤 남은 개수를 자유롭게 나눈다. 같은 초콜릿 8개를 네 명에게 한 개 이상씩 나누려면 먼저 한 개씩, 모두 4개를 나누어 준다. 남은 4개는 제한 없이 나눌 수 있으므로 {}_4\mathrm H_4={}_7\mathrm C_3=35가지로 센다. 이 값은 나눠 주기 문제의 기본 꼴이다.