Permutations

Cho là một số nguyên dương, là một số nguyên thoả mãn và là một tập hợp có phần tử. Một hoán vị của (hay một chỉnh hợp chập của ) là một cách xếp phần tử nào đó của thành một hàng. Một hoán vị của sẽ được gọi là một hoán vị của

Ví dụ 1. Cho tập . Khi đó các hoán vị của là (có tất cả ):

Định lí 1. Cho là một số nguyên dương, là một số nguyên thoả mãn và là một tập hợp có phần tử. Khi đó số hoán vị của bằng . Nói riêng, số hoán vị của bằng .

Chứng minh. Một hoán vị của sẽ được hình thành sau bước: Đầu tiên, chọn một phần tử từ và đặt nó vào vị trí thứ nhất; sau đó ta chọn trong các phần tử còn lại của một phần và đặt nó vào vị trí thứ hai;…; và cuối cùng ta chọn một phần tử từ phần tử còn lại của và đặt nó vào vị trí thứ . Vì có cách làm bước thứ nhất, cách làm bước thứ hai;…; và cách làm bước thứ nên theo quy tắc nhân, ta có

Ví dụ 2. Gọi là tập tất cả chữ cái tiếng Anh. Tìm số các từ gồm chữ trong sao cho chữ đầu tiên, chữ cuối cùng là các nguyên âm phân biệt và ba chữ còn lại là các phụ âm phân biệt.

Lời giải. Có nguyên âm trong đó là và chữ cái còn lại là các phụ âm. Một từ thỏa mãn yêu cầu của đầu bài sẽ được hình thành sau hai bước: Đầu tiên, chọn một hoán vị của và đặt nguyên âm thứ nhất vào vị trí , nguyên âm thứ hai vào vị trí , sau đó chọn một hoán vị của và đặt phụ âm thứ nhất, hai, ba của hoán vị vào vị trí tương ứng.

Bởi vì có cách để làm bước thứ nhất và cách để làm bước thứ hai nên theo quy tắc nhân ta có số các từ thoả mãn là

Ví dụ 3. Có bé trai và bé gái trong một buổi liên hoan. Có bao nhiêu cách có thể xếp họ thành một hàng sao cho

(a) bé gái đứng cạnh nhau?

(b) Hai vị trí đầu và cuối hàng bị chiếm bởi các bé trai và không có hai bé gái nào đứng cạnh nhau?

Lời giải.

(a) Vì bé gái đứng cạnh nhau nên ta có thể xem họ là một “bé gái”. Một cách xếp thoả mãn yêu cầu của bài toán sẽ được hình thành sau hai bước: Đầu tiên, xếp người này thành một hàng, sau đó xếp vị trí cho bé gái. Vì có cách thực hiện bước đầu và cách thực hiện bước thứ hai nên theo quy tắc nhân ta có số các cách xếp thoả mãn là

(b) Theo đầu bài, vị trí của các bé trai và các bé gái chỉ có thể như sau

Với vị trí của các bé trai là và các vị trí của các bé gái là . Theo quy tắc nhân, số cách xếp thoả mãn là

Ví dụ 4. Tìm số các số nguyên chẵn nằm giữa và sao cho các chữ số của chúng đôi một khác nhau.

Lời giải. Gọi là một số thoả mãn. Ta thấy và .

Nếu $a\in\{2,4,6\}$. Một số thoả mãn sẽ được hình thành sau ba bước: Đầu tiên chọn từ tập ; sau đó chọn từ tập ; cuối cùng chọn một hoán vị của tập và cho bằng số thứ nhất, bằng số thứ hai, và bằng số thứ ba của hoán vị.

Bởi vì có cách để làm bước thứ nhất, cách để làm bước thứ hai, và cách để làm bước thứ ba nên theo quy tắc nhân, số các số thoả mãn trong trường hợp này là .

Nếu . Tương tự ta có số các số thoả mãn trong trường hợp này là .

Theo quy tắc cộng, số các số thoả mãn là

Ví dụ 5. Gọi là tập các số nguyên có các chữ số lấy từ và các chữ số của chúng đôi một khác nhau. Tính và .

Lời giải. Gọi với là tập các số trong có chữ số, dễ thấy

Gọi tương ứng là tổng các chữ số hàng đơn vị, hàng chục, hàng trăm, hàng nghìn của các số trong $S$. Khi đó tổng cần tính bằng

i) Tính . Tổng các chữ số hàng đơn vị của các số trong bằng . Để tính tổng các chữ số hàng đơn vị của các số trong , ta cần tìm xem có bao nhiêu số trong có chữ số hàng đơn vị bằng tương ứng? Suy ra tổng các chữ số hàng đơn vị của các số trong bằng . Tương tự, tổng các chữ số hàng đơn vị của các số trong bằng , và trong bằng . Suy ra .

ii) Tính . Tương tự .

iii) Tính . Tương tự .

iv)Tính . Tương tự .

Vậy tổng cần tính bằng .