Bài 23: Quy tắc đếm

Chương VIII: Đại số tổ hợp

Bài 23: Quy tắc đếm

Chương này cung cấp những kiến thức cơ bản về Đại số tổ hợp, bao gồm hai quy tắc đếm thường dùng là quy tắc cộng và quy tắc nhân; các khái niệm và công thức về hoán vị, chỉnh hợp, tổ hợp; công thức khai triển nhị thức Newton trong trường hợp số mũ thấp.

Sơ đồ cây các bước lựa chọn

Thuật ngữ

Quy tắc cộng
Quy tắc nhân
Sơ đồ hình cây

Kiến thức, kĩ năng

Vận dụng quy tắc cộng, quy tắc nhân để tính toán số cách thực hiện một công việc hoặc đếm số phần tử của một tập hợp.
Vận dụng sơ đồ hình cây trong các bài toán đếm đơn giản.

Đặt vấn đề: Bài toán mật khẩu trang web

Đếm là một bài toán cổ xưa nhất của nhân loại. Trong khoa học và trong cuộc sống, người ta cần đếm các đối tượng để giải quyết các vấn đề khác nhau. Chẳng hạn như bài toán sau:

Mỗi mật khẩu của một trang web là một dãy có từ 2 tới 3 kí tự, trong đó kí tự đầu tiên là một trong 26 chữ cái in thường trong bảng chữ cái tiếng Anh (từ a đến z), mỗi kí tự còn lại là một chữ số từ 0 đến 9. Hỏi có thể tạo được bao nhiêu mật khẩu khác nhau?

Bài học này sẽ giúp em hiểu và áp dụng hai quy tắc đếm cơ bản để giải quyết bài toán trên (xem chi tiết ở Ví dụ 5).

1 Quy tắc cộng và sơ đồ hình cây

HĐ1

Chọn chuyến đi

Từ Hà Nội vào Nghệ An mỗi ngày có 7 chuyến tàu hoả và 2 chuyến máy bay. Bạn An muốn ngày Chủ nhật này đi từ Hà Nội vào Nghệ An bằng tàu hoả hoặc máy bay. Hỏi bạn An có bao nhiêu cách chọn chuyến đi?

Hình 8.1: Các tuyến từ Hà Nội vào Nghệ An

Phân tích và trả lời:

Bạn An chỉ cần chọn một chuyến tàu hoả hoặc một chuyến máy bay để hoàn thành chuyến đi:

Phương án 1 (Đi bằng tàu hoả): có 7 cách chọn chuyến.
Phương án 2 (Đi bằng máy bay): có 2 cách chọn chuyến.

Vì hai phương án này hoàn toàn độc lập và không trùng lặp, bạn An có tổng cộng: \(7 + 2 = 9\) cách chọn chuyến đi.

HĐ2

Chọn vé tàu

Bạn An đã quyết định mua vé tàu đi từ ga Hà Nội vào ga Vinh trên chuyến tàu SE7. Trên tàu có các toa ghế ngồi và các toa giường nằm. Toa ngồi có hai loại vé: ngồi cứng và ngồi mềm. Toa nằm có loại khoang 4 giường và khoang 6 giường. Khoang 4 giường có hai loại vé: tầng 1 và tầng 2, khoang 6 giường có ba loại vé: tầng 1, tầng 2 và tầng 3. Hỏi:

a) Có bao nhiêu loại vé ghế ngồi và bao nhiêu loại vé giường nằm?

b) Có bao nhiêu loại vé để bạn An lựa chọn?

Trả lời:

a) Vé ghế ngồi có 2 loại (ngồi cứng, ngồi mềm).
Vé giường nằm gồm: khoang 4 giường có 2 loại (tầng 1, 2) và khoang 6 giường có 3 loại (tầng 1, 2, 3). Do đó số loại vé giường nằm là: \(2 + 3 = 5\) (loại vé).

b) Vì An chỉ chọn mua một vé (ghế ngồi hoặc giường nằm), nên số loại vé để An lựa chọn là: \(2 + 5 = 7\) (loại vé).

Hình 8.2: Sơ đồ hình cây chọn vé tàu SE7

Quy tắc cộng

Giả sử một công việc có thể thực hiện theo một trong hai phương án khác nhau:

Phương án một có \(n_1\) cách thực hiện,
Phương án hai có \(n_2\) cách thực hiện (không trùng với bất kì cách thực hiện nào của phương án một).

Khi đó số cách thực hiện công việc sẽ là: \(n_1 + n_2\) cách.

Chú ý: Sơ đồ hình cây

Sơ đồ minh hoạ cách phân chia trường hợp như trong Hình 8.2 được gọi là sơ đồ hình cây. Trong các bài toán đếm, người ta thường dùng sơ đồ hình cây để minh hoạ, giúp cho việc đếm thuận tiện và không bỏ sót trường hợp.

Ví dụ 1

Chọn món ăn sáng

Một quán phục vụ ăn sáng có bán phở và bún. Phở có 2 loại là phở bò và phở gà. Bún có 3 loại là bún bò, bún riêu cua và bún cá. Một khách hàng muốn chọn một món để ăn sáng. Vẽ sơ đồ hình cây minh hoạ và cho biết khách hàng đó có bao nhiêu cách lựa chọn một món ăn sáng.

Giải:

Ta có sơ đồ hình cây minh hoạ như Hình 8.3.

Vì khách hàng chỉ chọn ăn một món (hoặc phở, hoặc bún), theo quy tắc cộng, số cách chọn một món ăn sáng là:

\(2 + 3 = 5\text{ (cách)}\)

Hình 8.3: Sơ đồ hình cây chọn món ăn sáng

Chú ý quan trọng

Ta áp dụng quy tắc cộng cho một công việc có nhiều phương án khi các phương án đó phải rời nhau, không phụ thuộc vào nhau (độc lập với nhau). Nếu hai phương án có phần tử trùng nhau, việc cộng trực tiếp sẽ dẫn đến sai số (phần tử chung bị đếm lặp 2 lần).

Ví dụ 2

Đếm quân cờ vua

Một bộ cờ vua có 32 quân cờ như Hình 8.4 (gồm 16 quân trắng và 16 quân đen; mỗi bên gồm 8 quân tốt, 2 xe, 2 mã, 2 tượng, 1 vua, 1 hậu).

a) Bạn Nam lấy ra tất cả các quân tốt. Hãy đếm xem Nam lấy ra bao nhiêu quân cờ.

b) Bạn Nam lấy ra tất cả các quân cờ trắng và tất cả các quân tốt. Hãy đếm số quân cờ Nam lấy ra.

Giải:

a) Quân cờ bạn Nam lấy ra có thể thuộc hai loại: màu trắng hoặc màu đen.

Số quân tốt trắng: 8 quân;
Số quân tốt đen: 8 quân.

Vì hai loại quân cờ này rời nhau nên theo quy tắc cộng, số quân cờ Nam lấy ra là: \(8 + 8 = 16\) (quân cờ).

b) Nam lấy tất cả các quân trắng và tất cả các quân tốt:

Đầu tiên ta đếm tất cả các quân cờ trắng, có 16 quân;
Tiếp theo ta đếm tất cả các quân tốt, có 16 quân tốt.

Vì trong 16 quân tốt có 8 quân tốt trắng đã được đếm ở lượt trước (bị đếm lặp 2 lần), nên số quân cờ thực tế Nam lấy ra là:

\(16 + 16 - 8 = 24\text{ (quân cờ)}\)

Nhận xét: Mối liên hệ với tập hợp và sơ đồ Venn

Ở câu b) Ví dụ 2, nếu gọi \(A\) là tập hợp gồm tất cả các quân cờ trắng, \(B\) là tập hợp gồm tất cả các quân tốt thì các quân cờ Nam lấy ra chính là các phần tử của tập hợp \(A \cup B\).

Nếu ta áp dụng quy tắc cộng: \(n(A \cup B) = n(A) + n(B) = 16 + 16 = 32\) (quân cờ), suy ra Nam lấy ra 32 quân cờ. Kết luận khi đó là SAI, vì \(A \cap B \neq \varnothing\) (giao của hai tập hợp chính là 8 quân tốt trắng). Do đó ta không thể áp dụng quy tắc cộng thông thường.

Công thức tổng quát cho hai tập hợp bất kì: \[n(A \cup B) = n(A) + n(B) - n(A \cap B)\]

Luyện tập 1

Số không nguyên tố cùng nhau

Có bao nhiêu số tự nhiên từ 1 đến 30 mà không nguyên tố cùng nhau với 35?

Nhắc lại: Hai số tự nhiên \(a\) và \(b\) gọi là nguyên tố cùng nhau nếu chúng có ước chung lớn nhất là 1 (\(\gcd(a, b) = 1\)).

Xem lời giải chi tiết

Ta có phân tích thừa số nguyên tố: \(35 = 5 \times 7\).

Do đó, một số tự nhiên \(x\) không nguyên tố cùng nhau với 35 khi và chỉ khi \(x\) chia hết cho 5 hoặc \(x\) chia hết cho 7 (nghĩa là có ước chung lớn hơn 1 với 35).

Gọi \(A\) là tập hợp các số từ 1 đến 30 chia hết cho 5: \[A = \{5, 10, 15, 20, 25, 30\} \implies n(A) = 6\]
Gọi \(B\) là tập hợp các số từ 1 đến 30 chia hết cho 7: \[B = \{7, 14, 21, 28\} \implies n(B) = 4\]
Tập hợp các số từ 1 đến 30 chia hết cho cả 5 và 7 (tức chia hết cho 35) là: \[A \cap B = \varnothing \implies n(A \cap B) = 0\]

Vì \(A \cap B = \varnothing\), theo quy tắc cộng, số các số tự nhiên từ 1 đến 30 không nguyên tố cùng nhau với 35 là:

\(n(A \cup B) = n(A) + n(B) = 6 + 4 = 10\text{ (số)}\)

Các số đó cụ thể là: 5, 7, 10, 14, 15, 20, 21, 25, 28, 30.

2 Quy tắc nhân

HĐ3

Chọn phương tiện di chuyển nối tiếp

Thầy Trung muốn đi từ Hà Nội vào Huế, rồi từ Huế vào thành phố Đà Nẵng. Biết rằng từ Hà Nội vào Huế có thể đi bằng 3 cách: ô tô, tàu hoả hoặc máy bay. Còn từ Huế vào thành phố Đà Nẵng có thể đi bằng 2 cách: ô tô hoặc tàu hoả (Hình 8.5). Hỏi thầy Trung có bao nhiêu cách chọn các phương tiện để đi từ Hà Nội vào thành phố Đà Nẵng?

Hình 8.5: Tuyến Hà Nội -> Huế -> Thành phố Đà Nẵng

Phân tích và trả lời:

Để hoàn thành chuyến đi từ Hà Nội đến Đà Nẵng, thầy Trung phải thực hiện hai công đoạn liên tiếp:

Công đoạn 1 (Đi từ Hà Nội vào Huế): có 3 cách chọn phương tiện (ô tô, tàu hoả, máy bay).
Công đoạn 2 (Đi từ Huế vào Đà Nẵng): ứng với mỗi cách chọn phương tiện ở chặng đầu, thầy Trung đều có 2 cách chọn phương tiện ở chặng tiếp theo (ô tô hoặc tàu hoả).

Tổng số cách chọn các phương tiện để đi từ Hà Nội vào thành phố Đà Nẵng là: \(3 \times 2 = 6\) cách.

HĐ4

Gắn nhãn ghế phòng chiếu phim

Để lắp ghế vào một phòng chiếu phim, các ghế được gắn nhãn bằng một chữ cái in hoa (trong bảng 26 chữ cái tiếng Anh từ A đến Z) đứng trước và một số nguyên từ 1 đến 20, chẳng hạn X15, Z2, ... Hỏi có thể gắn nhãn tối đa được cho bao nhiêu ghế?

Trả lời:

Mỗi nhãn ghế được tạo thành qua hai công đoạn liên tiếp:

Công đoạn 1: Chọn một chữ cái in hoa từ 26 chữ cái tiếng Anh \(\implies 26\) cách.
Công đoạn 2: Chọn một số nguyên từ 1 đến 20 \(\implies 20\) cách.

Theo quy tắc nhân, số nhãn ghế tối đa có thể gắn là: \(26 \times 20 = 520\) (nhãn ghế), tương ứng với tối đa 520 chiếc ghế.

Quy tắc nhân

Giả sử một công việc phải hoàn thành qua hai công đoạn liên tiếp nhau:

Công đoạn một có \(m_1\) cách thực hiện,
Với mỗi cách thực hiện công đoạn một, có \(m_2\) cách thực hiện công đoạn hai.

Khi đó số cách thực hiện công việc là: \(m_1 \cdot m_2\) cách.

Chú ý

Quy tắc nhân áp dụng để tính số cách thực hiện một công việc có nhiều công đoạn, các công đoạn nối tiếp nhau và những công đoạn này độc lập với nhau. Nếu công việc có \(k\) công đoạn liên tiếp với số cách thực hiện tương ứng là \(m_1, m_2, \dots, m_k\) thì tổng số cách là: \(m_1 \cdot m_2 \cdots m_k\) cách.

Ví dụ 3

Mua vé tàu ngồi đi Vinh

Một người muốn mua vé tàu ngồi đi từ ga Hà Nội vào ga Vinh. Có ba chuyến tàu là SE5, SE7 và SE35. Trên mỗi tàu có 2 loại vé ngồi khác nhau: ngồi cứng hoặc ngồi mềm. Hỏi có bao nhiêu loại vé ngồi khác nhau để người đó lựa chọn?

Giải:

Để mua được vé tàu, người đó phải thực hiện hai công đoạn liên tiếp:

Chọn chuyến tàu Chọn loại vé

Có 3 cách chọn chuyến tàu, với mỗi chuyến tàu có 2 cách chọn loại vé ngồi. Áp dụng quy tắc nhân, ta có số cách chọn loại vé là:

\(3 \cdot 2 = 6\text{ (cách)}\)

Chú ý (Cách tiếp cận theo Quy tắc cộng):

Ta cũng có thể dùng quy tắc cộng bằng cách chia 3 phương án tương ứng với 3 chuyến tàu: chuyến SE5 có 2 loại vé, chuyến SE7 có 2 loại vé, chuyến SE35 có 2 loại vé. Tổng số loại vé là: \(2 + 2 + 2 = 6\) (loại vé).

Sơ đồ quy trình và sơ đồ hình cây chọn vé tàu

Luyện tập 2

Tính số trận đấu vòng bảng World Cup

Tại kì World Cup năm 2018, vòng bảng gồm có 32 đội tham gia, được chia vào 8 bảng, mỗi bảng 4 đội thi đấu vòng tròn (mỗi đội chơi một trận với từng đội khác trong cùng bảng). Hỏi tổng cộng vòng bảng có bao nhiêu trận đấu?

Xem lời giải chi tiết

Trước hết ta tính số trận đấu trong một bảng đấu gồm 4 đội (giả sử là các đội A, B, C, D):

Đội A đấu với 3 đội còn lại (B, C, D) \(\implies 3\) trận đấu;
Đội B đấu với 2 đội còn lại (C, D) chưa đấu \(\implies 2\) trận đấu;
Đội C đấu với đội D \(\implies 1\) trận đấu.

Như vậy, trong mỗi bảng có tổng cộng: \(3 + 2 + 1 = 6\) trận đấu (hoặc tính theo số cặp: \(\frac{4 \times 3}{2} = 6\) trận đấu).

Vì có 8 bảng đấu độc lập diễn ra tương tự nhau, theo quy tắc nhân, tổng số trận đấu ở toàn bộ vòng bảng là:

\(8 \times 6 = 48\text{ (trận đấu)}\)

3 Kết hợp quy tắc cộng và quy tắc nhân

Trong các ví dụ trước, chúng ta chỉ cần áp dụng một quy tắc đếm. Tuy nhiên, hầu hết các bài toán đếm trong thực tế sẽ phức tạp hơn và thường phải áp dụng cả hai quy tắc.

Ví dụ 4

Thiết kế thực đơn bữa tiệc

Để tổ chức bữa tiệc, người ta chọn thực đơn gồm một món khai vị, một món chính và một món tráng miệng. Nhà hàng đưa ra danh sách: khai vị có 2 loại súp và 3 loại sa lát; món chính có 4 loại thịt, 3 loại cá và 3 loại tôm; tráng miệng có 5 loại kem và 3 loại bánh. Hỏi có thể thiết kế bao nhiêu thực đơn khác nhau?

Giải:

Để chọn thực đơn, ta chia thành 3 công đoạn chọn món liên tiếp:

Công đoạn 1 (Chọn món khai vị): Vì có hai phương án là súp (2 loại) hoặc sa lát (3 loại) nên theo quy tắc cộng có: \(2 + 3 = 5\) (cách).
Công đoạn 2 (Chọn món chính): Tương tự, chọn một trong ba loại thịt (4), cá (3), tôm (3) nên theo quy tắc cộng có: \(4 + 3 + 3 = 10\) (cách).
Công đoạn 3 (Chọn món tráng miệng): Chọn một loại kem (5) hoặc bánh (3) nên theo quy tắc cộng có: \(5 + 3 = 8\) (cách).

Tổng kết, theo quy tắc nhân, số cách chọn thực đơn là:

\(5 \cdot 10 \cdot 8 = 400\text{ (cách)}\)

Quy trình chọn món

Chọn món khai vị (5 cách)

Chọn món chính (10 cách)

Chọn món tráng miệng (8 cách)

Khi nào dùng Quy tắc cộng?

Quy tắc cộng được áp dụng khi công việc được chia thành các phương án phân biệt rời nhau. Học sinh chỉ cần thực hiện một trong các phương án là đã hoàn thành công việc.

Khi nào dùng Quy tắc nhân?

Quy tắc nhân được áp dụng khi công việc có nhiều công đoạn nối tiếp nhau. Học sinh phải thực hiện tất cả các công đoạn thì công việc mới hoàn thành.

Luyện tập 3

Lập số tự nhiên từ các chữ số

Từ các chữ số 0, 1, 2, 3 có thể lập được bao nhiêu số thoả mãn:

a) Là số tự nhiên có ba chữ số khác nhau?
b) Là số tự nhiên chẵn có ba chữ số khác nhau?

Xem lời giải chi tiết

Gọi số tự nhiên có ba chữ số cần lập là \(\overline{abc}\), với \(a, b, c \in \{0, 1, 2, 3\}\) và \(a \neq 0\).

a) Số tự nhiên có ba chữ số khác nhau:

Chọn chữ số \(a\): Vì \(a \neq 0\) nên \(a \in \{1, 2, 3\} \implies 3\) cách chọn.
Chọn chữ số \(b\): Chữ số \(b \in \{0, 1, 2, 3\} \setminus \{a\} \implies 3\) cách chọn.
Chọn chữ số \(c\): Chữ số \(c \in \{0, 1, 2, 3\} \setminus \{a, b\} \implies 2\) cách chọn.

Theo quy tắc nhân, số các số tự nhiên có ba chữ số khác nhau là:

\(3 \times 3 \times 2 = 18\text{ (số)}\)

b) Số tự nhiên chẵn có ba chữ số khác nhau:

Vì số cần lập là số chẵn nên chữ số hàng đơn vị \(c \in \{0, 2\}\). Ta xét hai trường hợp:

Trường hợp 1 (\(c = 0\)):
- Chữ số \(a \in \{1, 2, 3\} \implies 3\) cách chọn.
- Chữ số \(b \in \{1, 2, 3\} \setminus \{a\} \implies 2\) cách chọn.
Số các số ở trường hợp này là: \(3 \times 2 = 6\) (số).
Trường hợp 2 (\(c = 2\)):
- Chữ số \(a \in \{1, 3\}\) (do \(a \neq 0\) và \(a \neq c\)) \(\implies 2\) cách chọn.
- Chữ số \(b \in \{0, 1, 3\} \setminus \{a\} \implies 2\) cách chọn.
Số các số ở trường hợp này là: \(2 \times 2 = 4\) (số).

Vì hai trường hợp rời nhau, theo quy tắc cộng số các số chẵn thoả mãn là:

\(6 + 4 = 10\text{ (số)}\)

Ví dụ 5

Giải quyết bài toán mở đầu (Tạo mật khẩu)

Trở lại tình huống mở đầu, ta thấy có hai trường hợp: độ dài của mật khẩu là 2 hoặc 3 kí tự.

Giải:

Trường hợp 1: Độ dài mật khẩu là 2 kí tự. Chọn từng kí tự và áp dụng quy tắc nhân:
- Kí tự đầu tiên có 26 cách chọn trong các chữ cái in thường tiếng Anh.
- Kí tự thứ hai có 10 cách chọn trong các chữ số từ 0 đến 9.
Vậy theo quy tắc nhân, ta có: \(26 \cdot 10 = 260\) cách chọn mật khẩu trong trường hợp 1.
Trường hợp 2: Độ dài mật khẩu là 3 kí tự.
- Kí tự đầu tiên có 26 cách chọn.
- Mỗi kí tự thứ hai và thứ ba đều có 10 cách chọn.
Tương tự như trường hợp 1, theo quy tắc nhân ta có: \(26 \cdot 10^2 = 2\,600\) cách chọn mật khẩu.

Vì có hai trường hợp rời nhau, mật khẩu có thể rơi vào một trong hai trường hợp, nên ta áp dụng quy tắc cộng. Tổng số mật khẩu có thể tạo ra là:

\(260 + 2\,600 = 2\,860\text{ (mật khẩu)}\)

Vận dụng

Thành lập đội cờ đỏ khối 10

Khối lớp 10 của một trường trung học phổ thông có ba lớp 10A, 10B, 10C. Lớp 10A có 30 bạn, lớp 10B có 35 bạn, lớp 10C có 32 bạn. Nhà trường muốn chọn 4 bạn để thành lập đội cờ đỏ của khối sao cho có đủ đại diện của các lớp. Hỏi có bao nhiêu cách lựa chọn?

Xem lời giải chi tiết

Để chọn 4 bạn sao cho có đủ đại diện của cả ba lớp (10A, 10B, 10C), sẽ có đúng một lớp có 2 bạn và hai lớp còn lại mỗi lớp có 1 bạn. Do đó, ta có 3 phương án lựa chọn rời nhau:

Phương án 1: Lớp 10A có 2 bạn, lớp 10B có 1 bạn, lớp 10C có 1 bạn:
- Số cách chọn 2 bạn từ 30 bạn lớp 10A là: \(\frac{30 \times 29}{2} = 435\) cách.
- Số cách chọn 1 bạn từ 35 bạn lớp 10B là: 35 cách.
- Số cách chọn 1 bạn từ 32 bạn lớp 10C là: 32 cách.
\(\implies\) Số cách chọn ở phương án 1 là: \(435 \times 35 \times 32 = 487\,200\) cách.
Phương án 2: Lớp 10A có 1 bạn, lớp 10B có 2 bạn, lớp 10C có 1 bạn:
- Số cách chọn 1 bạn từ 30 bạn lớp 10A là: 30 cách.
- Số cách chọn 2 bạn từ 35 bạn lớp 10B là: \(\frac{35 \times 34}{2} = 595\) cách.
- Số cách chọn 1 bạn từ 32 bạn lớp 10C là: 32 cách.
\(\implies\) Số cách chọn ở phương án 2 là: \(30 \times 595 \times 32 = 571\,200\) cách.
Phương án 3: Lớp 10A có 1 bạn, lớp 10B có 1 bạn, lớp 10C có 2 bạn:
- Số cách chọn 1 bạn từ 30 bạn lớp 10A là: 30 cách.
- Số cách chọn 1 bạn từ 35 bạn lớp 10B là: 35 cách.
- Số cách chọn 2 bạn từ 32 bạn lớp 10C là: \(\frac{32 \times 31}{2} = 496\) cách.
\(\implies\) Số cách chọn ở phương án 3 là: \(30 \times 35 \times 496 = 520\,800\) cách.

Áp dụng quy tắc cộng cho 3 phương án độc lập trên, tổng số cách lựa chọn là:

\(487\,200 + 571\,200 + 520\,800 = 1\,579\,200\text{ (cách)}\)