순열 & 조합 (Permutations and Combinations)

1. 경우의수

경우의 수란 '일어날 수 있는 사건의 가짓수'입니다. 예를 들어 정육면체 주사위를 던져서 나올 수 있는 경우의 수는 {1, 2, 3, 4, 5, 6}의 6가지가 있습니다. 이때 '정육면체 주사위를 던지는 사건'은 6개의 경우의 수를 가집니다. 이를 확장시켜보면, 정육면체 주사위 두 개를 던졌을 때 합이 3이 되는 경우의 수는 두 주사위의 눈이 (1, 2)거나 (2, 1)일 때의 2가지가 됩니다. 이는 ‘정육면체 주사위 두 개를 던졌을 때 합이 3이 되는 사건'은 2개의 경우의 수를 가진다는 말과 같습니다.

N개의 경우의 수를 가진 사건 A와 M개의 경우의 수를 가진 사건 B가 있을 때를 생각해봅시다. 두 개의 사건은 따로 일어나거나, 동시에 일어날 수 있습니다. 먼저 두 개의 사건이 따로 일어나는 상황에서의 총 경우의 수를 생각해봅시다. 두 사건이 따로 일어난다는 의미는 사건 A가 일어나거나, 사건 B가 일어난다는 의미입니다. 따라서 총 경우의 수는 두 사건의 경우의 수를 더한 N + M가지가 되며, 이를 합의 법칙이라고 합니다.

반면 두 사건이 동시에 일어난다는 의미는 사건 A가 일어나고 사건 B도 일어난다는 의미입니다. 이때 사건 A가 일어나는 N개 각각의 경우마다 두 번째 사건이 일어나는 경우의 수 M가 생깁니다. 사건 A가 일어나는 경우를 {A1, A2, … AN}, 사건 B가 일어나는 경우를 {B1, B2, … , BM}이라고 했을 때 두 사건이 동시에 일어나는 총 경우의 수는 {(A1, B1), (A1, B2), …, (A1, BM), (A2, B1), …, (A2, BM), …, (AN, B1), …, (AN, BM)}의 N * M가지가 되며, 이를 곱의 법칙이라고 합니다.

2. 순열

n명의 학생이 있을 때 r명을 뽑아 차례대로 줄 세우는 상황을 생각해봅시다. 맨 앞에는 n명의 학생 중 한 명이 올 수 있습니다. 그 뒤, 두 번째에는 맨 앞의 학생을 제외한 n - 1명의 학생이 올 수 있습니다. 또 그 뒤에는 앞에 세운 2명을 제외한 n - 2명의 학생 중 한 명이 올 수 있습니다. 이와 같이 줄을 세우다 보면 마지막 r번째에는 r - 1명의 학생을 제외한 n - r + 1명의 학생 중 한 명을 배치할 수 있을 것입니다. 학생들을 모두 동시에 배치하고 있으므로 이때 총 경우의 수는 곱의 법칙에 따라 n * (n - 1) * … * (n - r + 1)이 됩니다. 예를 들어, n명을 모두 줄 세우는 방법의 수는 n!가지가 됩니다.

이는 학생을 줄 세우는 문제뿐만 아니라, 서로 다른 n개의 원소에서 r개를 중복하지 않고 선택하여 순서 있게 늘어놓는 경우라면 모두 적용될 수 있습니다. 이를 순열이라고 하며, 수식으로는 다음과 같이 표현할 수 있습니다.

nPr = n * (n - 1) * … * (n - r + 1) = n! / (n - r)!

3. 조합

앞에서는 n명의 학생 중 r명을 뽑아서 나열하는 방법을 살펴보았습니다. 이번에는 순서 없이 n명의 학생 중 r명을 뽑는 경우를 생각해 봅시다. 이때의 경우의 수는 앞에서 다룬 순열을 이용하면 쉽게 구할 수 있습니다. 예를 들어 1, 2, 3번 학생을 뽑아서 나열하는 방법은 {(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)}의 6가지 경우의 수가 있습니다. 하지만 지금 구하고자 하는 것은 이들을 일렬로 세우는 것이 아니라 단순히 뽑기만 하는 것입니다. 즉, 순서가 상관없으므로 이 6가지는 모두 (1, 2, 3)번 학생을 뽑은 하나의 경우가 됩니다. 따라서 n명의 학생 중 이 학생들을 뽑는 경우의 수를 세고 싶다면 이들을 뽑아서 나열하는 경우의 수인 nP3 을 3!(6)으로 나눠줘야 합니다.

이를 일반화해보면 n명의 학생 중 r명을 뽑는 경우는 nPr을 r!로 나눈 값이 될 것입니다. 이 결과를 조합이라고 하고 수식으로는 다음과 같이 적습니다.

nCr= n × (n − 1) × ⋯ × (n −r + 1) = n!
r× (r − 1) × ⋯ × 1 r!(n −r)!

조합은 몇 가지 특이한 성질을 가지고 있습니다. 먼저 n명의 학생 중 r명을 뽑는 경우는 n명의 학생을 r명의 학생이 있는 집단과 나머지 n −r명의 학생이 있는 두 집단으로 나누는 것으로도 생각해볼 수 있습니다. 그런데 이는 n −r명의 학생을 뽑고 r명을 남기는 것과 결과적으로 같습니다. 따라서 조합에서는 다음과 같은 식이 성립합니다.

nCr=n Cn-r

두 번째 성질을 보기 전에 파스칼의 삼각형에 대해 소개하겠습니다. 파스칼의 삼각형이란 아래 그림과 같이 생긴 수의 나열이며, 인접한 두 개의 수의 합을 바로 아랫줄에 두 수의 중간에 위치합니다.

파스칼 삼각형에서 위에서부터 n칸 아래에 있고 왼쪽에서부터 r 칸 옆에 있는 숫자는 nCr이라는 것을 확인할 수 있습니다. 따라서 이 결과를 바탕으로 조합의 두 번째 성질을 추측해볼 수 있습니다.

nCr=n-1 Cr-1 +n−1 Cr (n,r> 0)

이 식이 성립하는지는 수식을 통해 증명할 수 있습니다.

조합은 그 식에서 볼 수 있듯 재귀적으로 호출하여 구할 수도 있지만, 필요한 값이 중복되거나 다양할 경우 파스칼의 삼각형을 이용하여 동적 계획법으로도 구현할 수 있습니다. 아래는 이를 구현한 코드입니다.

import java.util.*;

public class Main {
    static int comb[][] = new int[1001][1001];

    public static void calc_combination() {
        comb[0][0] = 1;
        for (int i = 1; i <= 1000; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0) {
                    comb[i][j] = 1;
                } else {
                    comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % 1000007;
                }
            }
        }
    }

    public static void main(String args[]) {
        calc_combination();

        Scanner sc = new Scanner(System.in);

        int q = sc.nextInt();
        while (q-- > 0) {
            int n = sc.nextInt();
            int r = sc.nextInt();
            System.out.println(comb[n][r]);
        }
    }
}