Đếm bằng hai cách

Giả sử có hai đại lượng cần so sánh ${\displaystyle A}$ và ${\displaystyle B}$ . 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 ${\displaystyle C}$ .

Bước 2: Đếm ${\displaystyle C}$ và tìm mối liên hệ giữa ${\displaystyle C}$ và ${\displaystyle A}$ , ${\displaystyle C}$ và ${\displaystyle B}$ (vd. ${\displaystyle C\geq A}$ và ${\displaystyle C=B}$ ).

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

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ó ${\displaystyle m}$ hàng và ${\displaystyle n}$ 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 ${\displaystyle a_{1},a_{2},...,a_{m}}$ lần lượt là số đồng xu trong hàng thứ ${\displaystyle 1,2,...,m}$ và ${\displaystyle b_{1},b_{2},...b_{n}}$ lần lượt là số đồng xu trong cột thứ ${\displaystyle 1,2,...,n}$ . Chứng minh rằng: ${\displaystyle \sum _{i=1}^{m}a_{i}=\sum _{j=1}^{n}b_{j}}$ .

Giải

Gọi ${\displaystyle S}$ là số đồng xu trong tủ. Ta đếm ${\displaystyle S}$ 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ế ${\displaystyle S=a_{1}+a_{2}+...+a_{m}}$ .

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 đó ${\displaystyle S=b_{1}+b_{2}+...+b_{n}}$ .

Từ hai hệ thức trên ta suy ra ${\displaystyle \sum _{i=1}^{m}a_{i}=\sum _{j=1}^{n}b_{j}}$ , đpcm.

Ví dụ 1.2. Bậc và cạnh trong đồ thị

Cho đồ thị ${\displaystyle G}$ có ${\displaystyle n\geq 1}$ đỉnh và ${\displaystyle E}$ cạnh. Gọi ${\displaystyle d_{1},d_{2},\dots ,d_{n}}$ là bậc của các đỉnh trong đồ thị theo thứ tự tương ứng. Chứng minh rằng: ${\displaystyle \sum _{i=1}^{n}d_{i}=2E}$ .

Giải

Gọi ${\displaystyle S}$ là tập hợp tất cả các bộ ${\displaystyle (u,a)}$ thỏa mãn:

${\displaystyle i)}$ ${\displaystyle u}$ là một đỉnh của đồ thị.

${\displaystyle ii)}$ ${\displaystyle a}$ là một cạnh của đồ thị.

${\displaystyle iii)}$ ${\displaystyle u}$ là một trong hai mút của ${\displaystyle a}$ .

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

Cách 1: Chọn ${\displaystyle u}$ trước: có ${\displaystyle E}$ cách để chọn ra một cạnh của đồ thị, với mỗi cạnh ${\displaystyle a}$ , có đúng 2 đỉnh là mút của ${\displaystyle a}$ . Vì thế nên ${\displaystyle |S|=2{\dot {E}}}$ .

Cách 2: Chọn ${\displaystyle a}$ trước: có ${\displaystyle n}$ cách chọn đỉnh. Nếu ta chọn đỉnh thứ ${\displaystyle i}$ , vì đỉnh này có bậc là ${\displaystyle d_{i}}$ nên có đúng ${\displaystyle d_{i}}$ cạnh nhận đỉnh này làm mút. Vì thế ${\displaystyle |S|=\sum _{i=1}^{n}(d_{i})}$ .

Từ hai hệ thức trên suy ra ${\displaystyle \sum _{i=1}^{n}d_{i}=2E=|S|}$ , đpcm.

Ví dụ 1.3. Hệ số nhị thức

Chứng minh rằng: với ${\displaystyle n}$ là số nguyên dương thì ${\displaystyle {\binom {n}{0}}+{\binom {n}{1}}+...+{\binom {n}{n}}=2^{n}}$ .

Giải

Xét tập hợp ${\displaystyle S=\lbrace 1;2;...;n\rbrace }$ . Gọi ${\displaystyle P}$ là số tập con của ${\displaystyle S}$ .

Ta đếm ${\displaystyle P}$ bằng hai cách:

Cách 1: Số tập con có ${\displaystyle 0}$ phần tử của ${\displaystyle S}$ là ${\displaystyle {\binom {n}{0}}}$ , số tập con có ${\displaystyle 1}$ phần tử của ${\displaystyle S}$ là ${\displaystyle {\binom {n}{1}}}$ ,..., số tập con có ${\displaystyle n}$ phần tử của ${\displaystyle S}$ là ${\displaystyle {\binom {n}{n}}}$ . Vì thế ${\displaystyle P={\binom {n}{0}}+{\binom {n}{1}}+...+{\binom {n}{n}}}$ .

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

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

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

• Pranav A.Sriram, "Olympiad Combinatorics, Chapter 6: Counting in Two Ways".

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