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à

Continue reading “Permutations” →