원순열과 중복순열

확률과 통계 · 경우의 수 — 원탁에 사람을 앉히는 배치는 회전해서 겹치면 같은 것으로 본다. 그래서 원순열의 수는 일렬 배열 n!을 회전 가짓수 n으로 나눈 (n−1)! 이다. 뽑을 때마다 후보가 그대로인 중복순열 nʳ, 같은 것이 섞인 n!/(p!q!⋯) 도 함께 다룬다.

1. 직접 해보기

원탁의 자리 수 n 을 정하고, 다른 배치 로 서로 다른 원순열을 넘겨 보자. 회전시켜 보기 를 누르면 자리가 통째로 돌아가지만 이웃 순서는 그대로 — 즉 같은 배치다. 아래 슬라이더 r 은 중복순열 nʳ 계산에 쓰인다.

자리 수 5 (원탁 인원 n)

뽑는 횟수 3 (중복순열 지수 r)

일렬 배열 n!

–

원순열 (n−1)!

–

목걸이 (n−1)!/2

–

중복순열 nʳ

–

n 을 정하고 «다른 배치» 로 원순열을 넘겨 보세요.

현재 배치: –

2. 원순열 — 왜 (n−1)! 인가

서로 다른 n명을 일렬로 세우는 방법은 n! 이다. 그런데 원탁에서는 모두가 한 칸씩 옆으로 옮겨 앉아도 «이웃 관계»가 그대로라서 같은 배치로 센다. 한 배치를 회전시켜 얻는 것이 정확히 n가지이므로, n! 을 n 으로 나눈다.

원순열의 수 = n! / n = (n − 1)!

다르게 보면, 한 사람을 기준 자리에 고정하고 나머지 (n−1)명을 그 옆으로 일렬 배열하는 것과 같다. 그래서 (n−1)! 이 바로 나온다.

n	일렬 n!	원순열 (n−1)!	목걸이(뒤집기 허용) (n−1)!/2
3	6	2	1
4	24	6	3
5	120	24	12
6	720	120	60

목걸이(염주) 순열 — 구슬을 실에 꿰어 만든 목걸이는 뒤집으면 좌우가 바뀐 배치와도 같아진다. 그래서 반사까지 같은 것으로 보면 n ≥ 3 일 때 (n−1)! / 2 가지다.

3. 중복순열 — 뽑을 때마다 후보가 그대로

서로 다른 n개에서 중복을 허용하여 r개를 순서 있게 뽑는 경우의 수다. 한 번 뽑아도 후보가 줄지 않으므로 매번 n가지, 총

ₙΠᵣ = n · n · ⋯ · n (r번) = nʳ

예: 0~9 숫자로 만드는 네 자리 비밀번호는 10⁴ = 10000가지, A·B·O·AB형처럼 4종에서 6명의 혈액형을 정하는 방법은 4⁶ 가지. 아래는 현재 n·r 로 만든 문자열의 목록이다(일부).

–

4. 같은 것이 있는 순열

n개 중에 같은 것이 각각 p개, q개, ⋯ 있을 때, 일렬로 배열하는 방법은 n! 을 서로 구별되지 않는 것들끼리 자리를 바꾼 수로 나눈다.

n! / (p! · q! · r! · ⋯) (단, p + q + r + ⋯ = n)

예	계산	값
a, a, b (3글자)	3! / 2!	3
s, t, a, t, i, s, t, i, c, s → 'statistics'가 아니라 t·s 중복	—	—
1, 1, 2, 2, 3 (5개)	5! / (2!·2!)	30
'BANANA' (B1·A3·N2)	6! / (3!·2!)	60

최단 경로 문제와 연결된다. 가로 p칸·세로 q칸 격자에서 왼쪽 아래 → 오른쪽 위 최단 경로 수는 →를 p개, ↑를 q개 일렬 배열하는 것과 같아 (p+q)! / (p!·q!) 이다.

한 줄 요약 — 원순열은 회전이 같으니 n!/n = (n−1)!, 중복순열은 매번 n가지라 nʳ, 같은 것이 섞이면 n!/(p!q!⋯) 로 나눈다.

관련: 중복조합 (별과 막대) · 주사위 확률 · 생일 역설