Các định lý tổ hợp và các loại số - Bài toán áp dụng
1. Định lý tổ hợp Newton (Binomial Theorem)
Định lý tổ hợp Newton phát biểu rằng khai triển một nhị thức có dạng \( (x + y)^n \) được tính như sau:
\[
(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k
\]
Bài toán áp dụng
**Bài toán**: Tìm hệ số của \(x^3 y^2\) trong khai triển của \( (x + y)^5 \).
**Giải**: Hệ số của \( x^3 y^2 \) trong khai triển của \( (x + y)^5 \) tương ứng với \( k = 3 \), vì tổng số
mũ phải bằng 5. Do đó hệ số là:
\[
\binom{5}{3} = \frac{5!}{3!(5-3)!} = \frac{120}{6 \times 2} = 10
\]
Vậy hệ số của \( x^3 y^2 \) là 10.
2. Số Catalan (Catalan Numbers)
Số Catalan được sử dụng trong nhiều bài toán tổ hợp như đếm số cách ghép ngoặc hoặc chia một đa giác lồi
thành tam giác.
Công thức tổng quát của số Catalan thứ \( n \) là:
\[
C_n = \frac{1}{n+1} \binom{2n}{n}
\]
Bài toán áp dụng
**Bài toán**: Tính số cách ghép đúng 4 cặp dấu ngoặc (đóng và mở).
**Giải**: Số cách ghép 4 cặp ngoặc tương ứng với số Catalan thứ 4:
\[
C_4 = \frac{1}{4+1} \binom{8}{4} = \frac{1}{5} \times 70 = 14
\]
Vậy có 14 cách ghép 4 cặp dấu ngoặc đúng.
3. Số Fibonacci (Fibonacci Numbers)
Số Fibonacci tuân theo công thức truy hồi:
\[
F_n = F_{n-1} + F_{n-2}, \quad F_0 = 0, F_1 = 1
\]
Bài toán áp dụng
**Bài toán**: Tìm số Fibonacci thứ 12.
**Giải**: Dùng công thức truy hồi để tính:
\[
F_2 = F_1 + F_0 = 1 + 0 = 1, \quad F_3 = F_2 + F_1 = 1 + 1 = 2, \quad F_4 = F_3 + F_2 = 2 + 1 = 3, \ldots
\]
Tiếp tục tính đến \( F_{12} = 144 \).
Vậy số Fibonacci thứ 12 là 144.
4. Số Stirling loại 1 (Stirling Numbers of the First Kind)
Số Stirling loại 1 \( S_1(n, k) \) là số cách sắp xếp \( n \) phần tử thành \( k \) chu trình (hoán vị). Công
thức truy hồi:
\[
S_1(n, k) = S_1(n-1, k-1) + (n-1)S_1(n-1, k)
\]
Bài toán áp dụng
**Bài toán**: Tìm số cách sắp xếp 4 phần tử thành 2 chu trình.
**Giải**: Sử dụng công thức truy hồi:
\[
S_1(4, 2) = S_1(3, 1) + 3 \times S_1(3, 2) = 2 + 3 \times 3 = 11
\]
Vậy có 11 cách sắp xếp 4 phần tử thành 2 chu trình.
5. Số Stirling loại 2 (Stirling Numbers of the Second Kind)
Số Stirling loại 2 \( S_2(n, k) \) là số cách phân chia \( n \) phần tử thành \( k \) tập con không rỗng.
Công thức truy hồi:
\[
S_2(n, k) = S_2(n-1, k-1) + k \times S_2(n-1, k)
\]
Bài toán áp dụng
**Bài toán**: Tìm số cách chia 5 phần tử thành 3 nhóm không rỗng.
**Giải**: Sử dụng công thức truy hồi:
\[
S_2(5, 3) = S_2(4, 2) + 3 \times S_2(4, 3) = 7 + 3 \times 6 = 25
\]
Vậy có 25 cách chia 5 phần tử thành 3 nhóm không rỗng.
6. Bài toán chia kẹo
Giả sử bạn có \( n \) viên kẹo và cần chia cho \( k \) người sao cho mỗi người có thể nhận bất kỳ số lượng
kẹo nào (bao gồm cả 0 viên).
Bài toán áp dụng
**Bài toán**: Chia 10 viên kẹo cho 3 người.
**Giải**: Đây là bài toán đếm số cách phân tích số nguyên dương \( n = 10 \) thành tổng của \( k = 3 \) số
không âm, tức là bài toán tìm số nghiệm của phương trình:
\[
x_1 + x_2 + x_3 = 10
\]
Số nghiệm của phương trình này là:
\[
\binom{10 + 3 - 1}{3 - 1} = \binom{12}{2} = \frac{12 \times 11}{2} = 66
\]
Vậy có 66 cách chia 10 viên kẹo cho 3 người.
7. Định lý Euler (Euler's Theorem)
Nếu \( n \) và \( a \) là hai số nguyên nguyên tố cùng nhau, thì:
\[
a^{\phi(n)} \equiv 1 \ (\text{mod}\ n)
\]
với \( \phi(n) \) là hàm phi Euler.
Bài toán áp dụng
**Bài toán**: Tìm \( 5^6 \mod 7 \).
**Giải**: \( a = 5 \), \( n = 7 \), \( \phi(7) = 6 \). Theo định lý Euler:
\[
5^6 \equiv 1 \ (\text{mod}\ 7)
\]
8. Số Bell (Bell Numbers)
Số Bell \( B_n \) đếm số cách phân hoạch một tập \( n \) phần tử thành các tập con không rỗng.
Công thức truy hồi:
\[
B_{n+1} = \sum_{k=0}^{n} \binom{n}{k} B_k
\]
Bài toán áp dụng
**Bài toán**: Tính số Bell thứ 3.
**Giải**: Sử dụng công thức truy hồi:
\[
B_3 = \binom{2}{0}B_0 + \binom{2}{1}B_1 + \binom{2}{2}B_2 = 1 \times 1 + 2 \times 1 + 1 \times 2 = 5
\]
Vậy số Bell thứ 3 là 5.