[이산수학] 조합이론 - Part 2. 중복 집합에서의 순열

중복된 원소를 포함하는 집합에서는 순열을 어떻게 구할까? 

중복된 원소를 포함하는 집합에서 순열을 구하는 방법은 일반적인 순열 공식을 약간 확장하여 이해할 수 있다.
지난 글(조합 Part 1.)에서 살펴보았듯, 서로 다른 원소 n개를 모두 일렬로 배열하는 경우의 수는 n!이라는 것은 이미 알고 있다.

 

하지만 집합 안에 동일한 원소가 여러 개 존재한다면, 단순히 n!로 계산하는 것은 중복을 포함한 결과를 만들어내므로 적절하지 않다.

중복된 원소들끼리 자리를 바꿔도 전체 배열이 같기 때문이다.

예를 들어, 다음과 같은 문자 집합을 생각해 보자.

 

{A, A, B}

 

이 세 문자를 일렬로 배열하는 경우의 수를 생각하면,

겉보기에는 3개의 문자를 배열하므로 3! = 6 가지가 있을 것 같지만,

여기서 두 개의 A의 위치를 바꾸는 경우는 구분이 되지 않는다. 즉, AAB와 AAB가 구별되지 않기 때문에 중복이 생기는 것이다.

이러한 중복을 제거하기 위해, 같은 원소들끼리의 순열 수만큼을 전체 경우의 수에서 나누어 주면 된다.

 

위 예제에서는 A가 2개이므로, 그 둘을 서로 바꾸는 경우 2!만큼의 중복이 발생한다.
따라서 정확한 경우의 수는 다음과 같다.

실제로 가능한 배열은 다음 세 가지뿐이다:
AAB, ABA, BAA

 

중복 집합에서의 순열 공식

이제 일반적인 공식으로 확장해 보자.
총 원소의 개수가 n이고, 그 중 중복되는 원소가 각각 p,q,…,r개라면,
이 원소들을 일렬로 배열하는 경우의 수는 다음과 같이 계산한다.

 

이 공식은 전체 순열 수인 n!에서, 중복으로 생기는 동일한 배열의 수를 나누어 주는 원리이다.

 

조금 더 복잡한 예시로 단어 SUCCESS를 생각해 보자.
이 단어는 총 7개의 문자로 이루어져 있으며, 각각 다음과 같은 중복을 가진다:

• S: 3개
• C: 2개
• U, E: 1개

따라서 이 단어의 서로 다른 순열의 수는 다음과 같이 계산된다.

 

즉, SUCCESS라는 단어의 문자를 일렬로 배열했을 때, 서로 다른 배열의 수는 총 420가지가 된다.

결론적으로, 중복된 원소를 포함하는 집합의 순열을 구할 때는

전체 원소의 순열 수 n!에서 중복 원소들 각각의 개수만큼의 팩토리얼을 나누어 주면 된다.

이는 같은 원소들끼리 위치를 바꾸어도 실제로는 동일한 배열이 되는 것을 방지하기 위한 것이다.

 

 

❗️여기서 헷갈리지 말아야 할 것은, **중복 집합에서의 순열**과 **중복 순열**은 다른 개념이라는 것이다. 

 

➕ 중복 순열 (Permutation with Repetition)이란? 

중복 순열이란 서로 다른 원소가 주어졌을 때, 그 각 원소를 중복해서 사용할 수 있게 허용하여
정해진 자릿수만큼 배열하는 경우의 수를 구하는 것이다.
즉, 같은 원소를 여러 번 사용할 수 있는 상황을 의미하며, 공식은 다음과 같다. 

여기서

• n: 사용할 수 있는 서로 다른 원소의 수
• r: 뽑아서 배열할 자릿수

예를 들어, 숫자 0, 1, 2 중에서 3자리 숫자를 만드는 경우의 수를 생각해 보면
각 자리에 0, 1, 2 중 하나를 중복해서 사용할 수 있으므로,

 

이는 위에서 다룬 것처럼 원소가 이미 주어진 상태에서 그 전체를 한 번씩만 사용하여 배열하는 문제와는 본질적으로 다른 문제이다.