확률과 통계 경우의 수 완전 정리: 복합·배열·조합 노하우

확률과 통계 경우의 수 완전 정리: 복합·배열·조합 노하우

경우의 수는 확률·통계 학습의 첫 관문이자, 수능·경시·코딩테스트까지 관통하는 핵심 도구입니다. 그런데 **‘순열·조합 공식만 외우면 끝’**이라 생각했다가, 조건 · 중복 · 배치가 섞인 문제에서 막히는 경우가 많습니다.

이번 글에서는 복합(combination of multiple stages)·배열(arrangement)·조합(combination)의 기본 공식을 재정리하고, 실전 노하우와 실수 방지 체크리스트를 함께 소개합니다. ─ 길지만 끝까지 읽고 나면, 복잡한 경우의 수 문제도 차분히 ‘쪼개고·세고·확인하는’ 습관이 자리 잡을 것입니다.

---

1. 용어 클리어부터: 배열·조합·복합

• 배열(순열, permutation)
  순서를 고려해 n개 중 r개를 배치하는 방법 : $P(n,r)=n_r=n(n-1)\dots(n-r+1)$
• 조합(combination)
  순서를 무시해 n개 중 r개를 고르는 방법 : $C(n,r)=\binom{n}{r}=\dfrac{n!}{r!(n-r)!}$
• 복합 경우의 수
  여러 단계·조건이 결합된 상황을 단계별로 나눠 곱·합의 법칙을 적용해 계산
  • 곱의 법칙(AND) : 작업이 연속될 때 경우의 수는 곱
  • 합의 법칙(OR) : 선택지가 독립일 때 경우의 수는 합

---

2. 배열 노하우 ― 순서가 핵심인 문제

2-1. 고정·금지 자리 처리

1. 자리 고정 → 먼저 고정 후 남은 자리를 순열
2. 배치 금지 → 전체 − 금지배치 총합 + 교집합 …(포함·배제)

2-2. 같은 것이 있을 때

• 동일 문자 k개를 포함한 배열 : $\dfrac{n!}{k_1!k_2!\dots}$

2-3. 원순열·환순열

• 원순열 : $(n-1)!$
• 자리 구별 X·반시계 시계 동일 → $\dfrac{(n-1)!}{2}$

---

3. 조합 노하우 ― 순서가 필요 없는 선택

3-1. 팀·위원회 구성

• 역할 구분 없는 단순 조합 : $C(n,r)$
• 역할이 다르면 단계별 곱 (예: 회장·부회장·총무)

3-2. 중복 조합

• 동일 품목 무제한 선택 : $C(n+r-1,r)$ (별과 막대)

3-3. 파티션·분할

• 같은 집합으로 분할 : 스털링 수·벨 수
• 각각 최소 1명 조건 → 초과 인원만 자유 배치

---

4. 복합 문제 해법 ― 조건이 얽힌 경우

4-1. ‘최소 한 번’ 등장 조건

1. 전체 경우의 수 구하기
2. 등장하지 않는 경우를 빼기 (여사건)

4-2. 여러 조건이 충돌할 때

• 순서 : 어려운 조건 → 쉬운 조건 순으로 적용
• 포함·배제 : 교집합 계산이 쉬운 쪽부터

4-3. 숫자 배치·암호 문제

• 자리수 문제 → 자릿값별로 분해
• 조건식(합·차) → ‘봉우리·골짜기’, ‘미리 확보’ 기법 사용

---

5. 실전 체크리스트 5

1. 조건 파악 : 순서 유무, 중복 허용, 역할 구분
2. 단계 분리 : AND vs OR 판단 후 곱·합 적용
3. 전체·여사건 : 계산이 쉬운 쪽을 택해 빼거나 더하기
4. 중복 확인 : 같은 경우가 두 번 세어졌는지 포함·배제로 점검
5. 단위 시험 : 작은 n으로 실험해 논리 검증

---

6. 자주 틀리는 유형 Q&A

• Q. ‘적어도 하나’가 보이면?
  A. 여사건이 훨씬 쉽다. 0개 선택을 빼고 계산한다.
• Q. 색칠·좌우대칭 문제는?
  A. 대칭군(Group)만큼 나눠 준다. 원순열에서 $\div2$ 하는 원리와 같다.
• Q. 서로 다른 두 사람은 떨어져야 한다?
  A. ‘한 덩어리’로 묶어 계산한 뒤 총배열에서 제외하거나, 포함·배제를 쓴다.

---

결론

경우의 수는 ‘공식 암기 → 문제 유형별 분해 → 단계별 계산 → 포함·배제 점검’ 네 과정을 습관화하면 어떤 복합 조건도 처리 가능합니다. 특히 여사건 활용과 덩어리 묶기는 계산 난이도를 극적으로 낮춰 주니 꼭 체득해 두세요. 마지막으로, 문제를 접하면 조건을 말로 풀어 노트에 적는 연습부터 시작해 보세요. 수식보다 문장을 먼저 쓰면 실수가 줄고, 풀이 논리가 명확해집니다. 꾸준히 연습한다면 확률·통계뿐 아니라 알고리즘 설계에서도 빛을 발할 것입니다.

---