Chương 5: Đại số Tổ hợp

1. Quy tắc cộng và Quy tắc nhân

1.1 Quy tắc cộng

Định nghĩa: Nếu một công việc có thể thực hiện bằng một trong hai cách: cách thứ nhất có $m$ phương án, cách thứ hai có $n$ phương án (hai cách không đồng thời), thì số cách thực hiện công việc là $m + n$.

Ví dụ 1: Nếu muốn đi từ Hà Nội đến TP.HCM bằng máy bay hoặc tàu hỏa:

• Có 5 chuyến bay
• Có 3 chuyến tàu

→ Số cách đi = $5 + 3 = 8$ cách

1.2 Quy tắc nhân

Định nghĩa: Nếu một công việc gồm hai giai đoạn liên tiếp: giai đoạn 1 có $m$ phương án, giai đoạn 2 có $n$ phương án, thì số cách thực hiện công việc là $m \times n$.

Ví dụ 2: Một gia đình có 3 địa điểm du lịch ở Lào Cai và 4 địa điểm ở TP.HCM. Họ muốn đi cả hai nơi.

→ Số cách chọn = $3 \times 4 = 12$ cách

1.3 Sơ đồ hình cây

Sơ đồ hình cây giúp liệt kê và đếm tất cả trường hợp có thể.

Ví dụ 3: Từ các chữ số 1, 2, 3, có thể lập được bao nhiêu số có 2 chữ số khác nhau?

Phân tích bằng sơ đồ cây:

• Chữ số đầu: 3 cách (1, 2, hoặc 3)
• Chữ số sau: 2 cách (khác chữ số đầu)

     1 → 2, 3      (12, 13)
     2 → 1, 3      (21, 23)
     3 → 1, 2      (31, 32)

→ Tổng: $3 \times 2 = 6$ số

Hình minh họa sơ đồ cây:

Giải thích: Sơ đồ cây thể hiện quy tắc nhân: Chọn lần 1 có 3 cách (A, B, C), mỗi cách lại có 2 lựa chọn cho lần 2 → Tổng cộng 3×2=6 cách. Đây là nền tảng cho khái niệm chỉnh hợp.

2. Hoán vị

2.1 Định nghĩa

Hoán vị của $n$ phần tử là một cách sắp xếp $n$ phần tử đó theo một thứ tự nhất định.

Công thức: Số hoán vị của $n$ phần tử là: $P_n = n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1$

Quy ước: $0! = 1$

2.2 Ví dụ minh họa

Ví dụ 4: Có bao nhiêu cách xếp 5 người ngồi vào 5 ghế?

Lời giải:

• Ghế 1: 5 cách chọn
• Ghế 2: 4 cách chọn (còn 4 người)
• Ghế 3: 3 cách chọn
• Ghế 4: 2 cách chọn
• Ghế 5: 1 cách chọn

$P_5 = 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120 \text{ cách}$

Ví dụ 5: Xếp 11 cầu thủ vào hàng dọc để chụp ảnh. Có bao nhiêu cách?

Lời giải: $P_{11} = 11! = 39,916,800 \text{ cách}$

3. Chỉnh hợp

3.1 Định nghĩa

Chỉnh hợp chập k của n phần tử là một cách chọn và sắp xếp $k$ phần tử từ $n$ phần tử đã cho ($k \leq n$).

Công thức: $A_n^k = \frac{n!}{(n-k)!} = n(n-1)(n-2)\cdots(n-k+1)$

Nhận xét: Khi $k = n$, ta có $A_n^n = P_n = n!$

3.2 Ví dụ minh họa

Ví dụ 6: Chọn 3 học sinh từ 10 học sinh để làm lớp trưởng, lớp phó học tập, lớp phó lao động. Có bao nhiêu cách?

Lời giải:

Phân tích: Cần chọn 3 người từ 10 người VÀ sắp xếp vào 3 vị trí khác nhau → Đây là chỉnh hợp.

$A_{10}^3 = 10 \times 9 \times 8 = 720 \text{ cách}$

Hoặc dùng công thức: $A_{10}^3 = \frac{10!}{7!} = \frac{10!}{(10-3)!} = 720$

Ví dụ 7: Có bao nhiêu số tự nhiên có 4 chữ số khác nhau được lập từ 5?

Lời giải:

Lưu ý: Chữ số đầu tiên không được là 0!

Bước 1: Chọn chữ số đầu tiên (khác 0): 5 cách (1, 2, 3, 4, 5)

Bước 2: Chọn 3 chữ số còn lại từ 5 chữ số còn (bao gồm 0): $A_5^3 = 60$

→ Số cách = $5 \times 60 = 300$ số

4. Tổ hợp

4.1 Định nghĩa

Tổ hợp chập k của n phần tử là một cách chọn $k$ phần tử từ $n$ phần tử đã cho, không quan tâm thứ tự.

Công thức: $C_n^k = \binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{A_n^k}{k!}$

4.2 Tính chất

1. $C_n^0 = C_n^n = 1$
2. $C_n^k = C_n^{n-k}$ (tính đối xứng)
3. $C_n^k = C_{n-1}^{k-1} + C_{n-1}^k$ (công thức Pascal)

4.3 Ví dụ minh họa

Ví dụ 8: Chọn 3 học sinh từ 10 học sinh để đi dự trại hè. Có bao nhiêu cách?

Lời giải:

Phân tích: Chỉ CẦN CHỌN, không cần sắp xếp thứ tự → Đây là tổ hợp.

$C_{10}^3 = \frac{10!}{3! \times 7!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = \frac{720}{6} = 120 \text{ cách}$

Ví dụ 9: Trong mặt phẳng có 10 điểm, không có 3 điểm nào thẳng hàng. Có thể vẽ được bao nhiêu tam giác có đỉnh là các điểm đã cho?

Lời giải:

Phân tích: Mỗi tam giác xác định bởi 3 điểm, thứ tự không quan trọng.

$C_{10}^3 = \frac{10!}{3! \times 7!} = 120 \text{ tam giác}$

Hình minh họa tổ hợp:

Giải thích: Tổ hợp chỉ quan tâm đến việc CHỌN, không quan tâm thứ tự. Chọn 2 phần tử từ A, B, C: AB = BA (cùng 1 tổ hợp), nhưng là 2 chỉnh hợp khác nhau.

4.4 So sánh Chỉnh hợp và Tổ hợp

5. Nhị thức Newton

5.1 Công thức khai triển

Nhị thức Newton: Với mọi số nguyên dương $n$: $(a + b)^n = \sum_{k=0}^{n} C_n^k \cdot a^{n-k} \cdot b^k$

Hay viết đầy đủ: $(a + b)^n = C_n^0 a^n + C_n^1 a^{n-1}b + C_n^2 a^{n-2}b^2 + \cdots + C_n^n b^n$

5.2 Tính chất

1. Số hạng thứ $(k+1)$ trong khai triển: $T_{k+1} = C_n^k \cdot a^{n-k} \cdot b^k$
2. Tổng các hệ số: $C_n^0 + C_n^1 + \cdots + C_n^n = 2^n$
3. Hệ số đối xứng: $C_n^k = C_n^{n-k}$

5.3 Ví dụ minh họa

Ví dụ 10: Khai triển $(x + 1)^4$

Lời giải:

Nhắc lại: $(a + b)^n = \sum_{k=0}^{n} C_n^k \cdot a^{n-k} \cdot b^k$

Bước 1: Áp dụng công thức nhị thức Newton với $a = x$, $b = 1$, $n = 4$

$(x + 1)^4 = C_4^0 x^4 + C_4^1 x^3 \cdot 1 + C_4^2 x^2 \cdot 1^2 + C_4^3 x \cdot 1^3 + C_4^4 \cdot 1^4$

Bước 2: Tính các hệ số $C_4^k$

• $C_4^0 = 1$, $C_4^1 = 4$, $C_4^2 = 6$, $C_4^3 = 4$, $C_4^4 = 1$

Bước 3: Thay vào và rút gọn

$= 1 \cdot x^4 + 4 \cdot x^3 + 6 \cdot x^2 + 4 \cdot x + 1$

$= x^4 + 4x^3 + 6x^2 + 4x + 1$

Kiểm tra: Thay $x = 1$: $(1 + 1)^4 = 16$ và $1 + 4 + 6 + 4 + 1 = 16$ ✓

Ví dụ 11: Khai triển $(x - 1)^5$

Lời giải:

Lưu ý: $(x - 1)^5 = (x + (-1))^5$, khi $b = -1$ thì $b^k = (-1)^k$

Bước 1: Áp dụng công thức với các hệ số $C_5^k$: 1, 5, 10, 10, 5, 1

Bước 2: Viết khai triển (chú ý dấu thay đổi do $(-1)^k$)

$(x - 1)^5 = x^5 - 5x^4 + 10x^3 - 10x^2 + 5x - 1$

Nhận xét: Các hệ số luân phiên dấu (+, -, +, -, …) khi $b < 0$

Ví dụ 12: Tìm hệ số của $x^3$ trong khai triển $(2x + 1)^5$

Lời giải:

Bước 1: Xác định số hạng chứa $x^3$

• Số hạng tổng quát: $T_{k+1} = C_5^k (2x)^{5-k} \cdot 1^k = C_5^k \cdot 2^{5-k} \cdot x^{5-k}$
• Cần $5 - k = 3 \Rightarrow k = 2$

Bước 2: Tính hệ số $T_3 = C_5^2 \cdot 2^3 \cdot x^3 = 10 \cdot 8 \cdot x^3 = 80x^3$

Đáp án: Hệ số của $x^3$ là 80.

Bài tập mẫu

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

Một cửa hàng có 5 loại áo và 4 loại quần. Hỏi có bao nhiêu cách chọn: a) 1 bộ gồm 1 áo và 1 quần? b) 1 món (áo hoặc quần)?

Lời giải:

a) Chọn 1 bộ = chọn áo VÀ chọn quần → Quy tắc nhân

Nhắc lại: Khi làm 2 việc ĐỒNG THỜI → Nhân

Bước 1: Chọn áo: 5 cách
Bước 2: Chọn quần: 4 cách

$\text{Số cách} = 5 \times 4 = 20 \text{ cách}$

b) Chọn 1 món = chọn áo HOẶC chọn quần → Quy tắc cộng

Nhắc lại: Khi làm 1 trong 2 việc → Cộng

$\text{Số cách} = 5 + 4 = 9 \text{ cách}$

Bài 2: Hoán vị

Có bao nhiêu cách xếp 6 quyển sách khác nhau lên một kệ sách?

Lời giải:

Nhắc lại: Xếp TẤT CẢ n phần tử → Hoán vị $P_n = n!$

Bước 1: Xác định đây là bài toán hoán vị (xếp tất cả 6 quyển)

Bước 2: Áp dụng công thức $P_6 = 6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720 \text{ cách}$

Bài 3: Chỉnh hợp

Một đội có 12 vận động viên. Huấn luyện viên cần chọn 4 người để thi đấu theo thứ tự: người thứ nhất bơi 100m, người thứ hai bơi 200m, người thứ ba bơi 400m, người thứ tư bơi 800m. Có bao nhiêu cách chọn?

Lời giải:

Phân tích: Chọn 4 từ 12 VÀ sắp xếp theo thứ tự → Chỉnh hợp

Bước 1: Xác định $n = 12$, $k = 4$

Bước 2: Áp dụng công thức chỉnh hợp $A_{12}^4 = 12 \times 11 \times 10 \times 9 = 11,880 \text{ cách}$

Kiểm tra bằng công thức: $A_{12}^4 = \frac{12!}{8!} = \frac{12!}{(12-4)!} = 11,880$ ✓

Bài 4: Tổ hợp

Một lớp có 30 học sinh. Cần chọn 5 học sinh đi dự hội nghị. Có bao nhiêu cách chọn?

Lời giải:

Phân tích: Chỉ CẦN CHỌN, không quan tâm thứ tự → Tổ hợp

Bước 1: Xác định $n = 30$, $k = 5$

Bước 2: Áp dụng công thức tổ hợp $C_{30}^5 = \frac{30!}{5! \times 25!} = \frac{30 \times 29 \times 28 \times 27 \times 26}{5 \times 4 \times 3 \times 2 \times 1}$

Bước 3: Tính toán $C_{30}^5 = \frac{17,100,720}{120} = 142,506 \text{ cách}$

Bài 5: Phân biệt Chỉnh hợp và Tổ hợp

Từ 8 cuốn sách khác nhau: a) Chọn 3 cuốn để tặng 3 bạn A, B, C (mỗi bạn 1 cuốn). Có bao nhiêu cách? b) Chọn 3 cuốn để đem đi xa. Có bao nhiêu cách?

Lời giải:

a) Tặng 3 bạn cụ thể → Thứ tự quan trọng → Chỉnh hợp

$A_8^3 = 8 \times 7 \times 6 = 336 \text{ cách}$

b) Đem đi xa → Chỉ cần chọn, không phân biệt → Tổ hợp

$C_8^3 = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = \frac{336}{6} = 56 \text{ cách}$

Nhận xét: $C_8^3 = \frac{A_8^3}{3!} = \frac{336}{6} = 56$ ✓

Bài 6: Nhị thức Newton

Khai triển $(2x - 3)^4$.

Lời giải:

Nhắc lại: $(a + b)^n = \sum_{k=0}^{n} C_n^k a^{n-k} b^k$

Ở đây $a = 2x$, $b = -3$, $n = 4$

Bước 1: Viết các hệ số $C_4^k$: 1, 4, 6, 4, 1

Bước 2: Tính từng số hạng

Bước 3: Kết quả

$(2x - 3)^4 = 16x^4 - 96x^3 + 216x^2 - 216x + 81$

Kiểm tra: Thay $x = 1$: $(2 - 3)^4 = 1$. Tổng hệ số: $16 - 96 + 216 - 216 + 81 = 1$ ✓

Bài 7: Tìm hệ số trong khai triển

Tìm hệ số của $x^5$ trong khai triển $(1 + x)^8$.

Lời giải:

Nhắc lại: Số hạng tổng quát: $T_{k+1} = C_n^k \cdot 1^{n-k} \cdot x^k = C_n^k x^k$

Bước 1: Tìm k sao cho số mũ của x bằng 5 $k = 5$

Bước 2: Tính hệ số $C_8^5 = C_8^3 = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$

Đáp án: Hệ số của $x^5$ là 56.

Bài 8: Bài toán tổng hợp

Có 5 nam và 4 nữ. Cần lập một nhóm 4 người sao cho có ít nhất 1 nữ. Có bao nhiêu cách?

Lời giải:

Phân tích: “Ít nhất 1 nữ” = Tổng cách - Không có nữ nào

Cách 1: Dùng phần bù

Bước 1: Tổng số cách chọn 4 người từ 9 người $C_9^4 = \frac{9 \times 8 \times 7 \times 6}{4!} = 126$

Bước 2: Số cách không có nữ nào (chỉ chọn nam) $C_5^4 = 5$

Bước 3: Số cách có ít nhất 1 nữ $126 - 5 = 121 \text{ cách}$

Cách 2: Tính trực tiếp

Tổng: $40 + 60 + 20 + 1 = 121$ cách ✓

Bài tập tự luyện

Bài 1

Từ các chữ số 1, 2, 3, 4, 5 có thể lập được bao nhiêu số tự nhiên có 3 chữ số khác nhau?

Bài 2

Một tổ có 7 nam và 5 nữ. Cần chọn 4 người sao cho có đúng 2 nam và 2 nữ. Có bao nhiêu cách?

Bài 3

Tìm hệ số của $x^4$ trong khai triển $(3x - 2)^6$.

Tóm tắt

Công thức quan trọng

Key Points

• Chỉnh hợp = chọn CÓ thứ tự (AB ≠ BA)
• Tổ hợp = chọn KHÔNG thứ tự (AB = BA)
• Công thức: $C_n^k = \frac{A_n^k}{k!}$ (chia cho số cách sắp xếp)
• Lưu ý: Quy ước đặc biệt: $0! = 1$, $C_n^0 = C_n^n = 1$