Kỹ Thuật Đếm Hai Lần (Double Counting)

1. Giới thiệu

Kỹ thuật "Đếm hai lần" (Double Counting) là một phương pháp quan trọng trong Tổ hợp, đặc biệt hữu ích trong việc chứng minh các đẳng thức tổ hợp hoặc giải quyết các bài toán đếm phức tạp. Ý tưởng cơ bản của kỹ thuật này là đếm số phần tử của một tập hợp theo hai cách khác nhau. Vì số phần tử của tập hợp là một số duy nhất, hai cách đếm khác nhau này sẽ dẫn đến hai biểu thức toán học bằng nhau. Từ đó, ta có thể suy ra các đẳng thức hoặc giải quyết bài toán.

2. Nguyên lý cơ bản

Nguyên lý: Cho $S$ là một tập hợp hữu hạn. Nếu ta đếm số phần tử của $S$ theo hai cách khác nhau và thu được hai biểu thức $A$ và $B$, thì $A = B$.

3. Các bước áp dụng kỹ thuật "Đếm hai lần"

1. Xác định tập hợp $S$ cần đếm: Đây là bước quan trọng nhất, cần xác định rõ tập hợp mà ta muốn đếm số phần tử.
2. Đếm $S$ theo cách 1: Tìm một cách đếm tự nhiên, đơn giản hoặc trực tiếp để biểu diễn số phần tử của $S$ dưới dạng biểu thức $A$.
3. Đếm $S$ theo cách 2: Tìm một cách đếm khác, thường phức tạp hơn cách 1, để biểu diễn số phần tử của $S$ dưới dạng biểu thức $B$.
4. Kết luận: Vì cả hai cách đếm đều cho ra số phần tử của $S$, ta có $A = B$. Từ đẳng thức này, ta có thể suy ra các kết quả hoặc giải quyết bài toán.

4. Ví dụ minh họa

Ví dụ 1: Chứng minh đẳng thức tổ hợp

Chứng minh đẳng thức sau: $\sum_{k=0}^{n} \binom{n}{k} = 2^n$

Lời giải:

1. Xác định tập hợp $S$: Gọi $S$ là tập hợp tất cả các tập con của tập hợp $A = \{1, 2, ..., n\}$.

2. Đếm $S$ theo cách 1: Mỗi phần tử của $S$ là một tập con của $A$. Để tạo ra một tập con, ta có hai lựa chọn cho mỗi phần tử của $A$: hoặc chọn nó vào tập con, hoặc không chọn. Vì có $n$ phần tử trong $A$, nên số tập con của $A$ là $2^n$. Vậy $|S| = 2^n$.

3. Đếm $S$ theo cách 2: Ta có thể phân loại các tập con của $A$ theo số lượng phần tử. Có $\binom{n}{k}$ tập con có kích thước $k$, với $k$ chạy từ $0$ đến $n$. Do đó, tổng số tập con của $A$ là $\sum_{k=0}^{n} \binom{n}{k}$. Vậy $|S| = \sum_{k=0}^{n} \binom{n}{k}$.

4. Kết luận: Vì cả hai cách đếm đều cho ra số phần tử của $S$, ta có: $\sum_{k=0}^{n} \binom{n}{k} = 2^n$

Ví dụ 2: Bài toán về bắt tay

Trong một bữa tiệc có $n$ người. Chứng minh rằng tổng số cái bắt tay trong bữa tiệc luôn là một số chẵn.

Lời giải:

1. Xác định tập hợp $S$: Gọi $S$ là tập hợp các cặp $(p, h)$, trong đó $p$ là người và $h$ là cái bắt tay mà người $p$ thực hiện.

2. Đếm $S$ theo cách 1: Gọi $d_i$ là số cái bắt tay mà người thứ $i$ thực hiện, với $i = 1, 2, ..., n$. Khi đó, tổng số phần tử của $S$ là: $|S| = \sum_{i=1}^{n} d_i$

3. Đếm $S$ theo cách 2: Mỗi cái bắt tay được đếm hai lần (một lần cho mỗi người tham gia bắt tay). Nếu có $B$ cái bắt tay trong bữa tiệc, thì số phần tử của $S$ là $|S| = 2B$.

4. Kết luận: Vì cả hai cách đếm đều cho ra số phần tử của $S$, ta có: $\sum_{i=1}^{n} d_i = 2B$ Vậy tổng số cái bắt tay mà mỗi người thực hiện là một số chẵn.

Ví dụ 3: Bài toán đồ thị

Cho đồ thị $G$ có $n$ đỉnh. Gọi $d_i$ là bậc của đỉnh thứ $i$ (số cạnh kề với đỉnh đó). Chứng minh rằng: $\sum_{i=1}^{n} d_i = 2m$ trong đó $m$ là số cạnh của đồ thị.

Lời giải:

1. Xác định tập hợp $S$: Gọi $S$ là tập hợp các cặp $(v, e)$, trong đó $v$ là một đỉnh và $e$ là một cạnh kề với đỉnh $v$.

2. Đếm $S$ theo cách 1: Với mỗi đỉnh $i$, có $d_i$ cạnh kề với nó. Do đó, số phần tử của $S$ là: $|S| = \sum_{i=1}^{n} d_i$

3. Đếm $S$ theo cách 2: Mỗi cạnh được đếm hai lần (một lần cho mỗi đỉnh mà nó kết nối). Vì có $m$ cạnh, số phần tử của $S$ là $|S| = 2m$.

4. Kết luận: Vì cả hai cách đếm đều cho ra số phần tử của $S$, ta có: $\sum_{i=1}^{n} d_i = 2m$

5. Bài tập tự luyện

1. Chứng minh đẳng thức: $\sum_{k=1}^{n} k \binom{n}{k} = n2^{n-1}$
2. Trong một lớp học có $n$ học sinh và $m$ câu lạc bộ. Mỗi học sinh tham gia đúng $k$ câu lạc bộ, và mỗi câu lạc bộ có đúng $r$ học sinh. Chứng minh rằng $nk = mr$.
3. Cho một bảng kích thước $n \times n$. Chứng minh rằng tổng số hình chữ nhật tạo thành từ các ô trong bảng là $\binom{n+1}{2}^2$.

6. Kết luận

Kỹ thuật "Đếm hai lần" là một công cụ mạnh mẽ trong Tổ hợp. Việc luyện tập thường xuyên với các bài toán khác nhau sẽ giúp bạn làm quen và sử dụng kỹ thuật này một cách hiệu quả. Quan trọng nhất là xác định đúng tập hợp cần đếm và tìm ra hai cách đếm khác nhau.