[공통수학1 시리즈 22편] 순열과 조합

앞선 글에서는 경우의 수를 세기 전에 무엇을 서로 다른 경우로 볼 것인지를 먼저 확인해야 한다고 했습니다. 이번 글에서는 그 기준 중 하나인 순서를 중심으로 순열과 조합을 배워 보겠습니다.

계승의 뜻에서 출발해 순열과 조합의 공식을 만들고, 순서가 중요한 선택과 중요하지 않은 선택을 구분하기.

먼저 오늘의 흐름을 잡고 시작하겠습니다.

• 계승 $n!$은 서로 다른 $n$개를 모두 일렬로 배열하는 경우의 수이다.
• 순열은 서로 다른 것 중에서 몇 개를 뽑아 순서 있게 배열하는 경우이다.
• 조합은 서로 다른 것 중에서 몇 개를 순서 없이 선택하는 경우이다.
• 조합 공식은 순열에서 같은 선택이 중복되어 세어진 횟수를 나누어 얻는다.
• 수학적 성질을 먼저 이해한 뒤, 그 성질을 Python 배열 생성으로 옮긴다.

1. 계승이란 무엇인가?

순열과 조합을 배우기 전에 먼저 계승을 알아야 합니다. 계승은 느낌표 기호를 써서 나타냅니다.

는 $n$부터 1까지의 자연수를 모두 곱한 값입니다.

예를 들어

입니다.

그런데 계승은 단순히 곱셈 기호를 줄여 쓴 것이 아닙니다. 경우의 수에서는 다음 의미가 중요합니다.

서로 다른 $n$개를 모두 일렬로 배열하는 경우의 수가 $n!$이다.

예를 들어 A, B, C 세 명을 일렬로 세운다고 합시다.

• 첫 번째 자리: 3명 중 1명
• 두 번째 자리: 남은 2명 중 1명
• 세 번째 자리: 남은 1명

따라서 경우의 수는

입니다.

실제로 배열해 보면

으로 6가지입니다.

1-1. 왜 $0!=1$이라고 할까?

계승을 쓰다 보면 $0!$이 나옵니다. 처음 보면 이상하지만, 경우의 수에서는

로 정합니다.

이것은 "아무것도 배열하지 않는 방법"을 1가지로 보기 때문입니다. 예를 들어 순열에서 $n$개 중 0개를 뽑는 경우는 아무것도 선택하지 않는 한 가지 경우입니다.

또한 공식에서도 자연스럽습니다.

인데, 서로 다른 5개를 모두 배열하는 경우는 $5!$이어야 합니다. 따라서 $0!=1$이어야 공식이 맞게 이어집니다.

2. 순열과 조합을 가르는 질문

순열과 조합을 구분하는 가장 중요한 질문은 이것입니다.

뽑힌 대상들의 순서를 바꾸면 다른 경우인가?

예를 들어 A, B, C 세 명 중 두 명을 뽑는다고 합시다.

회장과 부회장을 정한다면

입니다. A가 회장이고 B가 부회장인 경우와, B가 회장이고 A가 부회장인 경우는 다릅니다. 역할이 다르기 때문입니다. 이런 경우는 순열입니다.

반면 대표 두 명을 뽑는다면

입니다. 누가 먼저 쓰였는지는 중요하지 않습니다. 뽑힌 구성원이 같으면 같은 경우입니다. 이런 경우는 조합입니다.

따라서 문제를 읽을 때는 먼저 이렇게 물어야 합니다.

자리를 바꾸면 의미가 달라지는가?

의미가 달라지면 순열, 달라지지 않으면 조합입니다.

3. 순열: 일부를 뽑아 순서 있게 배열하기

다음 문제를 봅시다.

서로 다른 5명 중에서 3명을 뽑아 회장, 부회장, 총무를 정하는 경우의 수는?

회장, 부회장, 총무는 서로 다른 자리입니다. 따라서 같은 세 명을 뽑더라도 누가 어떤 역할을 맡는지에 따라 다른 경우가 됩니다.

예를 들어

는 A가 회장, B가 부회장, C가 총무인 경우입니다. 반면

는 B가 회장, A가 부회장, C가 총무인 경우입니다. 두 경우는 다릅니다.

이제 곱의 법칙으로 세어 봅시다.

• 회장을 정하는 방법: 5가지
• 부회장을 정하는 방법: 회장을 제외하고 4가지
• 총무를 정하는 방법: 앞의 두 사람을 제외하고 3가지

따라서

가지입니다.

이처럼 서로 다른 $n$개 중에서 $r$개를 뽑아 순서 있게 배열하는 경우의 수를 순열이라고 하고,

로 나타냅니다.

위 문제는

입니다.

순열에서는 실제 배열이 만들어질 때 고른 원소가 다음 단계에서 제외됩니다. 아래 탐색기를 순열 모드로 두고, 원소가 하나씩 선택되어 리스트에 붙는 과정을 확인해 보세요.

4. 순열 공식은 어떻게 만들어질까?

서로 다른 $n$개 중에서 $r$개를 뽑아 순서 있게 배열한다고 합시다.

첫 번째 자리에는 $n$개 중 하나가 올 수 있습니다. 두 번째 자리에는 이미 하나를 썼으므로 $n-1$개가 남습니다. 세 번째 자리에는 $n-2$개가 남습니다.

이 과정을 $r$번째 자리까지 이어 가면

입니다.

여기서 마지막 항이 왜 $n-r+1$인지 확인해 봅시다.

• 첫 번째 자리: $n$
• 두 번째 자리: $n-1$
• 세 번째 자리: $n-2$
• $r$번째 자리: $n-(r-1)=n-r+1$

따라서 마지막 항은 $n-r+1$입니다.

이 식은 계승으로도 나타낼 수 있습니다.

이므로 뒤쪽의

을 나누면 앞의 $r$개 곱만 남습니다.

따라서

입니다.

예를 들어

입니다.

5. 순열의 점화적 해석

순열은 한 번에 공식을 외우는 대신 다음처럼 단계적으로 볼 수 있습니다.

먼저 첫 번째 자리에 올 대상을 하나 고릅니다. 선택지는 $n$가지입니다. 그다음 남은 $n-1$개 중에서 $r-1$개를 순서 있게 배열합니다.

따라서 순열의 개수를 ${}_nP_r$이라고 하면

입니다.

초기 조건은

입니다. 아무것도 뽑지 않는 방법은 1가지로 봅니다.

또 다른 방식으로는 마지막에 한 자리를 추가한다고 볼 수도 있습니다. 길이 $r-1$짜리 순열을 만든 뒤, 아직 사용하지 않은 원소 하나를 붙이면 됩니다. 이때 붙일 수 있는 원소의 수는 $n-r+1$개입니다. 따라서

로도 볼 수 있습니다.

아래 탐색기에서 순열의 점화관계를 작은 문제로 나누어 확인해 보세요.

6. 조합: 일부를 순서 없이 선택하기

이번에는 다음 문제를 봅시다.

서로 다른 5명 중에서 대표 3명을 뽑는 경우의 수는?

이번에는 회장, 부회장, 총무처럼 역할이 나뉘어 있지 않습니다. 대표 3명만 정하면 됩니다.

따라서

와

는 같은 경우입니다. 뽑힌 사람이 같기 때문입니다.

이런 경우를 조합이라고 합니다. 서로 다른 $n$개 중에서 $r$개를 순서 없이 선택하는 경우의 수를

로 나타냅니다.

7. 조합 공식은 왜 순열을 나누어 만들까?

조합은 처음부터 직접 세기보다 순열과 비교하면 이해하기 쉽습니다.

서로 다른 5명 중 대표 3명을 뽑는다고 합시다. 먼저 순서를 고려하여 3명을 배열하면

가지입니다.

그런데 조합에서는 같은 3명이 뽑혔다면 순서는 중요하지 않습니다. 예를 들어 A, B, C 세 명이 뽑힌 경우를 순서 있게 쓰면

으로 6가지입니다. 하지만 조합에서는 이 6가지가 모두 같은 선택

입니다.

즉, 순열로 세면 하나의 조합이 $3!$번씩 반복되어 세어집니다. 따라서

입니다.

일반적으로 $r$개를 뽑은 하나의 조합은 $r!$가지 순서 배열을 가집니다. 따라서

이고, 순열 공식을 대입하면

입니다.

조합에서는 순서만 다른 같은 선택을 다시 만들지 않기 위해, 한 번 지나간 원소로 돌아가지 않습니다. 아래 탐색기를 조합 모드로 두고, 왜 [A, B]는 만들지만 [B, A]는 만들지 않는지 확인해 보세요.

8. 조합의 기본 성질

조합에는 자주 쓰이는 성질이 있습니다.

먼저

입니다.

$n$개 중에서 $r$개를 고르는 것은, 반대로 말하면 고르지 않을 $n-r$개를 정하는 것과 같습니다. 예를 들어 5명 중 대표 3명을 뽑는 것은 대표가 아닌 2명을 정하는 것과 같습니다. 따라서

입니다.

다음으로 중요한 성질은

입니다.

서로 다른 $n$개 중 특정한 하나를 기준으로 생각합니다. 그 대상을 뽑는 경우와 뽑지 않는 경우로 나눌 수 있습니다.

• 그 대상을 뽑는 경우: 나머지 $n-1$개 중에서 $r-1$개를 더 뽑는다.
• 그 대상을 뽑지 않는 경우: 나머지 $n-1$개 중에서 $r$개를 뽑는다.

두 경우는 서로 겹치지 않습니다. 따라서 합의 법칙에 의해

입니다.

초기 조건은

입니다.

아래 탐색기에서 조합의 점화관계가 "뽑는 경우"와 "뽑지 않는 경우"로 나뉘는 모습을 확인해 보세요.

9. 순열과 조합 비교

여기까지가 수학적 이해입니다. 이제 다음 섹션에서 이 성질을 실제 배열 생성으로 옮겨 보겠습니다.

10. 코드로 배열을 만들어 검산하기

이 섹션의 목표는 Python으로 문제를 대신 푸는 것이 아닙니다. 앞에서 얻은 수학적 성질이 실제 가능한 배열 목록을 만드는 규칙으로도 작동하는지 확인하는 것입니다.

10-1. 순열 배열 생성하기

순열 배열은 다음 규칙으로 만듭니다.

1. 첫 번째 자리에 올 원소를 하나 고른다.
2. 그 원소를 제외한 나머지 원소들로 길이 $r-1$짜리 순열을 만든다.
3. 고른 원소를 앞에 붙인다.

리스트 $A$에서 $r$개를 순서 있게 뽑은 배열들의 모음을 $P(A,r)$이라고 하면

입니다.

def permutations(items, r):
    if r == 0:
        return [[]]

    if r > len(items):
        return []

    result = []

    for i, item in enumerate(items):
        remaining = items[:i] + items[i + 1:]

        for tail in permutations(remaining, r - 1):
            result.append([item] + tail)

    return result

people = ["A", "B", "C", "D", "E"]

cases = permutations(people, 3)

print(cases[:10])
print(len(cases))  # 60

코드에서 선택한 원소를 제거하는 부분은 순열의 핵심과 연결됩니다.

remaining = items[:i] + items[i + 1:]

한 사람이 두 역할을 동시에 맡을 수 없으므로, 한 번 고른 원소는 다음 단계에서 제외합니다.

10-2. 조합 배열 생성하기

조합 배열은 첫 원소를 기준으로 두 경우로 나누어 만듭니다.

1. 첫 원소를 포함하는 조합
2. 첫 원소를 포함하지 않는 조합

리스트 $A$의 첫 원소를 $a$라고 하면

입니다.

def combinations(items, r):
    if r == 0:
        return [[]]

    if len(items) < r:
        return []

    first = items[0]
    rest = items[1:]

    with_first = []
    for tail in combinations(rest, r - 1):
        with_first.append([first] + tail)

    without_first = combinations(rest, r)

    return with_first + without_first

people = ["A", "B", "C", "D", "E"]

cases = combinations(people, 3)

print(cases)
print(len(cases))  # 10

이 구현은 조합의 점화식

을 그대로 배열 생성으로 옮긴 것입니다.

순열과 조합을 각각 살펴본 뒤에는 두 모드를 바꾸어 보며 비교해도 좋습니다. 특히 순열에서는 선택한 원소를 제거하고, 조합에서는 오른쪽으로만 진행한다는 차이에 주목하세요.

11. 연습 문제

아래 점검 퀴즈에서 순열과 조합을 구분하고, 공식과 성질을 확인해 보세요.

12. 핵심 정리

• $n!$은 서로 다른 $n$개를 모두 일렬로 배열하는 경우의 수이다.
• 순서를 바꾸면 다른 경우가 되는 선택은 순열이다.
• 순서를 바꾸어도 같은 경우로 보는 선택은 조합이다.
• 순열 공식은 곱의 법칙에서 나온다.
• 조합 공식은 순열에서 같은 선택의 배열 수 $r!$을 나누어 얻는다.
• 조합의 성질 ${}_nC_r={}_{n-1}C_{r-1}+{}_{n-1}C_r$은 배열 생성 알고리즘으로도 구현된다.

다음 글에서는 중복을 허용하는 경우, 즉 중복순열과 중복조합을 다루겠습니다.

한 줄 결론:

순열과 조합은 공식 암기가 아니라, 순서를 서로 다른 경우로 볼 것인지 판단하는 데서 시작합니다.