Share tài liệuChuyên mục tổ hợp xác suất - bài toán đếm euler

"Có k chiếc kẹo giống nhau chia cho n em bé. Hỏi có tất cả bao nhiêu cách chia kẹo?". Đây là bài toán chia kẹo của Euler. Bài toán tưởng chừng đơn giản này lại gây khó cho rất nhiều học sinh phổ thông. Một số bài toán về tổ hợp trong các đề thi học sinh giỏi quốc gia, Olympic toán có thể giải được nhờ vận dụng kết quả của bài toán chia kẹo này. Bài viết đề cập đến các đối tượng của tổ hợp như hoán vị lặp, tổ hợp lặp, bài toán tìm số nghiệm nguyên không âm của phương trình x1 + x2 + . . . + xn = k và một số ứng dụng của bài toán chia kẹo.
| || || || || || || || || || || || || || || || || || || || || |

Tổ hợp lặp hay bài toán chia kẹo của Euler là một trong các đối tượng tổ hợp có ứng dụng đa dạng và hiệu quả.

Tuy nhiên, trước khi đi vào phần chính, ta nói đến một đối tượng tổ hợp đơn giản hơn. Đó là hoán vị lặp.

Ta biết rằng nếu có n phần tử (ký tự) khác nhau thì có thể tạo ra n! hoán vị. Ví dụ từ 4 chữ cái ABCD có thể tạo ra 24 xâu độ dài 4. Thế nhưng nếu có những chứ cái trùng nhau thì sao? Chẳng hạn nếu có 2 chữ A, 2 chữ B thì tạo được bao nhiêu từ có 4 chữ cái? Bằng cách liệt kê, ta thấy chỉ có 6 từ như vậy: AABB, BBAA, ABBA, BAAB, BABA, ABAB. Số từ tạo thành giảm đi 4 lần.

Một cách tổng quát, giả sử có n chữ cái, nhưng có một số chữ cái giống nhau, chẳng hạn có r1 chữ A1, r2 chữ A2, ..., rk chữ Ak với r1+...+rk = n thì tạo ra được bao nhiêu từ có n chữ cái?

Ta có thể giải bài này bằng cách dùng tổ hợp như sau: Việc tạo ra 1 từ tương ứng với việc ta đặt r1 chữ A1 vào n vị trí, sao đó đặt r2 chữ A2 vào n-r1 vị trí còn lại ... Vì thế, số hoán vị cần tìm bằng nCr1(n-r1)Cr2...(n-r1-..-r(k-1))Crk = n!/r1!...rk!.

Ví dụ:
Bài toán 1. Hoa hồng ở cửa hàng có 3 màu: Vàng, đỏ, trắng. Hỏi có bao nhiêu cách bó một bó hoa hồng gồm 5 bông.

Đ/S: 7C2 = 21.

Bài toán 2. Có 10 người xếp thành một hàng dọc. Có bao nhiêu cách chọn ra 3 người sao cho không có hai người kề nhau được chọn.

Thứ tự của 3 người được chọn sẽ hoàn toàn được xác định bởi các tham số sau: x1 là số người từ đầu đến sát người được chọn, x2 là số người giữa người 1 và người 2, x3 là số người giữa người 2 và người 3, x4 là số người sau người 3 đến cuối. Thế thì x1 + x2 + x3 + x4 = 7, trong đó x2, x3 >=1. Đặt y2 = x2 - 1, y3 = x3 - 1 ta được x1 + y2 + y3 + x4 = 5 với các biến nguyên không âm. Áp dụng bài toán chia kẹo Euler ta có đá số là 8C3.

Bài toán 4. (VMO 2012) Cho một nhóm gồm 5 cô gái, kí hiệu là G1, G2, G3, G4, G5 và 12 chàng trai. Có 17 chiếc ghế được xếp thành một hàng ngang. Người ta xếp nhóm người đã cho ngồi vào các chiếc ghế đó sao cho các điều kiện sau được đồng thời thỏa mãn:

i/ Mỗi ghế có đúng một người ngồi;

ii/ Thứ tự ngồi của các cô gái, xét từ trái qua phải, là G1, G2, G3, G4, G5;

iii/ Giữa G1 và G2 có ít nhất 3 chàng trai;

iv/ Giữa G4 và G5 có ít nhất 1 chàng trai và nhiều nhất 4 chàng trai.

Hỏi có tất cả bao nhiêu cách xếp như vậy?

(Hai cách xếp được coi là khác nhau nếu tồn tại một chiếc ghế mà người ngồi ở chiếc ghế đó trong hai cách xếp là khác nhau).

GIải:


Đánh số thứ tự các ghế từ trái sang phải là 1, 2, …,17.

Gọi x1 là số chàng trai được xếp bên trái G1, x2 là số chàng trai ở giữa G1 và G2, x3 là số chàng trai ở giữa G2 và G3, x4 là số chàng trai ở giữa G3 và G4, x5 là số chàng trai ở giữa G4 và G5, x6 là số chàng trai được xếp ở bên phải G5. Khi đó bộ số (x1, x2, …, x6) hoàn toàn xác định vị trí các cô gái và ta có 1) x1 + x2 + … + x6 = 12 2) 3 ≤ x2 3) 1 ≤ x5 ≤ 4

Đổi biến y2 = x2 – 3 và y5 = x5 – 1 ta được

x1 + y2 + x3 + x4 + y5 + x6 = 8 Với các ẩn không âm và có thêm điều kiện y5 ≤ 3.

Tiếp theo, sử dụng bài toán chia kẹo của Euler ở dạng

x1 + y2 + x3 + x4 + x6 = 8 – y5 ta được số cách phân ghế cho các cô gái là 12C4+11C4+10C4+9C4 = 1161.

Vì còn có 12 chàng trai có thể hoán đổi vị trí ở 12 chiếc ghế dành cho họ nên số cách xếp thỏa mãn yêu cầu bài toán là 12! 1161.


-katyusha
(Bài viết có 1 số thông tin được sưu tầm từ các diễn đàn trong và ngoài nước.)