2.4 Combinatorics

개념

경우의 수는 조건을 만족하는 서로 다른 선택이나 배치의 개수입니다. 결과가 언제 같은 경우로 취급되는지 먼저 정합니다.

합의 법칙

빵 $3$종류와 음료 $2$종류 중에서 하나만 고른다고 하겠습니다. 빵을 고르는 경우는 소보로빵·단팥빵·크림빵의 $3$가지이고, 음료를 고르는 경우는 우유·주스의 $2$가지입니다. 가능한 선택은 이 다섯 가지를 합친 $3+2=5$가지입니다.

이처럼 서로 겹치지 않는 경우 중 하나를 선택할 때는 경우의 수를 더합니다. 이를 합의 법칙이라고 하며, 두 경우의 수가 각각 $a,b$이면 전체는 $a+b$가지입니다.

여기서 서로 겹치지 않아야 한다는 조건이 중요합니다. $1$부터 $6$까지의 수 중에서 짝수이거나 $3$의 배수인 수를 고르면, 짝수는 $2,4,6$이고 $3$의 배수는 $3,6$입니다. 두 개수를 그대로 더하면 $6$을 두 번 세므로, 겹치는 한 가지를 빼서 $3+2-1=4$가지가 됩니다.

곱의 법칙

이번에는 같은 메뉴에서 빵 하나와 음료 하나를 함께 고른다고 하겠습니다. 빵을 하나 정할 때마다 음료를 고르는 방법이 $2$가지씩 있습니다.

전체 경우의 수는 $2+2+2=3\times2=6$가지입니다. 이처럼 여러 단계의 선택을 모두 수행하고, 첫 선택이 $a$가지이며 각 선택마다 다음 선택이 $b$가지이면 전체는 $ab$가지입니다. 이를 곱의 법칙이라고 합니다.

앞의 예시에서 빵과 음료 중 하나만 고르면 합의 법칙을, 빵과 음료를 하나씩 고르면 곱의 법칙을 적용합니다. 곱할 때는 첫 선택에 따른 다음 선택의 개수가 일정한지 확인합니다. 소보로빵에는 우유만 고를 수 있다면 세 행의 선택 수가 $1,2,2$가 되어 전체는 $1+2+2=5$가지입니다.

팩토리얼과 순열

서로 다른 $N$개를 모두 줄 세우는 경우는 $N!=N(N-1)\cdots1$입니다. 아무것도 고르지 않는 한 가지 경우를 반영하여 $0!=1$로 정의합니다.

서로 다른 $N$개 중 $R$개를 골라 순서 있게 배치하는 순열의 수는 $P(N,R)=N!/(N-R)!$입니다. 첫 자리는 $N$가지, 다음 자리는 $N-1$가지로 선택지가 줄어듭니다.

조합

순서를 구분하지 않고 $R$개를 고르면, 같은 선택이 순열에서 $R!$번씩 세어집니다. 따라서 조합의 수는 $C(N,R)=P(N,R)/R!$입니다. $4$개 중 $2$개를 고르면 순열은 $12$가지, 조합은 $6$가지입니다.

$A,B,C$ 중 두 개를 순서 있게 고르면 $AB,AC,BA,BC,CA,CB$의 $6$가지입니다. 순서를 구분하지 않으면 $AB$와 $BA$는 같은 선택이므로 $\{A,B\},\{A,C\},\{B,C\}$의 $3$가지입니다. 각 선택이 $2!=2$번씩 세어져 $6/2=3$이 됩니다. $R$개를 골랐을 때도 한 선택을 나열하는 순서가 $R!$가지이므로 같은 원리로 나눕니다.

공식은 선택의 개수를 계산할 때 사용합니다. 실제 선택들을 모두 출력해야 한다면 백트래킹으로 각 경우를 생성합니다.

복잡도

전체 물건 수를 $N$, 고르는 수를 $R$이라고 합니다.

예제

문제

서로 다른 물건 중 일부를 고를 때 순열의 수와 조합의 수를 구하여라.

입력

첫째 줄에 서로 다른 물건의 개수 $N$과 고를 개수 $R$이 공백을 사이에 두고 주어진다. $1\le N\le10$; $0\le R\le N$이다.

출력

순열의 수와 조합의 수를 공백으로 구분하여 출력한다.