Chương 40: Nghệ thuật đếm

Câu hỏi mở đầu

Mọi mô hình trong Phần III và IV đều giả định ta biết chắc: biết quy luật, biết điều kiện ban đầu, và tương lai hoàn toàn xác định. Nhưng thế giới đầy bất định. Làm sao tính toán với điều chưa biết? Bước đầu tiên: có bao nhiêu khả năng có thể xảy ra?

Đếm mà không liệt kê

Tung hai đồng xu, có bốn khả năng: sấp sấp, sấp ngửa, ngửa sấp, ngửa ngửa. Liệt kê là cách đếm đáng tin nhất, nhưng nó hỏng rất nhanh. Tráo một bộ bài 52 lá, có bao nhiêu thứ tự? Con số là \(52!\), khoảng \(8{,}07 \times 10^{67}\). Nếu mỗi giây liệt kê được một tỉ thứ tự, việc liệt kê sẽ kéo dài khoảng \(2{,}6 \times 10^{51}\) năm. Không ai liệt kê được; ta chỉ đếm được, bằng cách nhìn vào cấu trúc của cách các khả năng được tạo ra.

Cấu trúc ấy có vài dạng quay đi quay lại. Một khả năng thường được tạo ra qua nhiều bước nối tiếp: chọn món chính, rồi chọn đồ uống, rồi chọn tráng miệng. Khi ấy số khả năng là một tích. Một khả năng có thể rơi vào một trong vài trường hợp loại trừ nhau: đi bằng xe buýt hoặc bằng tàu. Khi ấy số khả năng là một tổng. Có khi ta đếm thừa có hệ thống, mỗi thứ đúng \(k\) lần, và phải chia cho \(k\). Và có khi đếm cái mình không muốn dễ hơn, nên lấy tổng trừ đi phần còn lại.

Vì sao những cấu trúc này phải xuất hiện, dù chưa ai đặt tên cho chúng? Vì chúng là cách thế giới khả năng được lắp ráp. Chương 5 đã thấy phép nhân là số ô của một lưới hình chữ nhật: mỗi hàng ứng với một lựa chọn thứ nhất, mỗi cột ứng với một lựa chọn thứ hai. Không ai chọn cho số suất ăn là một tích; nó bị ép ra từ việc mỗi suất là một cặp. Tương tự, việc chia cho \(k!\) khi không kể thứ tự bị ép ra từ việc ta cố ý không phân biệt những thứ tự khác nhau của cùng một nhóm, đúng hành động "đồng nhất" của Chương 3.

Cây lựa chọn

Quán ở bài B7 của Chương 5 có 4 loại bánh và 3 loại nước. Vẽ các lựa chọn thành một cây: từ gốc tỏa ra 4 nhánh ứng với 4 loại bánh, từ mỗi nhánh tỏa tiếp 3 nhánh ứng với 3 loại nước. Mỗi đường từ gốc tới ngọn là một suất, và có \(4 \cdot 3 = 12\) ngọn. Thêm 2 món tráng miệng, mỗi ngọn lại tỏa 2 nhánh: \(12 \cdot 2 = 24\) suất. Đó là quy tắc nhân (multiplication principle), và hình vẽ các lựa chọn thành nhánh như thế gọi là sơ đồ cây (tree diagram).

Mỗi đường từ gốc tới ngọn là một suất ăn. Bước 1 có 4 nhánh, và từ mỗi nhánh, bước 2 có 3 nhánh, nên có \(4 \cdot 3 = 12\) ngọn.

Điều kiện then chốt là số nhánh ở mỗi bước không phụ thuộc vào nhánh đã đi ở các bước trước. Xếp 5 người thành một hàng: chỗ đầu có 5 cách chọn người; dù đã chọn ai, chỗ thứ hai còn 4 cách; rồi 3, 2, 1. Vậy có \(5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 5! = 120\) cách xếp, với giai thừa của Chương 18. Những người được chọn thì khác nhau tùy nhánh, nhưng số lựa chọn còn lại thì không.

Khi các khả năng rơi vào những trường hợp loại trừ nhau, ta cộng. Từ nhà tới cơ quan có 3 tuyến xe buýt và 2 chuyến tàu; mỗi cách đi là hoặc một tuyến buýt, hoặc một chuyến tàu, không thể là cả hai. Vậy có \(3 + 2 = 5\) cách. Đó là quy tắc cộng (addition principle). Nhân cho "và rồi", cộng cho "hoặc là".

Bây giờ chọn ba người trong một nhóm 10 người. Nếu ba người ấy giữ ba chức khác nhau, trưởng nhóm, thư ký và thủ quỹ, quy tắc nhân cho \(10 \cdot 9 \cdot 8 = 720\) cách. Nếu ba người chỉ cùng làm một việc, không phân vai, thì mỗi nhóm ba người đã được đếm nhiều lần: cùng ba người An, Bình, Chi xuất hiện trong mọi cách phân ba chức cho họ, và có \(3! = 6\) cách như thế. Mỗi nhóm bị đếm đúng 6 lần, nên số nhóm là \(\frac{720}{6} = 120\).

Ký hiệu

Một cách sắp xếp \(n\) đối tượng khác nhau thành một hàng gọi là một hoán vị (permutation) của chúng; có \(n!\) hoán vị, với quy ước \(0! = 1\). Một cách chọn \(k\) trong \(n\) đối tượng rồi xếp chúng theo thứ tự gọi là một chỉnh hợp (arrangement) chập \(k\) của \(n\); theo quy tắc nhân, có

\[ n(n - 1) \cdots (n - k + 1) = \frac{n!}{(n - k)!} \]

chỉnh hợp như thế. Sách giáo khoa viết số này là \(A_n^k\).

Một cách chọn \(k\) trong \(n\) đối tượng, không kể thứ tự, tức một tập con \(k\) phần tử của một tập \(n\) phần tử (Chương 19), gọi là một tổ hợp (combination) chập \(k\) của \(n\). Số tổ hợp viết là \(\binom nk\), đọc "\(n\) chọn \(k\)"; sách giáo khoa viết \(C_n^k\). Mỗi tổ hợp ứng với đúng \(k!\) chỉnh hợp, các thứ tự khác nhau của cùng \(k\) đối tượng, nên

\[ \binom nk = \frac{n!}{k!\,(n - k)!}. \]

Các số \(\binom nk\) còn gọi là hệ số nhị thức (binomial coefficient), vì chúng là hệ số khi khai triển \((x + y)^n\). Công thức khai triển ấy,

\[ (x + y)^n = \sum_{k=0}^{n} \binom nk x^k y^{n - k}, \]

gọi là nhị thức Newton (binomial theorem). Xếp các số \(\binom nk\) thành hàng, hàng thứ \(n\) gồm \(\binom n0, \binom n1, \dots, \binom nn\), ta được tam giác Pascal (Pascal's triangle), trong đó mỗi số bằng tổng hai số ngay phía trên nó.

Làm bằng tay

Ví dụ 1 (biển số). Một kiểu biển số giả định gồm 2 chữ cái Latin (26 chữ) rồi 4 chữ số. Quy tắc nhân cho \(26 \cdot 26 \cdot 10^4 = 6.760.000\) biển số. Nếu hai chữ cái phải khác nhau, số biển giảm còn \(26 \cdot 25 \cdot 10^4 = 6.500.000\): bước thứ hai có ít lựa chọn hơn, nhưng vẫn là cùng một số, 25, dù bước thứ nhất đã chọn chữ nào.

Ví dụ 2 (bắt tay và chọn cặp). Năm người bắt tay nhau từng đôi một. Mỗi cái bắt tay là một cặp người, nên số cái bắt tay là \(\binom 52 = \frac{5 \cdot 4}{2} = 10\). Phép đếm \(5 \cdot 4 = 20\) đếm các cặp có thứ tự, "An bắt tay Bình" và "Bình bắt tay An", nên mỗi cái bắt tay bị đếm hai lần. Với \(n\) người, có \(\binom n2 = \frac{n(n - 1)}{2}\) cái bắt tay, đúng con số ở Chương 28.

Ví dụ 3 (tay bài). Số cách rút 5 lá từ bộ bài 52 lá, không kể thứ tự, là

\[ \binom{52}{5} = \frac{52 \cdot 51 \cdot 50 \cdot 49 \cdot 48}{5!} = 2.598.960. \]

Bao nhiêu tay bài có ít nhất một con át? Đếm trực tiếp phải chia trường hợp một, hai, ba, bốn con át. Đếm phần bù (Chương 19) dễ hơn nhiều: số tay bài không có con át nào là số cách chọn 5 trong 48 lá không phải át, \(\binom{48}{5} = 1.712.304\). Vậy có \(2.598.960 - 1.712.304 = 886.656\) tay bài có ít nhất một con át, khoảng \(34{,}1\%\) tổng số.

Ví dụ 4 (đường đi trên lưới). Trên một lưới 4 ô ngang, 3 ô dọc, đi từ góc dưới trái \(A\) tới góc trên phải \(B\), mỗi bước sang phải một ô hoặc lên trên một ô. Mỗi đường đi gồm đúng 7 bước: 4 bước sang phải và 3 bước lên. Một đường đi được xác định hoàn toàn khi biết 3 bước nào trong 7 bước là bước lên, nên có \(\binom73 = 35\) đường. Có một cách đếm khác: số đường tới một nút bằng số đường tới nút bên trái cộng số đường tới nút bên dưới, vì bước cuối cùng đến từ một trong hai nút ấy. Ghi các số ấy lên lưới, ta thấy lại tam giác Pascal nằm nghiêng.

Số xanh ở mỗi nút là số đường đi từ \(A\) tới nút ấy, bằng tổng hai số ở nút bên trái và nút bên dưới. Tại \(B\) có \(\binom73 = 35\) đường. Đường cam là một đường, viết thành dãy bước P (phải) và L (lên).

Ví dụ 5 (tam giác Pascal và nhị thức Newton). Khai triển \((x + 1)^5\) là tích của 5 thừa số \(x + 1\). Mỗi số hạng của khai triển chọn \(x\) từ một số thừa số và 1 từ những thừa số còn lại; số cách chọn \(x\) từ đúng \(k\) thừa số là \(\binom5k\). Vậy

\[ (x + 1)^5 = x^5 + 5x^4 + 10x^3 + 10x^2 + 5x + 1, \]

với các hệ số là hàng \(n = 5\) của tam giác Pascal. Đây chính là lập luận của Ví dụ 1 ở Chương 35, nơi hệ số của \(h\) trong \((x + h)^n\) là \(n = \binom n1\). Thay \(x = 1\): tổng hàng thứ \(n\) là \(2^n\), đúng số tập con của một tập \(n\) phần tử.

Tam giác Pascal, hàng \(n = 0\) tới \(n = 6\). Mỗi số bằng tổng hai số ngay phía trên nó: ô cam \(10 = \binom52\) là tổng của hai ô xanh \(4 = \binom41\) và \(6 = \binom42\).

Ví dụ 6 (chia kẹo). Chia 10 viên kẹo giống nhau cho ba bạn An, Bình, Chi; có thể có bạn không được viên nào. Có bao nhiêu cách? Viết 10 viên kẹo thành 10 ngôi sao, rồi đặt 2 vạch để cắt hàng sao thành ba đoạn: đoạn đầu cho An, đoạn giữa cho Bình, đoạn cuối cho Chi. Mỗi cách chia ứng với đúng một cách xếp 10 sao và 2 vạch thành một hàng 12 ký hiệu, và ngược lại. Một cách xếp được xác định khi biết 2 vị trí nào trong 12 là vạch, nên có \(\binom{12}{2} = 66\) cách chia. Đó cũng là số nghiệm nguyên không âm của \(x + y + z = 10\). Mẹo biến bài toán chia thành bài toán xếp sao và vạch gọi là phương pháp sao và vạch (stars and bars).

Cách chia An 3, Bình 5, Chi 2 viết thành một hàng 10 ngôi sao và 2 vạch. Mỗi cách chia ứng với đúng một cách chọn 2 trong 12 vị trí để đặt vạch.

Ví dụ 7 (lời giải cho câu đố ở Chương 1). Chương 1 đặt \(n\) điểm trên một đường tròn, nối mọi cặp điểm, và đếm số miền: 1, 2, 4, 8, 16, rồi 31 thay vì 32. Bài C3 ở đó cho thấy số miền bằng 1, cộng số dây cung, cộng số giao điểm bên trong. Số dây là \(\binom n2\). Mỗi giao điểm bên trong là chỗ hai dây cắt nhau, và hai dây cắt nhau bên trong đường tròn đúng khi bốn đầu mút của chúng xen kẽ nhau: chúng là hai đường chéo của một tứ giác có bốn đỉnh trên đường tròn. Mỗi cách chọn 4 điểm cho đúng một tứ giác, tức đúng một giao điểm, nên có \(\binom n4\) giao điểm. Vậy số miền là

\[ 1 + \binom n2 + \binom n4, \]

cho lần lượt \(1, 2, 4, 8, 16, 31, 57\) với \(n = 1, \dots, 7\). Chương 1 hẹn Phần V sẽ dạy cách đếm những lựa chọn "4 trong \(n\) điểm"; đây là lời giải ấy, và bài C3 cho thấy chính xác vì sao mẫu hình \(2^{n - 1}\) phải hỏng ở \(n = 6\).

Bên trái: 6 điểm, 15 dây, 15 giao điểm, 31 miền. Bên phải: mỗi giao điểm bên trong là chỗ hai đường chéo của một tứ giác cắt nhau, nên ứng với đúng một cách chọn 4 trong 6 điểm.

Ranh giới

Đếm trùng. Chọn 2 người trong 5 bằng phép tính \(5 \cdot 4 = 20\) là sai, vì mỗi cặp bị đếm hai lần, theo hai thứ tự. Lỗi đếm trùng rất khó thấy khi mỗi thứ bị đếm một số lần khác nhau; khi ấy không chia đơn giản được, và phải chia trường hợp.

Thứ tự có quan trọng không, và có được lặp lại không. Một mã PIN 4 chữ số là một dãy có thứ tự, và các chữ số được lặp lại: có \(10^4 = 10.000\) mã. Nếu bốn chữ số phải khác nhau, có \(10 \cdot 9 \cdot 8 \cdot 7 = 5040\) mã. Nếu chỉ quan tâm tập hợp bốn chữ số khác nhau, không kể thứ tự, có \(\binom{10}{4} = 210\). Ba câu hỏi nghe gần giống nhau cho ba đáp số khác hẳn. Tiếng Anh gọi ổ khóa số là "combination lock", nhưng với ổ khóa, thứ tự các số lại rất quan trọng: đúng ra nó mở bằng một dãy có thứ tự, không phải bằng một tổ hợp.

Các khả năng chưa chắc đã ngang nhau. Tung hai con xúc xắc, tổng hai mặt có 11 giá trị, từ 2 tới 12, nhưng tổng 7 xảy ra theo 6 cách còn tổng 2 chỉ theo 1 cách trong 36 cặp. Đếm số giá trị có thể của tổng khác với đếm số khả năng ngang nhau. Chương sau sẽ cần phân biệt rõ hai việc này.

Số lượng vượt xa trực giác. \(52!\), khoảng \(8{,}07 \times 10^{67}\), lớn tới mức một bộ bài được tráo kỹ hầu như chắc chắn đang ở một thứ tự chưa từng có ai tráo ra. Tổ hợp tăng rất nhanh: \(\binom{50}{25}\) đã vượt \(10^{14}\). Trực giác được luyện trên những con số nhỏ, và các bài toán đếm là nơi nó sai nhiều nhất.

Phát biểu chặt chẽ

Với một tập hữu hạn \(S\), viết \(\lvert S \rvert\) cho số phần tử của nó.

Định lý 1 (quy tắc cộng). Nếu \(A\) và \(B\) là hai tập hữu hạn không có phần tử chung thì \(\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert\). Tổng quát, số phần tử của hợp của nhiều tập hữu hạn đôi một rời nhau bằng tổng số phần tử của chúng.

Định lý này là cách nói chính xác của việc đếm tiếp: đếm hết \(A\) rồi đếm tiếp sang \(B\). Ta nhận nó như một nguyên lý nền.

Định lý 2 (quy tắc nhân). Giả sử mỗi đối tượng trong một tập \(S\) được xác định bởi một dãy \(k\) lựa chọn, sao cho hai dãy khác nhau cho hai đối tượng khác nhau, và dù các lựa chọn trước là gì, lựa chọn thứ \(i\) luôn có đúng \(n_i\) khả năng. Khi đó \(\lvert S \rvert = n_1 n_2 \cdots n_k\). Riêng với tích Descartes, \(\lvert A \times B \rvert = \lvert A \rvert \cdot \lvert B \rvert\).

Chứng minh. Quy nạp theo \(k\) (Chương 18). Với \(k = 1\), hiển nhiên. Giả sử đúng với \(k\) lựa chọn. Với \(k + 1\) lựa chọn, chia \(S\) theo lựa chọn đầu tiên thành \(n_1\) phần đôi một rời nhau. Trong mỗi phần, lựa chọn đầu đã cố định, và các đối tượng được xác định bởi \(k\) lựa chọn còn lại, với \(n_2, \dots, n_{k+1}\) khả năng; theo giả thiết quy nạp, mỗi phần có \(n_2 \cdots n_{k+1}\) đối tượng. Theo quy tắc cộng, \(\lvert S \rvert = n_1 \cdot n_2 \cdots n_{k+1}\). \(\square\)

Hệ quả 3. Có \(n!\) hoán vị của \(n\) đối tượng, và \(\frac{n!}{(n - k)!}\) chỉnh hợp chập \(k\) của \(n\) với \(0 \leq k \leq n\).

Chứng minh. Một chỉnh hợp là một dãy \(k\) lựa chọn: đối tượng ở vị trí thứ \(i\) được chọn trong \(n - i + 1\) đối tượng chưa dùng, bất kể \(i - 1\) đối tượng trước là gì. Quy tắc nhân cho \(n(n - 1) \cdots (n - k + 1) = \frac{n!}{(n - k)!}\). Với \(k = n\), được \(n!\). \(\square\)

Định lý 4 (số tổ hợp). Với \(0 \leq k \leq n\), số tập con \(k\) phần tử của một tập \(n\) phần tử là \(\binom nk = \frac{n!}{k!\,(n - k)!}\).

Chứng minh. Đếm số chỉnh hợp chập \(k\) của \(n\) theo hai cách. Cách thứ nhất, theo Hệ quả 3: \(\frac{n!}{(n - k)!}\). Cách thứ hai: mỗi chỉnh hợp được tạo bằng cách chọn trước tập \(k\) đối tượng, có \(\binom nk\) cách, rồi xếp chúng theo một thứ tự, có \(k!\) cách; theo quy tắc nhân, có \(\binom nk \cdot k!\) chỉnh hợp. Hai cách đếm cùng một tập, nên \(\binom nk \cdot k! = \frac{n!}{(n - k)!}\), và chia hai vế cho \(k!\) được công thức. \(\square\)

Đây là kỹ thuật "đếm một thứ theo hai cách" mà Chương 1 đã dùng để chứng minh bổ đề bắt tay và hẹn sẽ trở lại. Việc chia cho \(k!\) là hành động đồng nhất của Chương 3: ta gom các chỉnh hợp có cùng tập đối tượng thành một lớp, mỗi lớp có đúng \(k!\) phần tử, và đếm số lớp.

Định lý 5 (đẳng thức Pascal). Với \(1 \leq k \leq n - 1\), \(\binom nk = \binom{n - 1}{k - 1} + \binom{n - 1}{k}\).

Chứng minh. Trong một tập \(n\) phần tử, đánh dấu một phần tử \(a\). Các tập con \(k\) phần tử chia thành hai loại rời nhau. Loại chứa \(a\): bỏ \(a\) đi, còn một tập con \(k - 1\) phần tử của \(n - 1\) phần tử kia, và ngược lại; có \(\binom{n - 1}{k - 1}\) tập loại này. Loại không chứa \(a\): một tập con \(k\) phần tử của \(n - 1\) phần tử kia; có \(\binom{n - 1}{k}\) tập. Theo quy tắc cộng, có đẳng thức. \(\square\)

Định lý 6 (nhị thức Newton). Với mọi số \(x\), \(y\) và số tự nhiên \(n\),

\[ (x + y)^n = \sum_{k=0}^{n} \binom nk x^k y^{n - k}. \]

Chứng minh. \((x + y)^n\) là tích của \(n\) thừa số \(x + y\). Khai triển theo tính phân phối, ta được một tổng gồm các tích, mỗi tích chọn \(x\) hoặc \(y\) từ mỗi thừa số. Một tích chọn \(x\) từ đúng \(k\) thừa số bằng \(x^k y^{n - k}\), và số tích như thế bằng số cách chọn \(k\) thừa số trong \(n\), tức \(\binom nk\). Gom các tích bằng nhau lại được công thức. \(\square\)

Mệnh đề 7 (sao và vạch). Với các số nguyên dương \(m\) và số tự nhiên \(n\), số nghiệm nguyên không âm của \(x_1 + x_2 + \dots + x_m = n\) là \(\binom{n + m - 1}{m - 1}\).

Chứng minh. Cho mỗi nghiệm ứng với một hàng gồm \(x_1\) sao, một vạch, \(x_2\) sao, một vạch, ..., \(x_m\) sao: tổng cộng \(n\) sao và \(m - 1\) vạch. Ngược lại, mỗi hàng \(n\) sao và \(m - 1\) vạch cho đúng một nghiệm, đọc số sao giữa các vạch. Tương ứng này là một song ánh (Chương 20), nên hai tập có cùng số phần tử. Một hàng được xác định khi biết \(m - 1\) vị trí nào trong \(n + m - 1\) vị trí là vạch, nên có \(\binom{n + m - 1}{m - 1}\) hàng. \(\square\)

Sợi chỉ

• S1. Bất biến qua biến đổi. Một nhóm \(k\) người vẫn là nhóm ấy dù ta xếp họ theo thứ tự nào: nhóm là cái bất biến khi hoán vị các thành viên. Đếm các cái bất biến ấy bằng cách đếm tất cả rồi chia cho số biến đổi, \(k!\), là hành động đồng nhất của Chương 3. Xếp 5 người quanh một bàn tròn, coi các cách xoay là như nhau, cũng thế: \(\frac{5!}{5} = 24\) (bài B2).
• S6. Biểu diễn khác nhau của cùng một cấu trúc. Cùng một số \(\binom nk\) là số tập con \(k\) phần tử, số đường đi trên lưới, hệ số trong khai triển nhị thức, một ô trong tam giác Pascal, và qua sao và vạch, số cách chia kẹo. Mỗi cách nhìn làm một tính chất trở nên hiển nhiên: \(\binom nk = \binom{n}{n - k}\) hiển nhiên khi nghĩ tới tập con và phần bù của nó; đẳng thức Pascal hiển nhiên trên lưới.
• S3. Thứ tự của biến đổi. Câu hỏi "thứ tự có quan trọng không" tách chỉnh hợp khỏi tổ hợp, mã PIN khỏi một nhóm người; nó quyết định có chia cho \(k!\) hay không, và đáp số có thể chênh nhau hàng chục lần.

Tóm tắt

• Đếm không cần liệt kê: nhìn vào cách các khả năng được tạo ra. Quy tắc nhân cho các lựa chọn nối tiếp, quy tắc cộng cho các trường hợp loại trừ nhau.
• \(n!\) hoán vị, \(\frac{n!}{(n - k)!}\) chỉnh hợp, \(\binom nk = \frac{n!}{k!\,(n - k)!}\) tổ hợp.
• Chia cho \(k!\) vì mỗi nhóm \(k\) đối tượng ứng với \(k!\) thứ tự: đếm tất cả rồi đồng nhất các thứ tự.
• Đếm một thứ theo hai cách cho công thức tổ hợp; đếm phần bù khi đếm cái không muốn dễ hơn.
• Tam giác Pascal: \(\binom nk = \binom{n - 1}{k - 1} + \binom{n - 1}{k}\); các hàng là hệ số của nhị thức Newton, và tổng hàng thứ \(n\) là \(2^n\).
• Sao và vạch: chia \(n\) vật giống nhau cho \(m\) người theo \(\binom{n + m - 1}{m - 1}\) cách.
• Cùng một câu hỏi, thay đổi "có kể thứ tự không" hay "có được lặp lại không" cho đáp số khác hẳn; và số lượng khả năng tăng nhanh hơn trực giác rất nhiều.

Bài tập

A. Tư duy

A1. Trong các việc sau, thứ tự có quan trọng không, và các lựa chọn có được lặp lại không? (a) Đặt một mật khẩu 6 ký tự. (b) Chọn 3 người đi dự hội nghị. (c) Xếp lịch trực cho 3 người vào thứ Hai, thứ Ba, thứ Tư. (d) Mua 5 que kem từ 3 vị.

Lời giải

(a) Có thứ tự, được lặp: mỗi vị trí chọn độc lập, quy tắc nhân. (b) Không kể thứ tự, không lặp: một tổ hợp. (c) Có thứ tự, không lặp: mỗi người một ngày, một chỉnh hợp (hay hoán vị nếu đúng 3 người cho 3 ngày). (d) Không kể thứ tự, được lặp: chỉ quan tâm mỗi vị bao nhiêu que, tức chia 5 que cho 3 vị, sao và vạch cho \(\binom{7}{2} = 21\) cách.

A2. Vì sao \(\binom nk = \binom{n}{n - k}\), mà không cần tính?

Lời giải

Chọn \(k\) người để mời cũng là chọn \(n - k\) người không mời: mỗi tập con \(k\) phần tử ứng với đúng một tập con \(n - k\) phần tử, là phần bù của nó, và ngược lại. Tương ứng ấy là một song ánh, nên hai số bằng nhau. Công thức \(\frac{n!}{k!\,(n - k)!}\) chỉ xác nhận lại điều này bằng đại số: đổi vai \(k\) và \(n - k\) không làm đổi mẫu số.

A3. Quy ước \(0! = 1\) có vẻ lạ. Hãy kiểm tra rằng nó làm cho \(\binom n0\) và \(\binom nn\) đúng nghĩa, và giải thích nghĩa của \(0!\) như một số cách xếp.

Lời giải

Có đúng một tập con 0 phần tử (tập rỗng) và đúng một tập con \(n\) phần tử (cả tập), nên \(\binom n0 = \binom nn = 1\). Công thức cho \(\frac{n!}{0!\,n!}\), bằng 1 đúng khi \(0! = 1\). Về nghĩa, \(0!\) là số cách xếp 0 đối tượng thành hàng: có đúng một cách, là không xếp gì. Quy ước này không phải chọn tùy tiện: nó là giá trị duy nhất giữ được cả công thức lẫn nghĩa đếm, như \(0! = 1\) ở định nghĩa đệ quy của Chương 18.

B. Tính toán

B1. Có bao nhiêu biển số theo kiểu ở Ví dụ 1 mà cả 4 chữ số khác nhau? Có bao nhiêu biển mà hai chữ cái giống nhau?

Lời giải

Bốn chữ số khác nhau: \(26^2 \cdot 10 \cdot 9 \cdot 8 \cdot 7 = 676 \cdot 5040 = 3.407.040\). Hai chữ cái giống nhau: chữ cái có 26 cách, rồi \(10^4\) cách cho các chữ số, tổng \(260.000\).

B2. Có bao nhiêu cách xếp 5 người ngồi quanh một bàn tròn, nếu hai cách xếp chỉ khác nhau một phép xoay được coi là như nhau?

Lời giải

Xếp thẳng hàng có \(5! = 120\) cách. Mỗi cách xếp quanh bàn ứng với đúng 5 cách xếp thẳng, cắt vòng tròn ở 5 chỗ khác nhau, nên có \(\frac{120}{5} = 24 = 4!\) cách. Cũng có thể cố định chỗ của một người, rồi xếp 4 người còn lại: \(4! = 24\).

B3. Có bao nhiêu tay bài 5 lá không có lá cơ nào? Có đúng một lá cơ?

Lời giải

Bộ bài có 13 lá cơ và 39 lá khác. Không có lá cơ: \(\binom{39}{5} = 575.757\). Đúng một lá cơ: chọn lá cơ có 13 cách, chọn 4 lá khác có \(\binom{39}{4} = 82.251\) cách, tổng \(13 \cdot 82.251 = 1.069.263\).

B4. Có bao nhiêu đường đi ngắn nhất trên lưới 5 ô ngang, 5 ô dọc, từ góc dưới trái tới góc trên phải? Bao nhiêu đường trong số ấy đi qua nút cách góc xuất phát 2 ô ngang và 3 ô dọc?

Lời giải

Mỗi đường có 10 bước, trong đó 5 bước lên: \(\binom{10}{5} = 252\) đường. Một đường qua nút ấy gồm hai đoạn chọn độc lập: đoạn đầu có 5 bước, 3 bước lên, \(\binom53 = 10\) cách; đoạn sau có 5 bước, 2 bước lên, \(\binom52 = 10\) cách. Theo quy tắc nhân, có \(10 \cdot 10 = 100\) đường.

B5. Khai triển \((x - 1)^4\), và tìm hệ số của \(x^2\) trong \((2x + 1)^4\).

Lời giải

Theo nhị thức Newton với \(y = -1\): \((x - 1)^4 = x^4 - 4x^3 + 6x^2 - 4x + 1\). Trong \((2x + 1)^4\), số hạng chứa \(x^2\) là \(\binom42 (2x)^2 \cdot 1^2 = 6 \cdot 4x^2\), nên hệ số là 24.

B6. Có bao nhiêu nghiệm nguyên dương của \(x + y + z = 10\)?

Lời giải

Đặt \(x = x' + 1\), \(y = y' + 1\), \(z = z' + 1\) với \(x', y', z' \geq 0\): được \(x' + y' + z' = 7\), có \(\binom{9}{2} = 36\) nghiệm theo sao và vạch. Cách khác: xếp 10 sao thành hàng, chọn 2 trong 9 khe giữa các sao để đặt vạch, sao cho mỗi đoạn có ít nhất một sao: \(\binom92 = 36\).

B7. Có bao nhiêu số có 5 chữ số lập được từ các chữ số \(1, 1, 2, 2, 3\) (dùng mỗi chữ số đúng một lần)?

Lời giải

Nếu hai chữ số 1 và hai chữ số 2 khác nhau, có \(5! = 120\) cách xếp. Đổi chỗ hai chữ số 1 không đổi số, đổi chỗ hai chữ số 2 cũng vậy; mỗi số bị đếm \(2! \cdot 2! = 4\) lần. Vậy có \(\frac{120}{4} = 30\) số.

B8. Dùng công thức của Ví dụ 7, tính số miền với \(n = 8\) và \(n = 10\) điểm trên đường tròn, và so với \(2^{n - 1}\).

Lời giải

\(n = 8\): \(1 + \binom82 + \binom84 = 1 + 28 + 70 = 99\), trong khi \(2^7 = 128\). \(n = 10\): \(1 + 45 + 210 = 256\), trong khi \(2^9 = 512\). Số miền tăng như một đa thức bậc 4 theo \(n\), còn \(2^{n - 1}\) tăng theo cấp số nhân, nên khoảng cách ngày càng lớn (Chương 29, Định lý 5).

C. Phản ví dụ và chứng minh

C1. Chứng minh \(\sum_{k=0}^{n} \binom nk = 2^n\) bằng cách đếm số tập con của một tập \(n\) phần tử theo hai cách.

Lời giải

Cách thứ nhất: mỗi tập con được xác định bởi \(n\) lựa chọn, mỗi phần tử "có mặt" hoặc "vắng mặt", nên theo quy tắc nhân có \(2^n\) tập con. Cách thứ hai: chia các tập con theo số phần tử \(k = 0, 1, \dots, n\); có \(\binom nk\) tập con \(k\) phần tử, và các loại rời nhau, nên theo quy tắc cộng có \(\sum_{k=0}^{n} \binom nk\) tập con. Hai cách đếm cùng một tập, nên hai kết quả bằng nhau. \(\square\) Đây cũng là nhị thức Newton với \(x = y = 1\).

C2. Chứng minh \(k\binom nk = n\binom{n - 1}{k - 1}\) với \(1 \leq k \leq n\), bằng cách đếm theo hai cách số cách chọn một ban \(k\) người trong \(n\) người và một trưởng ban trong ban ấy.

Lời giải

Cách thứ nhất: chọn ban trước, có \(\binom nk\) cách, rồi chọn trưởng ban trong \(k\) thành viên, có \(k\) cách: tổng \(k\binom nk\). Cách thứ hai: chọn trưởng ban trước trong \(n\) người, có \(n\) cách, rồi chọn \(k - 1\) thành viên còn lại trong \(n - 1\) người kia, có \(\binom{n - 1}{k - 1}\) cách: tổng \(n\binom{n - 1}{k - 1}\). Hai cách đếm cùng một tập các cặp (ban, trưởng ban), nên chúng bằng nhau. \(\square\)

C3. Dùng đẳng thức Pascal để chứng minh \(1 + \binom n2 + \binom n4 = \binom{n - 1}{0} + \binom{n - 1}{1} + \binom{n - 1}{2} + \binom{n - 1}{3} + \binom{n - 1}{4}\) với \(n \geq 5\). Suy ra số miền ở Ví dụ 7 bằng \(2^{n - 1}\) khi \(n \leq 5\) và nhỏ hơn \(2^{n - 1}\) khi \(n \geq 6\).

Lời giải

Theo Định lý 5, \(\binom n2 = \binom{n - 1}{1} + \binom{n - 1}{2}\) và \(\binom n4 = \binom{n - 1}{3} + \binom{n - 1}{4}\); còn \(1 = \binom{n - 1}{0}\). Cộng lại được đẳng thức. \(\square\) Theo bài C1 với \(n - 1\), tổng đầy đủ \(\sum_{k=0}^{n - 1} \binom{n - 1}{k} = 2^{n - 1}\). Vế phải chỉ gồm năm số hạng đầu, \(k = 0, \dots, 4\). Khi \(n - 1 \leq 4\), đó là toàn bộ tổng (với \(n \leq 4\), các \(\binom{n - 1}{k}\) với \(k > n - 1\) bằng 0), nên số miền bằng \(2^{n - 1}\): 1, 2, 4, 8, 16. Khi \(n \geq 6\), tổng thiếu ít nhất số hạng \(\binom{n - 1}{5} \geq 1\), nên số miền nhỏ hơn \(2^{n - 1}\): với \(n = 6\) thiếu đúng \(\binom55 = 1\), nên được 31. Mẫu hình của Chương 1 không trùng hợp ngẫu nhiên: năm số đầu trùng với \(2^{n - 1}\) vì năm số hạng đầu của một hàng Pascal lúc ấy là cả hàng.

Câu hỏi để ngỏ

Giờ ta đếm được các khả năng. Nếu mọi khả năng ngang nhau, thì "cơ hội" để điều ta quan tâm xảy ra là gì? Xác suất có phải chỉ là một tỉ số đếm?