TOÁN 10 · ĐẠI SỐ TỔ HỢP — Đếm không cần liệt kê: quy tắc cộng, nhân, hoán vị, chỉnh hợp, tổ hợp và nhị thức Newton
Bài khái niệm Toán 10 về đại số tổ hợp, dựng quanh một câu hỏi: làm sao biết có bao nhiêu cách mà không phải liệt kê từng cách, và “có thứ tự hay không” thay…
TOÁN 10 · ĐẠI SỐ TỔ HỢP · LUKATO AI · BÀI KHÁI NIỆM
Đếm không cần liệt kê
Quy tắc cộng, quy tắc nhân, hoán vị, chỉnh hợp, tổ hợp và nhị thức Newton: mọi phép đếm đều là đếm đường đi trên một cây lựa chọn
Một bộ khóa có ba vòng số, mỗi vòng mười chữ số. Em có thể thử từng mã, nhưng cũng có thể chỉ nhìn một lần và biết ngay có đúng một nghìn mã. Bài này trả lời một câu hỏi: làm sao biết có bao nhiêu cách mà không phải liệt kê từng cách, và "có thứ tự hay không" thay đổi câu trả lời thế nào? Ẩn dụ xuyên suốt là ngăn kéo và con đường: mỗi lựa chọn là một ngã rẽ, và đếm số cách chỉ là đếm số đường đi từ gốc đến lá của cây. Từ một ý ấy, em sẽ hiểu khi nào cộng, khi nào nhân, vì sao 0! = 1, vì sao chỉnh hợp và tổ hợp khác nhau đúng một phép chia cho k!, vì sao tam giác Pascal sinh ra hệ số của nhị thức Newton, và cách chọn công cụ đúng chỉ bằng ba câu hỏi. Mọi tình huống và con số tự đặt đều là hư cấu.
12 SƠ ĐỒ TỰ DỰNG 3 PHÒNG THÍ NGHIỆM THUẦN KHÁI NIỆM 8 CÂU TRẮC NGHIỆM TỰ SOẠN
BẢN ĐỒ BÀI
Một cây lựa chọn, bốn công cụ, một bảng hệ số
Mỗi bài toán đếm đều có cùng một dáng: phải làm một việc gồm vài lựa chọn, và ta hỏi có bao nhiêu cách làm. Liệt kê từng cách thì chậm và dễ sót. Cách nhanh hơn là nhìn cấu trúc: các lựa chọn nối tiếp nhau (nhân), hay thay thế cho nhau (cộng); thứ tự có quan trọng không; có được dùng lại một vật không. Trả lời ba câu hỏi ấy là chọn được công cụ.
Vuốt ngang để xem hết sơ đồ
Hình 1. Bản đồ bài: quy tắc cộng và nhân là nền; từ đó sinh ra hoán vị, chỉnh hợp và tổ hợp; tổ hợp là hệ số của nhị thức Newton; mục 6 gom lại thành bản đồ chọn công cụ.
Câu hỏi · Ý then chốt · Ở mục
Khi nào cộng, khi nào nhân? Đếm trùng thì sao? · Hoặc (rời nhau) thì cộng; và (nối tiếp) thì nhân; có phần chung thì trừ phần chung · 1
Xếp n vật có bao nhiêu cách? Vì sao 0! = 1? · n! = n·(n − 1)·…·1; 0! = 1 để quy tắc nhân vẫn đúng · 2
Chọn k trong n vật và xếp thứ tự? · Chỉnh hợp: n·(n − 1)·…·(n − k + 1) · 3
Chọn k trong n vật mà không xét thứ tự? · Tổ hợp: chia chỉnh hợp cho k! vì mỗi nhóm bị đếm k! lần · 4
Hệ số trong (a + b) n từ đâu ra? · Chọn k trong n ngoặc để lấy b: hệ số là C k n ; tam giác Pascal liệt kê chúng · 5
Gặp bài toán đếm thì dùng công cụ nào? · Thứ tự? Lặp? Nhiều trường hợp? Khó đếm thì đếm phần bù · 6
Vuốt ngang để xem hết bảng
Công cụ A · Cây lựa chọn
Vẽ mỗi bước là một tầng của cây, mỗi lựa chọn là một nhánh. Mỗi lá ứng với đúng một cách; đếm lá là đếm cách.
Công cụ B · Cộng hay nhân
Các bước nối tiếp, bước nào cũng phải làm: nhân. Các phương án thay thế nhau, chỉ chọn một: cộng. Hai nhóm có phần chung: trừ phần chung.
Công cụ C · Thứ tự và lặp
Đổi chỗ hai vật đã chọn có thành cách khác không? Một vật có được dùng nhiều lần không? Hai câu trả lời chọn một trong bốn mô hình.
Giả định của bài (dùng suốt bài). (a) Nội dung bám chương trình Toán 10 hiện hành (chương trình giáo dục phổ thông mới): quy tắc cộng, quy tắc nhân, hoán vị, chỉnh hợp, tổ hợp và nhị thức Newton; phần bắt buộc khai triển nhị thức với số mũ 4 và 5. Dạng tổng quát cho mọi n được nêu ở mục 5 với nhãn MỞ RỘNG. (b) Các vật, người, ghế được đếm đều phân biệt được với nhau, trừ khi bài nói rõ. (c) n và k là số tự nhiên; A k n và C k n chỉ định nghĩa (bằng công thức giai thừa) khi 0 ≤ k ≤ n; còn khi k > n thì số cách chọn k vật khác nhau từ n vật bằng 0 (xem mục 3.2). Kí hiệu hoán vị là P n = n!. (d) Số nguyên từ 5 chữ số trở lên viết có dấu chấm ngăn hàng nghìn (ví dụ 3.628.800); không có số thập phân nào trong bài vì mọi kết quả đều là số nguyên chính xác.
Về chữ "hư cấu". Mọi lớp học, tuyến đường, thực đơn, đội thi, mật khẩu và các con số mô tả chúng đều do bài tự đặt, được kiểm bằng máy tính, và mang nhãn hư cấu . Các kết quả toán học (giai thừa, chỉnh hợp, tổ hợp, hệ số nhị thức) là chính xác. Phần ngoài chương trình bắt buộc mang nhãn MỞ RỘNG . Bài này nói về cách đếm; xác suất là bài riêng.
MỤC 1 · CỘNG VÀ NHÂN
Ngã rẽ nối tiếp thì nhân, đường song song thì cộng
Mọi phép đếm bắt đầu từ hai chữ rất nhỏ trong đề: "và" và "hoặc". "Làm việc này và làm việc kia" là các ngã rẽ nối tiếp. "Làm việc này hoặc làm việc kia" là các con đường thay thế nhau. Cả hai chữ đều nói về hình dạng của cây lựa chọn, và hình dạng quyết định phép tính.
1.1 Các bước nối tiếp: quy tắc nhân hư cấu
Một bạn đi từ A đến C và buộc phải qua B. Từ A đến B có 3 con đường a 1 , a 2 , a 3 ; từ B đến C có 2 con đường b 1 , b 2 . Chọn xong đường ở chặng đầu, chặng sau vẫn còn đủ 2 đường. Vẽ thành cây: gốc A mọc 3 nhánh, mỗi nhánh lại mọc thêm 2 nhánh nhỏ, tổng cộng 3 × 2 = 6 lá. Mỗi lá là một hành trình hoàn chỉnh, ví dụ "a 2 rồi b 1 ".
Vuốt ngang để xem hết sơ đồ
Hình 2. Cây lựa chọn của hành trình A → B → C (hư cấu): 3 đường chặng đầu, mỗi đường nối với 2 đường chặng sau, được 6 lá. Nét cam: hành trình a2 rồi b1.
Quy tắc nhân: m cách cho công đoạn 1, rồi n cách cho công đoạn 2 ⇒ m·n cách Với k công đoạn nối tiếp có m 1 , m 2 , …, m k cách: số cách là m 1 ·m 2 ·…·m k . Điều kiện: với mỗi cách chọn ở các công đoạn trước, công đoạn sau luôn có cùng số cách.
Vì sao nhân? Mỗi nhánh của chặng 1 "nhân bản" ra đủ n nhánh của chặng 2, nên m nhánh sinh ra m lần n lá. Thêm một chặng thứ ba có 4 đường thì mỗi lá cũ mọc thêm 4 lá: 6 × 4 = 24 hành trình. Đây cũng là cách tính số mã của bộ khóa ba vòng mười chữ số: 10 × 10 × 10 = 1000.
1.2 Các phương án thay thế: quy tắc cộng hư cấu
Từ điểm P đến điểm Q, em đi bằng một trong 3 tuyến buýt, hoặc một trong 2 tuyến tàu. Em chỉ đi bằng một phương tiện, nên hai nhóm đường không chồng lên nhau: 3 + 2 = 5 cách. Trên cây, đây là hai cây nhỏ được cắm chung một gốc; số lá của cây lớn bằng tổng số lá của hai cây nhỏ.
Quy tắc cộng: phương án 1 có m cách, phương án 2 có n cách, không cách nào thuộc cả hai ⇒ m + n cách Điều kiện then chốt là "rời nhau". Nếu có cách thuộc cả hai phương án, phép cộng đếm cách đó hai lần (xem mục 1.4).
Vuốt ngang để xem hết sơ đồ
Hình 3. Ba tình huống (hư cấu): đường song song thì cộng (3 + 2 = 5); hai chặng nối tiếp thì nhân (3 × 2 = 6); cây không đều thì cộng từng nhánh (2 + 1 + 3 = 6).
PHÒNG A Cây đếm: mỗi bước là một ngã rẽ hư cấu
Một hành trình có thể đi theo phương án A hoặc phương án B (hư cấu). Phương án A có 1 đến 3 bước nối tiếp, phương án B có 0 đến 2 bước (0 nghĩa là tắt B), mỗi bước có từ 1 đến 4 lựa chọn. Lab vẽ cây, tính tích trong từng phương án (quy tắc nhân), rồi cộng hai phương án (quy tắc cộng), và tô đỏ một đường đi để em đọc ra đó là lựa chọn nào ở từng bước. Giới hạn của lab: A tối đa 3 bước, B tối đa 2 bước, mỗi bước tối đa 4 lựa chọn, nên cây có nhiều nhất 4×4×4 + 4×4 = 64 + 16 = 80 lá.
Mẫu có sẵn
Số bước của A
Số bước của B
A, bước 1 3
A, bước 2 2
A, bước 3 4
B, bước 1 2
B, bước 2 3
Đường số 17
Số chính xác
Phương án A
Phương án B
Tổng hợp
Đường đang tô đỏ
Vuốt ngang để xem hết sơ đồ
1.3 Khi các nhánh không đều thì cộng từng nhánh hư cấu
Thực đơn của một quán (hư cấu) có 3 món chính. Món chính số 1 đi kèm 2 món phụ, món số 2 đi kèm 1 món phụ, món số 3 đi kèm 3 món phụ. Số phần ăn gồm một món chính và một món phụ không phải 3 × 2, vì số lựa chọn ở bước sau đổi theo bước trước. Ta cộng từng nhánh: 2 + 1 + 3 = 6.
Một chỗ dễ nhầm theo chiều ngược lại. Quy tắc nhân chỉ đòi số lựa chọn ở bước sau bằng nhau, chứ không đòi tập lựa chọn giống nhau. Xếp hai người vào hai ghế: người ngồi ghế thứ nhất có 4 cách; dù đó là ai, ghế thứ hai luôn còn đúng 3 người để chọn, tuy là 3 người khác nhau. Vì thế vẫn nhân: 4 × 3 = 12. Đây chính là cơ chế sinh ra chỉnh hợp ở mục 3.
1.4 Khi hai nhóm có phần chung: bù trừ hư cấu
Trong một lớp 30 bạn (hư cấu), 18 bạn chơi cờ vua, 14 bạn chơi bóng bàn, và 6 bạn chơi cả hai. Hỏi bao nhiêu bạn chơi ít nhất một trong hai môn? Cộng thô 18 + 14 = 32 là sai, vì 6 bạn chơi cả hai bị đếm hai lần: một lần trong nhóm cờ, một lần trong nhóm bóng bàn. Bỏ bớt một lần: 32 − 6 = 26. Kiểm lại bằng ba phần rời nhau: chỉ chơi cờ 12, chỉ chơi bóng bàn 8, cả hai 6; 12 + 8 + 6 = 26. Còn lại 30 − 26 = 4 bạn không chơi môn nào.
Vuốt ngang để xem hết sơ đồ
Hình 4. Biểu đồ Venn của lớp 30 bạn (hư cấu): chỉ cờ vua 12, cả hai 6, chỉ bóng bàn 8, ngoài cả hai 4. Số bạn chơi ít nhất một môn là 18 + 14 − 6 = 26.
|A ∪ B| = |A| + |B| − |A ∩ B| Quy tắc cộng chỉ đúng cho hai nhóm rời nhau (A ∩ B rỗng, giao bằng 0). Khi có phần chung, cộng rồi trừ phần chung. Đây là nguyên lí bù trừ cho hai tập hợp. Cách khác để tránh đếm trùng: đếm phần bù, tức là lấy tất cả trừ đi số cách không thỏa.
1.5 Đếm đủ để khẳng định, không cần liệt kê MỞ RỘNG hư cấu
Nguyên lí chuồng bồ câu. Nếu nhốt 13 con bồ câu vào 12 chuồng thì có một chuồng chứa ít nhất 2 con: nếu mỗi chuồng chỉ có tối đa 1 con thì tổng cộng chỉ có tối đa 12 con. Áp dụng: trong 13 người bất kì (hư cấu), chắc chắn có hai người sinh cùng một tháng (12 tháng là 12 chuồng). Ta không biết đó là ai, cũng không biết tháng nào, nhưng sự tồn tại thì chắc chắn. Tổng quát: nhét n + 1 vật vào n ngăn thì có ngăn chứa ít nhất 2 vật. Nguyên lí này không đếm số cách, mà đếm vừa đủ để chắc chắn có một cặp trùng.
Chốt ý mục 1: "và" nối tiếp thì nhân, "hoặc" rời nhau thì cộng Mỗi lá của cây là một cách. Các bước nối tiếp có số lựa chọn không đổi thì nhân; nhánh không đều thì cộng từng nhánh; hai nhóm có phần chung thì cộng rồi trừ phần chung.
Một bạn (hư cấu) có 3 áo và 2 quần. Có bao nhiêu cách mặc một bộ gồm một áo và một quần? Có bao nhiêu cách chọn đúng một món (một áo hoặc một quần) để tặng bạn khác?
Hỏi: các món có nối tiếp nhau, hay thay thế nhau?
Giải thích. Một bộ cần áo và quần: hai công đoạn nối tiếp, 3 × 2 = 6 bộ. Tặng đúng một món là áo hoặc quần: hai phương án thay thế nhau và rời nhau, 3 + 2 = 5 cách. Cùng hai con số 3 và 2 nhưng cho 6 hay 5 là do chữ "và" hay "hoặc" trong câu hỏi.
MỤC 2 · HOÁN VỊ
Xếp n vật vào n ngăn kéo: n giai thừa
Hoán vị là bài toán đếm đơn giản nhất mà vẫn bật ra một con số khổng lồ: có n vật khác nhau, xếp tất cả vào một hàng, có bao nhiêu thứ tự? Ẩn dụ ngăn kéo rất hợp: có n ngăn xếp thành hàng, mỗi ngăn đựng đúng một vật, và mỗi ngăn có ít lựa chọn hơn ngăn trước một đơn vị.
2.1 Quy tắc nhân cho các ngăn kéo hư cấu
Có 5 quyển sách khác nhau (hư cấu) cần xếp vào 5 ngăn kéo thành một hàng. Ngăn thứ nhất có 5 lựa chọn. Chọn xong, ngăn thứ hai chỉ còn 4 sách, ngăn thứ ba còn 3, rồi 2, rồi 1. Các ngăn nối tiếp nhau và số lựa chọn ở mỗi ngăn không phụ thuộc vào việc cụ thể đã đặt sách nào, nên ta nhân: 5 × 4 × 3 × 2 × 1 = 120 cách.
P n = n! = n·(n − 1)·(n − 2)·…·2·1 Mỗi cách xếp n vật khác nhau thành một hàng gọi là một hoán vị của n vật; số hoán vị kí hiệu P n và đọc là "n giai thừa".
Vuốt ngang để xem hết sơ đồ
Hình 5. Năm ngăn kéo với 5, 4, 3, 2, 1 lựa chọn cho 5! = 120 cách; bảng giai thừa từ 0! đến 10!; và lí do 0! = 1.
Bảng ở hình 5 cho thấy giai thừa lớn lên nhanh đến mức nào: 5! = 120, 10! = 3.628.800, còn 20! xấp xỉ 2,4·10 18 , lớn hơn số giây đã trôi qua kể từ Vụ Nổ Lớn (khoảng 4·10 17 giây). Vì thế "liệt kê từng cách" gần như không bao giờ khả thi khi n chỉ cỡ vài chục, trong khi một phép nhân thì xong ngay. Nhận xét hữu ích: n! = n·(n − 1)!, vì chọn vật cho ngăn đầu (n cách) rồi xếp n − 1 vật còn lại.
2.2 Vì sao 0! = 1 mà không phải 0
Đây là một quy ước, nhưng không tùy tiện. Có ba lí do cùng chỉ về một hướng.
- Đếm trực tiếp. Có bao nhiêu cách xếp 0 vật vào hàng? Đúng một cách: "không làm gì". Số cách không phải 0, vì 0 cách nghĩa là không xếp nổi, còn ở đây xếp được (và chỉ theo một kiểu).
- Giữ nguyên quy tắc nhân. Hệ thức n! = n·(n − 1)! đúng với mọi n ≥ 2. Muốn nó đúng luôn với n = 1 thì phải có 1! = 1·0!, tức 0! = 1. Giá trị 0! = 1 là giá trị duy nhất thỏa điều ấy.
- Giữ nguyên công thức tổ hợp. Chọn 0 vật từ n vật có đúng 1 cách. Công thức C k n = n!/(k!·(n − k)!) cho k = 0: n!/(0!·n!) = 1/0!. Muốn bằng 1 thì 0! = 1 (mục 4).
2.3 Hoán vị có điều kiện: gộp thành khối, hoặc đếm phần bù hư cấu
Năm bạn (hư cấu) xếp thành một hàng ngang, trong đó An và Bình phải đứng cạnh nhau. Coi An và Bình là một "khối": khối cùng 3 bạn còn lại là 4 đối tượng, có 4! = 24 cách xếp. Bên trong khối, An và Bình đổi chỗ được: 2! = 2 cách. Hai công đoạn nối tiếp, nhân: 24 × 2 = 48 cách. Muốn số cách không đứng cạnh nhau, ta lấy phần bù: tất cả trừ đi số cách đứng cạnh nhau, 5! − 48 = 120 − 48 = 72.