Tổ hợp là một dạng toán khó. Khó vì chúng ta chưa quen và thời gian chưa đủ để ngấm khái niệm. Vì thế rất cần phải tiếp cận một cách bài bản.
Các bài toán tổ hợp rất đa dạng phong phú về nội dung cũng như phương pháp giải. Nhưng tất cả phải bắt đầu từ phép đếm.
Ta phải biết đếm để giải các bài toán ... đếm (Tìm số phần tử của một tập hợp) nhưng ta cũng phải biết đếm để giải các bài toán tổ hợp khác.
Bài hôm nay ta nói về quy tắc đếm.
Trước hết, một ta nói tập hợp hữu hạn A có n phần tử nếu tồn tại song ánh f từ A vào tập hợp {1, 2, ..., n}. Nôm nay là khi ta đếm các phần tử của A từ 1, 2, 3 thì kết thúc bằng n. Trong quá trình đó ta không đếm lặp (hai phần tử được gán chung một số) và không đếm cách (bị nhảy). Không đếm lặp tức là đơn ánh, không đếm cách tức là toàn ánh. Một ánh xạ có hai tính chất ấy gọi là song ánh.
Có ba quy tắc đếm cơ bản ta cần biết.
Thứ nhất là quy tắc cộng. Nếu một tập hợp có thể chia thành một số tập con rời nhau thì để đếm số phần tử của tập hợp, ta đếm số phần tử của các tập con rồi cộng lại. Ví dụ để biết số học sinh hiện diện trong buổi chào cờ thì chỉ cần lấy báo cáo từ các GVCN ở mỗi lớp rồi cộng lại. Nếu một công việc có 2 phương án thực hiện, phương án thứ nhất có m cách thực hiện, phương án thứ hai có n cách thực hiện thì công việc đó có m + n cách thực hiện. Quy tắc cộng vì thế sử dụng trong các tình huống ta phải phân trường hợp, phân phương án.
Quy tắc cộng không giúp tăng tốc độ tính mà chỉ chia việc ra để xử lý song song. Nhưng quy tắc nhân thì là quy tắc công nghiệp. Ví dụ nếu cần biết số lượng bàn trong một phòng học, ta chỉ cần đếm số dãy bàn rồi nhân với số bàn của mỗi dãy. Quy tắc nhân có thể phát biểu: Nếu một công việc có thể phân thành 2 công đoạn. Công đoạn 1 có m cách thực hiện, công đoạn 2, sau khi thực hiện công đoạn 1, có n cách thực hiện thì công việc ấy có m.n cách thực hiện. Quy tắc nhân vì thế phù hợp với các bài toán mà công việc có thể thực hiện tuần tự (thành lập tổ trực, rút quân bài, lập các số có n chữ số)
Quy tắc nhân sẽ giúp chúng ta tăng đáng kể tốc độ đếm. Nhưng nó chỉ làm việc tốt với các tập hợp có cấu trúc đều (ví dụ nếu học sinh toàn trường xếp hàng ngay ngắn thì ta đếm rất nhanh, nhưng nếu cách em chạy lung tung trong sân trường thì khó lòng đếm nhanh và đếm đúng). Trong tình huống tập hợp có cấu trúc phức tạp thì ta phải sắp xếp lại hoặc chia nhỏ ra (sử dụng quy tắc cộng).
Một quy tắc nữa cũng được dùng để giải quyết các bài toán đếm, đó là quy tắc phần bù. Nếu ta đã biết số học sinh của trường và muốn biết có bao nhiêu học sinh hiện diện, ta chỉ cần biết số học sinh vắng. Rõ ràng đếm số học sinh vắng sẽ nhanh hơn (vì ít hơn).
Ta đi vào phần thực hành. Ta bắt đầu từ bài toán đơn giản sau.
Bài toán 1. Trong các số tự nhiên viết trong hệ thập phân.
i) Có bao nhiêu số có 3 chữ số?
ii) Có bao nhiêu số chẵn có 3 chữ số?
iii) Có bao nhiêu số có 3 chữ số khác nhau?
iv) Có bao nhiêu số chẵn có 3 chữ số khác nhau?
Bài toán i) và ii) có thể giải bằng cách lớp 5: bài toán đếm cách. Nhưng đến bài iii) thì khó rồi. Ở đây các số không còn liên tiếp hay cách đều nữa. Và ta đếm bằng quy tắc nhân như sau: Một số có ba chữ số có dạng abc. a có 9 cách chọn (a khác 0), b có 9 cách chọn (khác a), c có 8 cách chọn (khác a và c). Vì thế có 9 x 9 x 8 = 648 số có ba chữ số khác nhau.
Sang bài toán iv) nếu tiếp tục làm như vậy thì hai công đoạn đầu (chọn a và chọn b) không gặp khó khăn gì, nhưng đến công đoạn 3 (chọn c) thì ta gặp khó. Do c phải chẵn nên số cách chọn c ở đây sẽ phụ thuộc vào sự kiện còn bao nhiêu số trong các chữ số khác a, b là số chẵn. Trong tình huống như thế, ta không áp dụng trực tiếp quy tắc nhân được.
Phải làm thế nào? Có 1 số cách tiếp cận.
1. Để số cách chọn c là hoàn toàn xác định, ta chia các cách chọn ab thành 4 loại: (chẵn,chẵn), (chẵn, lẻ), (lẻ, chẵn), (lẻ, lẻ). Số cách chọn a rồi b rồi c trong các TH tương ứng sẽ là 4x4x3=48, 4x5x4=80, 5x5x4=100, 5x4x5=100. Cộng lại ta được đáp số 328.
2. Ta có thể đổi thứ tự thực hiện: chọn c trước rồi mới chọn a, b. Ở đây vẫn có đôi chút rắc rối ở khâu chọn a (do a phải khác 0 và khác c), vì thế ta phân làm 2 TH.
+ Chọn c = 0, sau đó chọn a, b. a có 9 cách chọn, b có 8 cách chọn. TH này ta có 72 số.
+ Chọn c chẵn, khác 0, sau đó chọn a, b. c có 4 cách chọn, a có 8 và b cũng có 8. TH này có 256 số.
Cộng lại ta được 328.
3. Ta đã biết là có 648 số có 3 chữ số khác nhau. Để đếm xem có bao nhiêu số chẵn có ba chữ số khác nhau, ta đếm xem có bao nhiêu số lẻ có 3 chữ số khác nhau. Bài toán này hóa ra dễ hơn. Ta thiết lập 1 số có 3 chữ số như thế theo thứ tự chọn c, chọn a rồi chọn b. c có 5 cách chọn (c phải lẻ), a có 8 cách chọn (a khác c và khác 0, chắc chắn là c khác 0 rồi!), b có 8 cách chọn (b khác c và khác a). Vì thế có 5 x 8 x 8 = 320 số lẻ có 3 chữ số khác nhau. Theo quy tắc phần bù, ta có 648 - 320 = 328 số chẵn có 3 chữ số khác nhau.
Qua ví dụ trên ta thấy để giải bài toán đếm, ta cần áp dụng một cách hợp lý các quy tắc nhân, quy tắc cộng và quy tắc phần bù. Tư tưởng chủ đạo là quy tắc nhân (ta phải làm việc công nghiệp chứ) nhưng dùng quy tắc cộng và quy tắc phần bù để tháo gỡ khó khăn. Ta tiếp tục xem xét một ví dụ nữa.
Bài toán 2. Ở một nhà hàng có 3 món khai vị là salat Nga, mầm cải trộn cá ngừ và gỏi ngó sen tôm thịt, 4 món chính là sườn nướng, đùi gà rô-ti, cá kèo kho tộ và thịt kho trứng, 3 món canh là canh cải thịt bằm, cành gà lá giang và canh khổ qua cá thác lác, 4 món tráng miệng là bánh flan, chè đậu đỏ, trái cây thập cẩm và sữa chua.
a) Hỏi có bao nhiêu cách chọn 1 bữa ăn gồm 1 món khai vị, 1 món chính, một canh và một món tráng miệng.
b) Có một người không thích cá nhưng vì bác sĩ yêu cầu phải ăn cá nên người đó chỉ chọn đúng một món cá trong các món ăn. Hỏi người ấy có bao nhiêu cách chọn bữa ăn?
Câu a) là quá đơn giản. Ta chỉ cần dùng quy tắc nhân và đáp số sẽ là 3x4x3x4 = 144. Với câu b), ta chỉ cần xét 3 TH: 1) Món cá là món khai vị 2) món cá là món chính 3) món cá là món canh. Đáp số sẽ là 1 x 3 x 2 x 4 + 2 x 1 x 2 x 4 + 2 x 3 x 1 x 4 = 64.
Chú ý trong bài toán đếm, việc chọn thứ tự thực hiện đóng một vai trò quan trọng. Có thể nói, nếu sắp xếp công việc tốt thì ta đếm nhanh và nhàn nhã, còn sắp xếp kém thì đếm phức tạp và dễ sai. Một nguyên tắc là những công đoạn có nhiều ràng buộc sẽ được ưu tiên thực hiện trước.
Để kết thúc bài giảng mở đầu này, mời các bạn làm bài tập sau:
Bài tập
1. Có bao nhiêu số tự nhiên có 7 chữ số khác nhau thỏa mãn
i) Không chứa chữ số 1;
ii) Có chứa chữ số 1;
iii) Có chứa các chữ số 0 và 1.
2. Có bao nhiêu số có 3 chữ số khác nhau và chia hết cho 3?



Bạn là khách nên chưa được phép xem hoặc tải tài liệu này
[Bạn cần đăng nhập hoặc để xem nội dung]