Đếm bằng hai cách

Trong toán học tổ hợp, đếm bằng hai cách là một kĩ thuật được dùng để so sánh hai đại lượng.

Phương pháp đếm bằng hai cách áp dụng nguyên lý: mọi cách đếm một đại lượng nào đó đều cho ra kết quả giống nhau. Ý tưởng chính của phương pháp này là xét thêm một đại lượng thứ ba có thể được đếm bằng hai cách cho kết quả liên quan đến các đại lượng ban đầu.

== Phương pháp ==
Giả sử có hai đại lượng cần so sánh formula_1 và formula_2. Phương pháp đếm bằng hai cách được thực hiện như sau:

"Bước 1:" Chỉ ra một đại lượng formula_3.

"Bước 2:" Đếm formula_3 và tìm mối liên hệ giữa formula_3 và formula_1, formula_3 và formula_2 (vd. formula_9 và formula_10).

"Bước 3:" Từ các kết luận ở bước 2 rút ra quan hệ giữa formula_1 và formula_2 (vd. formula_13).

== Ví dụ ==
Phương pháp đếm bằng hai cách có thể được sử dụng để giải quyết một số bài toán đếm tổ hợp.

=== Ví dụ 1.1 ===
"Một tủ đựng đồ có" formula_14 "hàng và" formula_15 "cột, mỗi ô tủ chứa nhiều nhất 1 đồng xu (có thể không chứa đồng xu nào). Gọi" formula_16 "lần lượt là số đồng xu trong hàng thứ" formula_17 "và" formula_18 "lần lượt là số đồng xu trong cột thứ" formula_19". Chứng minh rằng:" formula_20.

Giải

Gọi formula_21 là số đồng xu trong tủ. Ta đếm formula_21 bằng hai cách:

"Cách 1:" Số đồng xu trong tủ chính là tổng số đồng xu trên các hàng, vì thế formula_23.

"Cách 2:" Tương tự, số đồng xu trong tủ cũng chính là tổng số đồng xu trên các cột, do đó formula_24.

Từ hai hệ thức trên ta suy ra formula_20, đpcm.

=== Ví dụ 1.2. Bậc và cạnh trong đồ thị ===
"Cho đồ thị" formula_26 "có" formula_27 "đỉnh và" formula_28 "cạnh. Gọi" formula_29 "là bậc của các đỉnh trong đồ thị theo thứ tự tương ứng. Chứng minh rằng:" formula_30.

Giải

Gọi formula_21 là tập hợp tất cả các bộ formula_32 thỏa mãn:

formula_33 formula_34 là một đỉnh của đồ thị.

formula_35 formula_36 là một cạnh của đồ thị.

formula_37 formula_34 là một trong hai mút của formula_36.

Ta đếm số lượng phần tử của formula_21 bằng hai cách:

"Cách 1:" Chọn formula_34 trước: có formula_28 cách để chọn ra một cạnh của đồ thị, với mỗi cạnh formula_36, có đúng 2 đỉnh là mút của formula_36. Vì thế nên formula_45.

"Cách 2:" Chọn formula_36 trước: có formula_15 cách chọn đỉnh. Nếu ta chọn đỉnh thứ formula_48, vì đỉnh này có bậc là formula_49 nên có đúng formula_49 cạnh nhận đỉnh này làm mút. Vì thế formula_51.

Từ hai hệ thức trên suy ra formula_52, đpcm.

=== Ví dụ 1.3. Hệ số nhị thức ===
"Chứng minh rằng: với" formula_15 "là số nguyên dương thì" formula_54.

Giải

Xét tập hợp formula_55. Gọi formula_56 là số tập con của formula_21.

Ta đếm formula_56 bằng hai cách:

"Cách 1:" Số tập con có formula_59 phần tử của formula_21 là formula_61, số tập con có formula_62 phần tử của formula_21 là formula_64..., số tập con có formula_15 phần tử của formula_21 là formula_67. Vì thế formula_68.

"Cách 2:" Ta đếm số cách chọn một số phần tử bất kì của formula_21. Với mỗi cách chọn ta thu được một tập con duy nhất. Với mỗi phần tử, ta có thể chọn hoặc không chọn phần tử này, nên có hai trường hợp. Mà formula_21 có formula_15 phần tử nên số trường hợp khác nhau có thể xảy ra là formula_72. Vậy formula_73.

Từ hai hệ thức trên ta có đpcm.

== Ứng dụng ==
Phương pháp đếm bằng hai cách cũng được sử dụng trong chứng minh của các bài toán sau:

- Số Catalan
- Bài toán phiếu bầu
- Luật tương hỗ bậc hai

== Tham khảo ==
- Pranav A.Sriram, "Olympiad Combinatorics, Chapter 6: Counting in Two Ways".