Chỉnh hợp

Ta dùng chỉnh hợp khi chọn ra một số đối tượng từ một tập hợp các đối tượng, trong đó thứ tự chọn các đối tượng có ý nghĩa.

Xây dựng công thức

Ta bắt đầu bằng một bài toán điển hình về chỉnh hợp: trong làng hằng năm có tổ chức cuộc thi ăn bánh trôi. Vào vòng chung kết có tất cả 7 thí sinh đã no căng bụng. Tính số cách để 7 thí sinh này chiếm 3 vị trí đầu.

Cần nhận thấy rằng trong ví dụ này thứ tự có ý nghĩa. Chẳng hạn nếu biết 3 vị trí đầu thuộc về Minh, Hùng và Nam thì bộ ba này cho tất cả 6 cách xếp hạng khác nhau:

• Minh, Hùng, Nam;
• Minh, Nam, Hùng;
• Hùng, Minh, Nam;
• Hùng, Nam, Minh;
• Nam, Minh, Hùng;
• Nam, Hùng, Minh.

Đây đều là những cách xếp hạng khác nhau, và ta muốn tính xem có tất cả bao nhiêu cách xếp hạng khác nhau khi có 7 thí sinh.

Ta dùng quy tắc nhân. Ta chọn các bộ ba dạng (x₁; x₂; x₃), trong đó x₁ là thí sinh về nhất, v.v. Những thí sinh nào có thể đứng ở vị trí x₁? Tất cả, tức là có 7 thí sinh cho vị trí x₁. Những ai có thể đứng ở vị trí x₂? Tất cả, trừ người đã đứng ở vị trí thứ nhất, nên có 7 − 1 = 6 thí sinh cho vị trí x₂. Ở vị trí x₃ có thể là những thí sinh không đứng ở vị trí thứ nhất hay thứ hai, nên có 7 − 2 = 5 khả năng. Áp dụng quy tắc nhân, ta được tổng số khả năng: 7 · 6 · 5 = 210.

Ta thấy rằng nếu muốn biết số khả năng cho 4 vị trí đầu thì ở vị trí x₄ có 7 − 3 = 4 thí sinh, nên tổng số khả năng là 7 · 6 · 5 · 4 = 840. Từ đây rút ra được điều gì?

Nếu có một tập hợp gồm n phần tử (trong ví dụ là 7 thí sinh) và ta chọn ra 3 phần tử, trong đó thứ tự có ý nghĩa, thì kết quả bằng n · (n − 1) · (n − 2). Ở vị trí thứ nhất có thể là bất kì ai, ở vị trí tiếp theo ít hơn 1 người, v.v. Từ đó suy ra công thức tổng quát khi chọn k phần tử từ một tập hợp gồm n phần tử: số khả năng bằng n · (n − 1) · (n − 2) · … · (n − k + 1).

Ta biến đổi tiếp công thức này nhờ giai thừa. Nhìn vào giai thừa của 7: 7! = 7 · 6 · 5 · 4 · 3 · 2 · 1 và cách ta tính số cách trao huy chương 7 · 6 · 5, ta thấy hai biểu thức khá giống nhau. Chỉ cần bỏ phần đuôi, tức là chia 7! cho 4 · 3 · 2 · 1, khi đó chỉ còn lại 7 · 6 · 5. Còn biểu thức 4 · 3 · 2 · 1 bằng bao nhiêu? Đó chính là 4!.

Như vậy, nếu có một tập hợp gồm n phần tử và ta chọn ra k phần tử, trong đó thứ tự có ý nghĩa, thì có tất cả

$${\mathrm{A}}_n^k=\frac{n!}{(n-k)!}$$

khả năng. Mỗi cách chọn như vậy gọi là một chỉnh hợp. Thay số từ cuộc thi ăn bánh trôi vào công thức:

$${\mathrm{A}}_7^3=\frac{7!}{(7-3)!}=\frac{7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}{4\cdot 3\cdot 2\cdot 1}=7\cdot 6\cdot 5=210.$$

Máy tính

Máy tính sau đây tính số chỉnh hợp với n và k cho trước.

Ví dụ có lời giải

1. Vẫn xét cuộc thi ăn bánh trôi. Số cách trao huy chương sẽ thay đổi thế nào nếu biết rằng có Tuấn tham gia, một cao thủ luôn giành chiến thắng? Tức là có bao nhiêu cách trao huy chương khác nhau nếu có 7 thí sinh và chắc chắn Tuấn về nhất?

Đây lại là một chỉnh hợp đơn giản: vị trí thứ nhất đã chắc chắn, chỉ cần xác định xem 6 thí sinh còn lại có thể chiếm vị trí thứ hai và thứ ba như thế nào. Như vậy ta chọn 2 phần tử từ một tập hợp có 6 phần tử, dẫn đến chỉnh hợp

$${\mathrm{A}}_6^2=\frac{6!}{(6-2)!}=30$$

2. Ngày xưa, khi Tuấn chưa giỏi như bây giờ, anh thường xuyên lọt vào ba vị trí đầu. Có bao nhiêu cách trao huy chương khác nhau nếu có 7 thí sinh và chắc chắn Tuấn nhận được một huy chương nào đó?

   Ví dụ này khác ví dụ trước ở chỗ ta không biết Tuấn đứng ở vị trí nào; anh có thể chỉ về nhì, thậm chí về ba, điều mà đến giờ anh vẫn còn xấu hổ. Vì vậy ta phải tính 3 chỉnh hợp khác nhau: trường hợp Tuấn về nhất, trường hợp Tuấn giành huy chương bạc và cuối cùng là huy chương đồng. Tuy nhiên mỗi lần chỉ còn lại 2 vị trí cho người khác. Chẳng hạn nếu Tuấn về nhì thì những người còn lại có thể đứng ở vị trí thứ nhất hoặc thứ ba. Như vậy ta lại tính chỉnh hợp chập 2 của 6, chỉ có điều phải tính 3 lần, ứng với 3 vị trí khác nhau của Tuấn. Tổng số cách xếp hạng là:

   $$3\cdot {\mathrm{A}}_6^2=3\cdot \frac{6!}{(6-2)!}=3\cdot 30=90$$

   Lưu ý rằng số 3 đứng trước chỉnh hợp có thể viết là ${\mathrm{A}}_3^1$, vì thực chất ta chọn 1 phần tử (một vị trí cụ thể) từ một tập hợp có 3 phần tử (3 vị trí có huy chương).

3. Trường có tất cả 20 giáo viên. Sắp đến kỳ thi tốt nghiệp THPT và cần lập một hội đồng gồm: một chủ tịch, một uỷ viên dễ tính và một uỷ viên khó tính. Có tất cả bao nhiêu khả năng?

   Trước hết phải trả lời câu hỏi thứ tự có ý nghĩa không: có, vì 3 giáo viên lại có thể hoán đổi vị trí theo 6 cách khác nhau. Bây giờ thì đơn giản: ta chọn chỉnh hợp chập 3 của 20 phần tử:

   $${\mathrm{A}}_{20}^3=\frac{20!}{17!}=6840.$$

4. Từ các chữ số {0; 1; 2; 3; 4; 5} có thể lập được bao nhiêu số có ba chữ số, nếu không chữ số nào được lặp lại?

   Thứ tự có ý nghĩa không? Có, 123 là số khác với 321. Có bao nhiêu bộ ba khác nhau? Đó là chỉnh hợp chập 3 của 6:

   $${\mathrm{A}}_6^3=\frac{6!}{3!}=120.$$

   Nhưng ta còn phải bớt đi các chỉnh hợp có chữ số 0 ở vị trí thứ nhất, vì 012 không phải là số có ba chữ số. Câu hỏi bây giờ là: có bao nhiêu bộ ba khác nhau bắt đầu bằng chữ số 0? Khi đó các chữ số chỉ thay đổi ở 2 vị trí còn lại (các bộ ba có dạng (0; x₂; x₃)), nên ta tìm xem có thể lập được bao nhiêu cặp khác nhau từ các số {1; 2; 3; 4; 5}. Điều này cũng đơn giản: ${\mathrm{A}}_5^2=5!/3!=20$. Vậy có 20 bộ ba bắt đầu bằng chữ số 0.

   Tổng số các số có ba chữ số lập từ các chữ số {0; 1; 2; 3; 4; 5} là 120 − 20 = 100.

5. Từ các chữ số {1; 2; 3; 4; 5} có thể lập được bao nhiêu số có ba chữ số khác nhau, nếu không chữ số nào được lặp lại và số lập được phải là số lẻ?

   Thứ tự có ý nghĩa, vì 123 là số khác với 321. Ta lập số lẻ có ba chữ số, nghĩa là ở 2 vị trí đầu có thể là chữ số bất kì, nhưng ở vị trí cuối phải là một trong các chữ số {1; 3; 5}. Trước hết ta tính số tất cả các bộ ba lập được từ 5 chữ số: ${\mathrm{A}}_5^3=5!/2!=60$.

   Mỗi chữ số xuất hiện ở vị trí cuối với số lần như nhau, nên với 5 chữ số, mỗi chữ số xuất hiện ở vị trí cuối 60 / 5 = 12 lần. Có 3 chữ số {1; 3; 5} có thể đứng ở vị trí cuối, nên có 12 số tận cùng bằng 1, 12 số tận cùng bằng 3 và 12 số tận cùng bằng 5. Áp dụng quy tắc cộng, ta được tất cả 12 + 12 + 12 = 36 khả năng.

6. Tìm x, biết rằng ${\mathrm{A}}_x^2=72$. Nói cách khác: từ một tập hợp có x phần tử ta chọn ra các cặp có thứ tự và biết rằng chọn được tất cả 72 cặp khác nhau. Tập hợp ban đầu có bao nhiêu phần tử? Ta viết ra:

   $${\mathrm{A}}_x^2=\frac{x!}{(x-2)!}=72$$

   Biến đổi tiếp:

   $$\begin{array}{rcl}\frac{x!}{(x-2)!}& =& 72\\ \frac{x\cdot (x-1)\cdot (x-2)!}{(x-2)!}& =& 72\\ x\cdot (x-1)& =& 72\\ x^2-x& =& 72\\ x^2-x-72& =& 0\end{array}$$

   Đây là một phương trình bậc hai quen thuộc, ta giải bằng biệt thức hoặc viết lại phương trình dưới dạng

   $$(x+8)\cdot (x-9)=0$$

   từ đó đọc ngay được nghiệm: x₁ = −8 và x₂ = 9. Nghiệm âm bị loại, vì số phần tử của tập hợp không thể âm, nên nghiệm của phương trình ban đầu là x = 9: tập hợp có 9 phần tử.