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

앞선 글에서는 서로 다른 것 중에서 중복 없이 뽑는 순열과 조합을 다뤘습니다. 이번에는 같은 대상을 여러 번 고를 수 있는 경우, 즉 중복순열과 중복조합을 정리하겠습니다.

중복을 허용한다는 뜻을 정확히 이해하고, 순서가 중요한지에 따라 중복순열과 중복조합을 구분하기.

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

• 중복을 허용한다는 것은 한 번 고른 대상을 다시 고를 수 있다는 뜻이다.
• 중복순열은 중복을 허용하여 순서 있게 뽑는 경우이다.
• 중복조합은 중복을 허용하여 순서 없이 뽑는 경우이다.
• 중복조합은 각 종류를 몇 개 고르는지로 바꾸어 생각할 수 있다.
• 수학적 공식과 점화식을 먼저 이해한 뒤, Python으로 실제 배열을 생성해 검산한다.

1. 중복을 허용한다는 것은 무엇일까?

중복을 허용한다는 말은 한 번 고른 대상을 다시 고를 수 있다는 뜻입니다.

예를 들어 숫자 1, 2, 3 중에서 세 자리 비밀번호를 만든다고 합시다. 중복을 허용하면

같은 배열이 가능합니다.

하지만 중복을 허용하지 않으면 $111$은 불가능합니다. 같은 숫자 1을 세 번 사용했기 때문입니다.

여기서 다시 질문해야 합니다.

순서가 중요한가?

비밀번호에서는 순서가 중요합니다. 예를 들어

입니다. 숫자의 순서가 바뀌면 다른 비밀번호가 됩니다. 이런 경우는 중복순열입니다.

반대로 아이스크림 맛을 고르는 상황에서는 순서가 중요하지 않을 수 있습니다. 예를 들어 딸기, 딸기, 초코를 고른 것과 초코, 딸기, 딸기를 고른 것은 같은 선택입니다. 이런 경우는 중복조합입니다.

2. 중복순열: 중복을 허용하여 순서 있게 뽑기

다음 문제를 봅시다.

숫자 1, 2, 3, 4 중에서 중복을 허용하여 세 자리 비밀번호를 만드는 경우의 수는?

각 자리에는 1, 2, 3, 4 중 하나가 올 수 있습니다. 그리고 중복을 허용하므로 앞에서 사용한 숫자를 다시 사용할 수 있습니다.

• 첫 번째 자리: 4가지
• 두 번째 자리: 4가지
• 세 번째 자리: 4가지

앞에서 어떤 숫자를 골랐는지와 상관없이 다음 자리에는 여전히 4가지 선택지가 있습니다. 따라서 곱의 법칙에 의해

가지입니다.

일반적으로 서로 다른 $n$개에서 중복을 허용하여 $r$개를 순서 있게 뽑는 경우의 수는

입니다.

왜냐하면 $r$개의 자리마다 각각 $n$가지 선택지가 있기 때문입니다.

중복순열에서는 한 번 고른 원소를 제거하지 않습니다. 아래 탐색기를 중복순열 모드로 두고, 같은 원소를 다시 고를 수 있는 과정을 확인해 보세요.

3. 중복순열의 점화적 해석

중복순열은 한 자리를 추가할 때마다 선택지가 다시 $n$가지입니다. 길이가 $r-1$인 배열을 이미 만들었다고 합시다. 그 뒤에 마지막 원소 하나를 붙이려면 $n$가지 중 하나를 고르면 됩니다.

교과서에서는 중복순열의 개수를 보통

로 나타냅니다. 여기서 $\Pi$는 대문자 파이입니다. 따라서

입니다.

초기 조건은

입니다. 길이가 0인 배열을 만드는 방법은 빈 배열 하나입니다.

이 점화식은 $n^r$과 같은 내용을 다른 방식으로 표현한 것입니다. 예를 들어

입니다.

아래 탐색기에서 중복순열의 점화관계가 "이전 길이의 배열에 다시 n가지 선택을 붙이는 구조"임을 확인해 보세요.

4. 중복조합: 중복을 허용하되 순서는 보지 않기

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

딸기, 초코, 바닐라 3가지 맛 아이스크림 중에서 중복을 허용하여 4개를 고르는 경우의 수는?

이 문제에서는 순서가 중요하지 않습니다.

예를 들어

와

는 같은 선택입니다. 중요한 것은 각 맛을 몇 개 골랐는지입니다.

따라서 이 문제는 다음처럼 바꿀 수 있습니다.

• 딸기를 몇 개 고르는가?
• 초코를 몇 개 고르는가?
• 바닐라를 몇 개 고르는가?

딸기, 초코, 바닐라를 각각 $x_1,x_2,x_3$개 고른다고 하면

입니다. 또한 각 개수는 0개일 수도 있으므로

입니다.

즉, 중복조합은 음이 아닌 정수해의 개수를 세는 문제로 바꿀 수 있습니다.

5. 별과 막대 방법을 천천히 보기

중복조합 공식은 처음 보면 갑자기 느껴질 수 있습니다. 그래서 별과 막대 방법을 천천히 보겠습니다.

아이스크림 4개를 별 4개로 나타냅니다.

이제 이 별들을 딸기, 초코, 바닐라 세 구역으로 나누어야 합니다. 세 구역을 만들려면 구분선, 즉 막대가 2개 필요합니다.

예를 들어

는

• 첫 번째 구역에 별 2개: 딸기 2개
• 두 번째 구역에 별 1개: 초코 1개
• 세 번째 구역에 별 1개: 바닐라 1개

를 뜻합니다.

또 다른 예로

는

• 딸기 0개
• 초코 3개
• 바닐라 1개

를 뜻합니다.

막대가 맨 앞에 오면 첫 번째 맛을 0개 고른다는 뜻입니다. 막대 두 개가 붙어 있으면 가운데 맛을 0개 고른다는 뜻입니다. 그래서 0개를 고르는 경우도 자연스럽게 포함됩니다.

아이스크림 4개와 막대 2개를 모두 합치면 총 6개의 기호가 있습니다.

이 6개의 자리 중 별이 들어갈 4자리를 고르면 전체 배치가 정해집니다. 따라서

입니다.

또는 막대가 들어갈 2자리를 고른다고 보아

로 계산해도 됩니다.

일반적으로 서로 다른 $n$종류에서 중복을 허용하여 $r$개를 순서 없이 고르는 경우에는

• 별이 $r$개
• 막대가 $n-1$개

필요합니다.

따라서 전체 기호의 수는

개이고, 그중 별 $r$개의 위치를 고르면 됩니다.

또는 막대 $n-1$개의 위치를 고르면

입니다.

두 값은 조합의 성질 때문에 같습니다.

중복조합에서는 같은 원소를 다시 고를 수 있지만, 순서만 다른 중복을 만들지 않기 위해 이전 원소로 돌아가지는 않습니다. 아래 탐색기를 중복조합 모드로 두고, [A, A], [A, B]는 만들지만 [B, A]는 만들지 않는 이유를 확인해 보세요.

6. 중복조합의 점화식

중복조합도 첫 원소를 기준으로 두 경우로 나눌 수 있습니다.

리스트의 첫 원소를 $a$라고 합시다.

1. $a$를 적어도 하나 포함하는 경우
2. $a$를 하나도 포함하지 않는 경우

$a$를 적어도 하나 포함하는 경우에는 $a$ 하나를 먼저 고릅니다. 그런데 중복을 허용하므로 나머지를 고를 때도 $a$를 다시 고를 수 있습니다.

따라서 개수로 보면

입니다.

• 첫 원소를 적어도 하나 쓰는 경우: ${}_nH_{r-1}$
• 첫 원소를 쓰지 않는 경우: ${}_{n-1}H_r$

초기 조건은

입니다. 0개를 고르는 방법은 아무것도 고르지 않는 1가지입니다.

또한 종류가 1개뿐이면 몇 개를 고르든 방법은 1가지입니다.

입니다.

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

7. 네 가지 경우 비교

앞에서 배운 순열, 조합까지 함께 놓고 보면 다음과 같습니다.

이 표에서 가장 중요한 것은 공식을 외우는 것이 아니라, 문제의 조건을 읽는 순서입니다.

1. 순서가 중요한가?
2. 중복이 허용되는가?
3. 서로 같은 것이 섞여 있는가?
4. 실제 배열을 세는가, 결과값만 세는가?

이 판단이 끝난 뒤에 공식을 선택해야 합니다.

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

이제 수학적으로 정리한 내용을 실제 배열 생성 규칙으로 옮겨 보겠습니다. 이 섹션의 코드는 경우의 수만 반환하지 않습니다. 실제로 가능한 배열 목록을 만들고, 그 길이로 앞에서 구한 값을 검산합니다.

8-1. 중복순열 배열 생성하기

중복순열은 순열과 비슷하지만 한 가지가 다릅니다. 순열에서는 한 번 고른 원소를 제거했지만, 중복순열에서는 제거하지 않습니다.

리스트 $A$에서 중복을 허용하여 $r$개를 순서 있게 뽑은 배열들의 모음을 ${}_A\Pi_r$이라고 하면

입니다.

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

    result = []

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

    return result

digits = [1, 2, 3, 4]

cases = repeated_permutations(digits, 3)

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

핵심은 재귀 호출에서 items를 그대로 넘긴다는 점입니다.

repeated_permutations(items, r - 1)

선택한 원소를 제거하지 않으므로 같은 숫자가 여러 번 나올 수 있습니다.

8-2. 중복조합 배열 생성하기

중복조합은 첫 원소를 기준으로 나눕니다.

1. 첫 원소를 적어도 하나 포함하는 경우
2. 첫 원소를 하나도 포함하지 않는 경우

배열들의 모음으로 쓰면

입니다.

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

    if not items:
        return []

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

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

    without_first = repeated_combinations(rest, r)

    return with_first + without_first

flavors = ["딸기", "초코", "바닐라"]

cases = repeated_combinations(flavors, 4)

for case in cases:
    print(case)

print(len(cases))  # 15

포함하는 경우에 rest가 아니라 items를 다시 사용해야 첫 번째 맛을 여러 번 고를 수 있습니다. 반대로 첫 번째 맛을 아예 쓰지 않는 경우는 rest로 넘어갑니다.

8-3. 네 가지 배열 생성 함수 모음

순열, 조합, 중복순열, 중복조합을 모두 배운 뒤에는 네 함수를 한 번에 모아 비교할 수 있습니다. 이 부분은 처음 개념을 배울 때보다, 마지막 정리용으로 보는 것이 좋습니다.

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


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

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

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

    return with_first + without_first


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

    result = []
    for item in items:
        for tail in repeated_permutations(items, r - 1):
            result.append([item] + tail)
    return result


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

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

    with_first = [[first] + tail for tail in repeated_combinations(items, r - 1)]
    without_first = repeated_combinations(rest, r)

    return with_first + without_first

9. 연습 문제

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

10. 핵심 정리

• 중복을 허용한다는 것은 한 번 고른 대상을 다시 고를 수 있다는 뜻이다.
• 중복순열은 중복을 허용하여 순서 있게 뽑는 경우이다.
• 중복순열의 경우의 수는 ${}_n\Pi_r=n^r$이다.
• 중복조합은 중복을 허용하여 순서 없이 뽑는 경우이다.
• 중복조합은 음이 아닌 정수해의 개수와 연결되며, ${}_nH_r={}_{n+r-1}C_r$이다.
• 배열 생성 관점에서는 중복을 허용하는 순간, 선택한 원소를 다음 단계에서도 다시 사용할 수 있어야 한다.

다음 글에서는 공통수학1의 마지막 단원인 행렬로 넘어가겠습니다.

한 줄 결론:

중복을 허용할 때도 핵심 질문은 같다. 순서를 보면 중복순열, 순서를 보지 않으면 중복조합입니다.