Máy tính hoán vị lặp

Sắp xếp lại các chữ cái của từ MATEMATIKA (tiếng Séc nghĩa là “toán học”) thì được bao nhiêu “từ” khác nhau? Nếu cả 10 chữ cái đều khác nhau thì có 10! hoán vị. Nhưng chữ A xuất hiện 3 lần, M 2 lần và T cũng 2 lần. Đổi chỗ hai chữ A cho nhau thì vẫn được đúng từ cũ, và những cách sắp xếp trùng nhau như thế chỉ được đếm một lần.

Nhập vào máy tính tổng số chữ cái (phần tử) n, sau đó số lần xuất hiện của từng chữ cái. Những chữ cái chỉ xuất hiện 1 lần thì không cần nhập. Các ô không dùng hãy để giá trị 1, vì 1! = 1 nên không làm thay đổi kết quả.

Cách tính

Vì vậy, số hoán vị lặp bằng n! chia cho tích các giai thừa của số lần xuất hiện từng phần tử:

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

Từ MATEMATIKA có 10 chữ cái. Chữ A xuất hiện 3 lần, M và T mỗi chữ 2 lần, E, I và K mỗi chữ 1 lần. Nếu mọi chữ cái đều khác nhau thì có 10! = 3.628.800 cách sắp xếp. Nhưng 3 chữ A có thể đổi chỗ cho nhau theo 3! = 6 cách mà từ vẫn giữ nguyên, 2 chữ M theo 2 cách và 2 chữ T cũng theo 2 cách. Ta chia:

$$\frac{10!}{3!\cdot 2!\cdot 2!}=\frac{3.628.800}{6\cdot 2\cdot 2}=\frac{3.628.800}{24}=151.200$$

Vậy từ các chữ cái của từ MATEMATIKA lập được 151.200 từ khác nhau. Phần lớn các từ đó vô nghĩa, nhưng MATEMATIKA, KAMATEMATI và TIKAMATEMA đều có trong số đó.