같은 것이 있는 순열

확률과 통계 · 경우의 수 — n개를 일렬로 놓는데 그중 같은 것이 각각 p개, q개, … 있으면 서로 다른 배열은 n! / (p! q! …). 같은 것끼리 자리를 바꿔도 구별이 안 되므로 그 수(p!, q!)로 나눈다.

1. 직접 해보기

전체 개수와 같은 문자의 개수 p, q 를 조절해 서로 다른 배열의 수를 확인하자. 예: ‘BANANA’ 는 6!/(3!·2!) = 60.

–

n! 은 모두 다르다고 보고 센 값. 그런데 A끼리는 어떻게 배열해도 같은 단어이므로 p! 가지가 한 가지로 겹친다. 겹치는 만큼 나눠 실제 가짓수를 얻는다. 최단 경로 문제도 ‘→’ a개, ‘↑’ b개의 같은 것이 있는 순열이다.

핵심 같은 것이 p개, q개 섞인 n개의 일렬 배열은 n! / (p! q! …). 겹쳐 세어진 만큼 나눈다.