여러 가지 순열과 조합

개요

공통수학1의 순열과 조합에서 우리는 “서로 다른 것을 뽑아 나열하거나 뽑기만 하는” 두 가지 셈법을 배웠다. 확률과 통계는 그 위에 조건이 붙은 경우들을 얹는다.

새로 다루는 것은 넷이다. 한 줄이 아니라 둥글게 앉히는 원순열, 같은 것을 여러 번 골라도 되는 중복순열, 구슬처럼 똑같은 것이 섞여 있는 순열, 그리고 순서 없이 중복을 허용하는 중복조합이다. 공식은 넷뿐이지만 문제에서 어느 것인지 알아보는 일이 훨씬 어렵다. 그래서 이 소단원의 진짜 목표는 공식 암기가 아니라 “무엇이 다른가”를 묻는 습관이다.

핵심 사실

• 회전해서 같아지는 배열을 하나로 보기 때문에 $n$ 으로 나눈다. $4$ 명이 원탁에 앉는 방법은 $3! = 6$ 가지다.
• 중복순열 $_n\Pi_r$: 서로 다른 $n$ 개에서 중복을 허락해 $r$ 개를 뽑아 나열한다. 매 자리마다 $n$ 가지를 고르므로

$$_n\Pi_r = n^r$$

• 예를 들어 $0$ 부터 $9$ 까지로 만드는 네 자리 비밀번호는 $10^4 = 10000$ 가지다.
• 같은 것이 있는 순열: $n$ 개 중 같은 것이 각각 $p$ 개, $q$ 개, … 있을 때, 같은 것끼리 자리를 바꾼 만큼을 나눈다.

$$\frac{n!}{p!\,q!\cdots}$$

• "$\text{MATH}$" 는 $4! = 24$ 가지지만 "$\text{LEVEL}$" 은 $\text{L}$ 두 개·$\text{E}$ 두 개가 겹쳐 $\dfrac{5!}{2!\,2!} = 30$ 가지다.
• 중복조합 $_n\mathrm{H}_r$: 서로 다른 $n$ 개에서 중복을 허락해 순서 없이 $r$ 개를 뽑는다. 칸막이를 세우는 문제로 바꾸면 조합이 된다.

$$_n\mathrm{H}_r = {}_{n+r-1}\mathrm{C}_r$$

• 세 종류의 사탕에서 다섯 개를 고르는 방법은 $_3\mathrm{H}_5 = {}_7\mathrm{C}_5 = 21$ 가지다.
• 판단의 두 물음: ① 순서를 따지는가 ② 중복을 허락하는가. 이 두 물음의 답이 정해지면 쓸 공식은 하나로 정해진다.

비교표

	순서 따짐	순서 안 따짐
중복 없음	$_n\mathrm{P}_r$	$_n\mathrm{C}_r$
중복 허용	$_n\Pi_r = n^r$	$_n\mathrm{H}_r = {}_{n+r-1}\mathrm{C}_r$

유형	식	예
원순열	$(n-1)!$	원탁에 $n$ 명 앉히기
같은 것이 있는 순열	$\dfrac{n!}{p!\,q!}$	$\text{LEVEL}$ 의 배열

시험 포인트

• 원순열은 $n!$ 이 아니라 $(n-1)!$ 이다. 회전해서 겹치는 배열을 하나로 세기 때문이다. 목걸이처럼 뒤집어도 같은 경우라면 여기서 다시 $2$ 로 나눈다.
• $_n\Pi_r$ 에서는 $r > n$ 이어도 된다. 중복을 허락하므로 뽑는 개수가 원소 수보다 많아도 문제가 없다. $_n\mathrm{P}_r$ 과 다른 점이다.
• 같은 것이 있는 순열은 반드시 나눈다. 같은 문자끼리 자리를 바꾼 것은 구분되지 않으므로 그 개수의 계승으로 나눠야 한다.
• 중복조합은 $_n\mathrm{H}_r = {}_{n+r-1}\mathrm{C}_r$ 로 바꿔 계산한다. 아래 첨자를 $n$ 과 $r$ 중 어느 쪽에 더할지 헷갈리면, 사탕 $r$ 개와 칸막이 $n-1$ 개를 한 줄로 늘어놓는 그림을 떠올린다.
• “적어도 하나씩” 같은 조건은 먼저 하나씩 나눠 준 뒤 남은 것으로 중복조합을 세면 깔끔하다.