세기·순열·조합

수를 세기 전에 결과를 정의하기

실험에서 가능한 결과의 수는 공식보다 먼저 무엇을 같은 결과로 보는가에 따라 정해집니다. A, B, C라는 세 특성을 고르는 것과 A→B→C라는 처리 순서를 고르는 것은 다릅니다. 앞의 경우 {A,B,C}와 {C,B,A}는 같은 집합이지만 뒤의 경우에는 다른 실행입니다.

n개 구별되는 종류에서 k개를 고를 때 두 질문을 먼저 적으세요. 순서가 중요한가요? 한 종류를 여러 번 고를 수 있나요? 이 두 조건이 네 가지 모형을 만듭니다. 확률을 계산할 때는 경우의 수뿐 아니라 각 결과가 같은 확률인지도 별도로 확인해야 합니다.

곱의 법칙과 순열

5명의 후보 중 서로 다른 세 역할을 배정한다면 첫 역할에는 5명, 둘째에는 남은 4명, 셋째에는 3명이 가능합니다. 따라서 5·4·3=60입니다. 매 단계의 선택 수가 일정하게 정해지는 이 모형에서 곱의 법칙을 적용합니다.

각 자리의 선택지가 이전 선택에 따라 달라져도 개수만 동일하다면 위 곱을 쓸 수 있습니다. 반대로 금지 조합 때문에 어떤 가지는 다음 선택지가 두 개, 다른 가지는 네 개라면 하나의 단순 곱으로 처리하지 말고 경우를 나누거나 점화식을 사용하세요.

순서를 잊으면 조합

이번에는 세 역할 없이 세 명의 위원회를 고릅니다. 특정 세 명의 위원회는 3!=6개의 순열로 중복 계산되었습니다. 모든 위원회가 똑같이 여섯 번 세어졌으므로 60/6=10입니다.

이 나눗셈은 각 동치류의 크기가 같다는 사실에 근거합니다. 대칭이나 중복 원소 때문에 어떤 결과는 두 번, 다른 결과는 여섯 번 세어졌다면 같은 수로 일괄 나눌 수 없습니다. 뒤의 군 작용과 궤도 단원에서 이 문제를 다시 다룹니다.

중복을 허용하는 두 방식

순서 있는 길이 k 문자열은 각 자리에 n개 선택지가 있으므로 nᵏ개입니다. 5종 기호의 길이 3 문자열은 125개입니다. 이는 무중복 순열 60개와 다른 대상입니다.

순서를 무시하면서 반복을 허용하면 n개 종류별 개수 x₁,…,xₙ을 기록할 수 있습니다. 합이 k인 음이 아닌 정수해를 세는 문제가 됩니다. n≥1일 때 별 k개와 구분선 n−1개를 배열하는 일대일 대응으로

를 얻습니다. 예를 들어 두 종류 중 세 개를 고르면 개수 벡터 (0,3),(1,2),(2,1),(3,0)의 네 가지입니다. 종류마다 최대 개수 제한이 있으면 이 공식의 가정이 깨집니다.

경계값을 읽는 방법

아무것도 고르지 않는 결과는 빈 선택 하나입니다. 따라서 k=0인 네 모형의 값은 모두 1이며 0!=1입니다. n=0,k>0이면 선택할 종류가 없으므로 값은 0입니다. n=0,k=0도 1로 직접 정의합니다. 실습은 이 조합적 관례로 빈 문자열의 수를 처리하며, 일반 해석학의 모든 0⁰ 문제에 동일한 답을 강제하지 않습니다.

무중복 모형에서 k>n이면 경우의 수는 0입니다. 정의되지 않은 음수 계승을 억지로 계산하지 말고 대상 자체가 없음을 확인하세요.

시각화와 AI 연결

방식 0은 순열, 1은 조합, 2는 반복 문자열, 3은 중복 조합입니다. 그림은 정수 k=0,…,8에서의 실제 개수만 표시합니다. 점 사이의 연속 곡선이나 확률밀도가 아닙니다. n=5,k=3을 고정하고 방식을 바꾸면 60,10,125,35를 비교할 수 있습니다.

특성 부분집합 탐색은 조합, 토큰 시퀀스 탐색은 반복 문자열에 가깝습니다. 이론적 후보 수가 학습에 실제로 방문하는 후보 수나 실행 시간을 뜻하지는 않습니다. 제약·가지치기·동치 처리와 각 결과의 가중치가 필요합니다.

확인 문제와 답

1. 4개 중 서로 다른 2개를 순서 있게 고르면? 12개입니다.
2. 같은 선택에서 순서를 지우면? 6개입니다.
3. 두 종류 중 중복을 허용해 세 개를 무순서로 고르면? 4개입니다.
4. 5개 특성에서 모든 부분집합을 탐색하면? 각 특성의 포함 여부를 정하므로 2⁵=32개입니다.

추가 읽기: MIT Mathematics for Computer Science. 본문의 대응과 작은 정수 계산은 직접 구성한 예제입니다.