Định trị một đại lượng bằng hai cách [1]

Ngô Quang Hưng | 31 tháng 03, 2006 | Bản để in Bản để in

Một trong những ý tưởng sâu sắc nhất tôi học được trong Toán học là “định trị một đại lượng bằng hai cách“. Ta có thể dùng ý tưởng này để

  • chứng minh rất nhiều các đẳng thức toán học
  • tìm công thức (gọn) tính một biểu thức toán học
  • chứng minh rất nhiều các bất đẳng thức toán học

Trong loạt bài này tôi ghi lại một số ví dụ minh họa ý tưởng này. Trong các ví dụ sau đây, ta dùng ký hiệu

[n] = \{1, \dots, n\}

Ví dụ 1: xét đẳng thức

\sum_{i=0}^n \binom{n}{i} = 2^n

Vế trái rõ là đếm tổng số các tập con của [n] (đếm theo i là kích thước tập con). Mỗi tập con tương ứng 1-1 với một vector trong \mathbb{F}_2^n, các phần tử của tập con tương ứng với thành phần bằng 1 trong vector. Có tổng cộng 2^n vectors như vậy.

Ví dụ 2: đẳng thức sau đây thường được gọi là đẳng thức Vandermonde (Vandermonde’s convolution formula), là trường hợp đặc biệt của đẳng thức Chu-Vandermonde trong lý thuyết chuỗi siêu hình học (hypergeometric series):

\sum_{i=0}^k \binom{n}{k-i} \binom{m}{i} = \binom{m+n}{k}

Vế phải là tổng số các tập con kích thước k của tập [m+n]. Ta có thể chọn một tập kích thước k bằng cách chọn i phần tử từ [m] và k-i phần tử từ [m+n]-[m]. Đó là đại lượng mà vế trái tính.

Ví dụ 3: với các số nguyên dương i \leq j \leq n, định nghĩa ma trận W_{ij} như sau. Các hàng của W_{ij} được đánh số bằng các tập con kích thước i của [n], các cột tương ứng với các tập con kích thước j. Và,

(W_{ij})_{X,Y} = \begin{cases} 1 & X \subseteq Y \\ 0 & X \not\subseteq Y \end{cases}

Ta sẽ chứng minh rằng A = W_{ij}^TW_{ij} là matrận positive semi-definite, và là positive definite nếu i=j. (Dĩ nhiên, B^TB luôn positive semi-definite vì v^TB^TBv = |Bv|^2, nhưng ta chứng minh bằng cách hơi khác.) Trước hết, với X,Y là các tập con kích thước j của [n], ta có
a_{X,Y} = \binom{|X \cap Y|}{i}

Với vector v \neq 0 bất kỳ (trong không gian thực \binom{n}{j} chiều), ta có
v^TAv = \sum_X \sum_Y \binom{|X \cap Y|}{i} v_Xv_Y

Đến đây, ta sẽ dùng ý tưởng “định trị một đại lượng theo hai cách”. Trong tổng trên, số lần xuất hiện của mỗi cặp v_Xv_Y bằng với tổng số tập con I kích thước i trong phần giao của X và Y. Như vậy, ta có thể viết lại cái tổng trên bằng cách nhóm các số hạng theo I:
v^TAv = \sum_{I : |I| = i} \sum_{X \supseteq I} \sum_{Y \supseteq I} v_Xv_Y

Đến đây thì ta xong vì
v^TAv = \sum_{I : |I| = i} \left( \sum_{X \supseteq I} v_X \right)^2 \geq 0

Ví dụ trên xuất hiện trong các chứng minh dùng đại số tuyến tính của định lý Ray-Chaudhuri–Wilson trong lý thuyết thiết kế (Design Theory).

Ví dụ 4: khi nhắc đến ý tưởng “định trị bằng hai cách”, không thể nào không nhắc đến định lý Erdos-Ko-Rado lừng danh và chứng minh của Katona. Định lý Erdos-Ko-Rado phát biểu như sau:

Gọi \mathcal{A} là một bộ các tập con kích thước k của [n] (n \geq 2k) thỏa mãn điều kiện rằng hai thành viên bất kỳ của \mathcal{A} đều giao nhau. Ta có, |\mathcal{A}| \leq \binom{n-1}{k-1}

Chứng minh. Gọi \mathcal{C} là tập tất cả các cách xếp các số 1, \dots, n trên một đường tròn (cyclic order). Có tất cả (n-1)! cách. Ta sẽ định trị đại lượng s sau đây bằng hai cách: tổng số các cặp (A, C) trong đó A \in \mathcal{A}, C \in \mathcal{C}, và các phần tử của A nằm liên tục trên một cung của C.

  • Cách một: với mỗi A \in \mathcal{A}, có tất cả k!(n-k)! đường tròn C chứa A liên tục trên một cung. Do đó, s = |\mathcal{A}| k! (n-k)!
  • Cách hai: với mỗi đường tròn C, có nhiều nhất là k thành viên của \mathcal{A} là cung của đường tròn, do từng cặp trong chúng phải giao nhau. Vì thế, s \leq (n-1)!k

Ta suy ra kết quả |\mathcal{A}| \leq \binom{n-1}{k-1} từ hai cách định trị s như trên. Đẳng thức có thể đạt được bằng cách chọn \mathcal{A} là bộ tất cả các tập con chứa phần tử 1. Ví dụ này cho thấy ta có thể dùng ý tưởng “định trị hai cách” để chứng minh bất đẳng thức.

Chủ đề: Combinatorics | Bình luận »

RSS cho bình luận bài này

Ghi bình luận của bạn