순열·조합·중복순열·중복조합 차이: 두 질문으로 고르기

순열과 조합 문제는 공식을 먼저 외우면 자주 섞인다. 다음 두 질문에 답하면 대부분의 경우를 고를 수 있다.

1. 순서가 결과를 바꾸는가?
2. 한 항목을 다시 선택할 수 있는가?

순서가 중요하면 순열, 중요하지 않으면 조합이다. 같은 항목을 다시 선택할 수 있으면 “중복”이 붙는다.

네 가지 경우를 한 표로 정리하기

서로 다른 항목 n개 중 r번 선택한다고 하자.

순서	다시 선택	이름	개수
중요	불가	순열	nPr = n! / (n-r)!
무관	불가	조합	nCr = n! / (r!(n-r)!)
중요	가능	중복순열	n^r
무관	가능	중복조합	C(n+r-1, r)

일반 순열과 조합은 0 <= r <= n에서 생각한다. 중복순열은 n >= 0, r >= 0, 중복조합 공식은 보통 n >= 1, r >= 0인 항목 종류에 사용한다.

같은 예제로 네 경우 비교하기

항목이 A, B, C 세 개이고 두 번 선택한다고 하자.

순열: 순서가 중요하고 다시 뽑지 않는다

AB, AC, BA, BC, CA, CB

AB와 BA는 다른 결과다. 한 결과 안에 같은 항목은 두 번 나오지 않는다.

3P2 = 3! / 1! = 6

조합: 순서는 중요하지 않고 다시 뽑지 않는다

AB, AC, BC

AB와 BA를 같은 선택으로 센다.

3C2 = 3! / (2!1!) = 3

중복순열: 순서가 중요하고 다시 뽑을 수 있다

AA, AB, AC,
BA, BB, BC,
CA, CB, CC

첫 번째 자리 3가지, 두 번째 자리도 3가지이므로 곱의 법칙에 따라 3 * 3 = 9다.

3^2 = 9

중복조합: 순서는 무관하고 다시 뽑을 수 있다

AA, AB, AC, BB, BC, CC

중복순열의 결과에서 순서만 다른 경우를 하나로 합치면 6개다.

C(3+2-1, 2) = C(4, 2) = 6

상황을 공식으로 바꾸는 질문

순서가 중요하다는 것은 무엇인가

선택한 항목이 같아도 위치를 바꿨을 때 의미가 달라지면 순서가 중요하다.

• 금·은·동메달 수상자: A-B-C와 B-A-C는 다르다.
• password·PIN의 각 자리: 1234와 4321은 다르다.
• 발표 순서: 누가 먼저 발표하는지가 결과에 포함된다.

반면 팀 구성, 메뉴 묶음, 투표 대상 집합처럼 순서가 결과에 들어가지 않으면 조합이다.

다시 선택할 수 있다는 것은 무엇인가

한 결과 안에 같은 종류가 여러 번 등장할 수 있으면 repetition allowed다.

• 숫자 10개로 길이 4 PIN을 만들며 같은 숫자 사용 가능: 중복순열
• 맛 3종류에서 아이스크림 2 scoop를 고르며 같은 맛 가능, scoop 순서 무관: 중복조합
• 사람 한 명을 팀 자리 두 곳에 동시에 배정할 수 없음: 일반 순열 또는 조합

현실 문제에서는 재고, 역할 중복, 동일 인물 중복 허용 같은 제약을 문장에서 먼저 확인한다.

중복조합 공식은 왜 C(n+r-1, r)인가

종류 n개에서 모두 r개를 고른 결과를 종류별 개수로 적어 보자.

x1 + x2 + ... + xn = r
각 xi >= 0

별 r개와 종류를 나누는 막대 n-1개를 배열하면 각 해를 하나씩 나타낼 수 있다.

예: n=3, r=4
**|*|*  -> 첫째 2개, 둘째 1개, 셋째 1개

전체 r+n-1자리에서 별 r자리 또는 막대 n-1자리를 고르면 된다.

C(r+n-1, r) = C(r+n-1, n-1)

이 설명은 항목 종류가 구분되고, 각 종류를 몇 번이든 선택할 수 있으며, 선택 순서는 무시할 때만 적용된다. 종류별 최대 개수 제한이 있으면 inclusion-exclusion이나 dynamic programming 같은 다른 방법이 필요할 수 있다.

팩토리얼과 경계값

팩토리얼은 n부터 1까지 곱한 값이다.

n! = n * (n-1) * ... * 2 * 1
0! = 1

0! = 1로 두면 아무것도 고르지 않는 경우가 한 가지라는 경계가 자연스럽다.

nP0 = 1
nC0 = 1

중복순열에서도 길이 r=0인 빈 sequence는 한 개로 센다. 항목이 0개이고 r>0이면 만들 수 있는 sequence가 없다. 중복조합 역시 r=0이면 아무것도 고르지 않는 한 가지를 별도 경계로 처리할 수 있다.

Python에서 개수만 계산하기

Python 3.8 이상에서는 math.perm()과 math.comb()로 일반 순열·조합을 정확한 정수로 계산할 수 있다.

from math import comb, perm


def count_selection_cases(n: int, r: int) -> dict[str, int]:
    if n < 0 or r < 0:
        raise ValueError("n and r must be non-negative")

    return {
        "permutation": perm(n, r) if r <= n else 0,
        "combination": comb(n, r) if r <= n else 0,
        "permutation_with_repetition": n**r,
        "combination_with_repetition": (
            1 if r == 0 else comb(n + r - 1, r) if n > 0 else 0
        ),
    }


assert count_selection_cases(3, 2) == {
    "permutation": 6,
    "combination": 3,
    "permutation_with_repetition": 9,
    "combination_with_repetition": 6,
}

floating-point 계산 뒤 반올림하는 대신 math의 exact integer 함수를 사용한다. n과 r이 커지면 결과 자체의 자릿수가 커지므로 integer arithmetic 비용은 남는다.

Python에서 실제 결과를 열거하기

itertools에는 네 경우에 대응하는 iterator가 있다.

from itertools import (
    combinations,
    combinations_with_replacement,
    permutations,
    product,
)


items = ("A", "B", "C")
r = 2

ordinary_permutations = permutations(items, r)
ordinary_combinations = combinations(items, r)
repeated_permutations = product(items, repeat=r)
repeated_combinations = combinations_with_replacement(items, r)

이 함수들은 iterator를 반환하므로 한 항목씩 소비할 수 있다. 그렇다고 결과 수가 줄어드는 것은 아니다. 모든 결과를 list()로 만들면 순열에서는 nPr, 중복순열에서는 n^r만큼 memory와 시간이 필요하다. 개수만 필요하면 공식을 사용한다.

“같은 것이 있는 순열”은 별도 문제다

AAB처럼 입력 자체에 구별되지 않는 같은 원소가 있고, 그 원소를 모두 배열하는 문제는 중복순열 n^r이 아니다.

전체 N개, 종류별 개수 n1, n2, ..., nk

N! / (n1! * n2! * ... * nk!)

이 경우는 같은 것이 있는 순열: AAB·BANANA 공식에서 증명과 Python 계산을 따로 정리했다. 순열을 한 줄 배열이 아니라 mapping의 cycle로 해석하는 방법은 백준 10451 순열 사이클에서 볼 수 있다.

마지막 선택 기준

문제에서 다음 순서로 표시하면 공식이 덜 헷갈린다.

1. 후보 종류 수 n과 선택 횟수 r를 구분한다.
2. 위치를 바꿨을 때 같은 결과인지 확인한다.
3. 같은 항목을 다시 선택할 수 있는지 확인한다.
4. 종류별 개수 제한이나 추가 조건이 있는지 확인한다.
5. 개수만 필요한지, 실제 결과를 생성해야 하는지 확인한다.

공식 이름보다 두 축을 먼저 보면 된다. 순서가 중요하면 순열, 다시 선택할 수 있으면 중복이다.

참고 자료

• NIST DLMF: Binomial Coefficients
• NIST DLMF: The Twelvefold Way
• Python 문서: math.perm
• Python 문서: math.comb
• Python 문서: itertools