Đế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.

:Thể loại: Toán học tổ hợp

 Phương pháp 
Giả sử có hai đại lượng cần so sánh  và . 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 .

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

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

 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ó  hàng và  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  lần lượt là số đồng xu  trong hàng thứ  và  lần lượt là số đồng xu trong cột thứ . Chứng minh rằng: .

Giải

Gọi  là số đồng xu trong tủ. Ta đếm  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ế .

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 đó .

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

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

Giải

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

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

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

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

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

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

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

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

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

Giải

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

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

Cách 1: Số tập con có  phần tử của  là , số tập con có  phần tử của  là ,..., số tập con có  phần tử của  là . Vì thế .

Cách 2: Ta đếm số cách chọn một số phần tử bất kì của . 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à  có  phần tử nên số trường hợp khác nhau có thể xảy ra là . Vậy .

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

 Xem thêm 

 Tham khảo 

 Pranav A.Sriram, "Olympiad Combinatorics, Chapter 6: Counting in Two Ways".
:Thể loại: Toán học tổ hợp

Thể loại:Chứng minh toán học