Khám phá hệ thức tổ hợp Chu-Vandermonde qua 2 phương pháp chứng minh: lập luận tổ hợp và nhị thức Newton. Tìm hiểu lịch sử thú vị đằng sau hệ thức này
Hệ thức Chu-Vandermonde là một trong những đẳng thức tổ hợp kinh điển, ghi dấu sự gặp gỡ kỳ diệu giữa hai nền toán học Đông - Tây cách nhau hơn 5 thế kỷ.
Được Chu Thế Kiệt (Chu Shih-chieh, nhà toán học thời Nguyên) ghi chép từ năm 1303 và sau đó được Alexandre-Théophile Vandermonde tái phát hiện, hệ thống hóa bằng ngôn ngữ đại số hiện đại vào năm 1772, hệ thức này không chỉ là công cụ mạnh mẽ để rút gọn các tổng tổ hợp mà còn là minh chứng cho sự phát triển độc lập nhưng thống nhất của tư duy nhân loại.
Trong bài viết này, chúng ta sẽ cùng khám phá bản chất của hệ thức thông qua các phương pháp chứng minh từ lập luận tổ hợp trực quan đến biến đổi nhị thức Newton chặt chẽ.
Chứng minh hệ thức Chu-Vandermonde bằng phương pháp tổ hợp và đại số
Đề bài toán
Hệ thức Chu-Vandermonde
Chứng minh hệ thức Chu-Vandermonde:
\[ \sum_{k=0}^{r} \binom{n}{k} \binom{m}{r-k} = \binom{n+m}{r} \]
Trong đó $n, m, r$ là các số nguyên không âm và $r \leq \min(n, m)$.
Ví dụ minh họa
Áp dụng cho bộ $(8,7,4)$ ta có
\[ \sum_{k=0}^{4} \binom{8}{k} \binom{7}{4-k} = \binom{15}{4} \]
Lời giải
Trong bài viết này, chúng ta sử dụng kí hiệu số tổ hợp chập $k$ của $n$ phần tử là $\binom{n}{k}$ thay cho kí hiệu $C_n^k$.
Cách 1: Phương pháp lập luận tổ hợp (Đếm bằng hai cách)
Giả sử chúng ta có một tập hợp gồm $n+m$ phần tử, chia làm hai nhóm riêng biệt:
- Nhóm 1 có $n$ phần tử (ví dụ: $n$ học sinh nam).
- Nhóm 2 có $m$ phần tử (ví dụ: $m$ học sinh nữ).
Yêu cầu: Chọn ra $r$ phần tử từ tổng số $n+m$ phần tử này.
Hướng 1: Tính trực tiếp
Số cách chọn $r$ phần tử từ $n+m$ phần tử mà không phân biệt nhóm là: \[ \binom{n+m}{r} \]
Hướng 2: Chia theo các trường hợp
Để chọn được $r$ phần tử, ta có thể chọn $k$ phần tử từ nhóm 1 và $(r-k)$ phần tử từ nhóm 2. Vì tổng số phần tử cần chọn là $r$, nên chỉ số $k$ chạy từ $0$ đến $r$:
Với mỗi giá trị $k$ cố định, số cách chọn là: \(\binom{n}{k} \binom{m}{r-k}\)
Tổng số cách chọn cho tất cả các trường hợp là: \[ \sum_{k=0}^{r} \binom{n}{k} \binom{m}{r-k} \]
Vì cả hai hướng đều đếm cùng một đối tượng, ta có đẳng thức cần chứng minh.
Cách 2: Phương pháp đại số (Sử dụng Nhị thức Newton)
Xét đa thức $P(x) = (1+x)^{n+m}$. Ta sẽ tìm hệ số của số hạng $x^r$ trong khai triển của đa thức này theo hai cách khác nhau.
Cách khai triển 1:
Theo công thức Nhị thức Newton: \[ (1+x)^{n+m} = \sum_{p=0}^{n+m} \binom{n+m}{p} x^p \] Hệ số của $x^r$ trong khai triển này là: \(\binom{n+m}{r}\).
Cách khai triển 2:
Ta viết lại đa thức dưới dạng tích: \[ (1+x)^{n+m} = (1+x)^n \cdot (1+x)^m \] Khai triển từng nhân tử: \[ (1+x)^n = \sum_{i=0}^n \binom{n}{i} x^i \] \[ (1+x)^m = \sum_{j=0}^m \binom{m}{j} x^j \]
Khi nhân hai tổng này, số hạng chứa $x^r$ xuất hiện khi tổng các số mũ bằng $r$ (tức là $i+j=r \Rightarrow j=r-i$). Hệ số của $x^r$ trong tích này là: \[ \sum_{i=0}^{r} \binom{n}{i} \binom{m}{r-i} \]
Đồng nhất hệ số của $x^r$ ở cả hai cách khai triển, ta được: \[ \sum_{k=0}^{r} \binom{n}{k} \binom{m}{r-k} = \binom{n+m}{r} \]
Kết luận
Hệ thức Chu-Vandermonde là một công cụ mạnh mẽ để rút gọn các tổng tổ hợp phức tạp. Trong trường hợp cụ thể ở đề bài:
\[ \sum_{k=0}^{4} \binom{8}{k} \binom{7}{4-k} = \binom{15}{4} = 1365. \]
