같은 것이 있는 순열 계산기

MATEMATIKA(체코어로 “수학”)라는 단어의 문자를 재배열하면 서로 다른 “단어”가 몇 개 생길까? 10개의 문자가 모두 다르다면 순열의 수는 10!이다. 하지만 이 단어에는 A가 3개, M이 2개, T도 2개 있다. 두 A의 자리를 서로 바꿔도 같은 단어가 되므로, 이렇게 바꾸기만 한 같은 배열을 여러 번 세면 안 된다.

계산기에는 문자(원소)의 전체 개수 n과 같은 문자가 각각 몇 개씩 있는지 입력한다. 한 번만 나오는 문자는 입력하지 않아도 된다. 1! = 1이므로 쓰지 않는 칸은 1로 두면 결과가 달라지지 않는다.

계산 방법

그래서 n!을 같은 것의 개수의 계승으로 각각 나눈다.

$$\frac{n!}{k_1!\cdot k_2!\cdot \dots }$$

MATEMATIKA는 10글자이다. A가 3개, M과 T가 2개씩, E, I, K가 1개씩이다. 문자가 모두 다르다면 늘어놓는 방법은 10! = 3,628,800가지이다. 그런데 3개의 A끼리 자리를 바꾸는 방법은 3! = 6가지이고, 어느 경우에도 같은 단어가 된다. 2개의 M끼리, 2개의 T끼리 바꾸는 방법도 각각 2가지이다. 따라서 다음과 같이 나눈다.

$$\frac{10!}{3!\cdot 2!\cdot 2!}=\frac{\mathrm{3,628,800}}{6\cdot 2\cdot 2}=\frac{\mathrm{3,628,800}}{24}=\mathrm{151,200}$$

MATEMATIKA의 문자로 만들 수 있는 서로 다른 단어는 151,200개이다. 대부분은 뜻이 없는 배열이지만, MATEMATIKA, KAMATEMATI, TIKAMATEMA도 그 안에 들어 있다.