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

Hôm qua một phần bài giảng lớp randomized algorithms đẫn đến chứng minh đẳng thức sau đây:

$\sum_{j=1}^m j \binom{2m}{m+j} = m\binom{2m-1}{m-1}$

Có thể chứng minh đẳng thức này bằng cách viết lại vế trái thành

$\frac 1 2 \sum_{j=1}^m 2j \binom{2m}{m+j} = \frac 1 2 \sum_{j=1}^m \left( (m+j) \binom{2m}{m+j} – (m-j)\binom{2m}{m-j}\right)$

Sau đó, chú ý rằng $k\binom{n}{k} = n \binom{n-1}{k-1}$ , ta khai triển tiếp thành:

$m \sum_{j=1}^m \binom{2m-1}{m+j-1} – m \sum_{j=1}^{m-1} \binom{2m-1}{m-j-1} = m\binom{2m-1}{m-1}$

Đẳng thức cuối cùng có được là do $\binom{2m-1}{m+j-1} = \binom{2m-1}{m-j}$ . Có cách nào chứng mình đẳng thức đầu tiên nhanh gọn và trực quan hơn không?

Xét tập $S = \{1,\dots,2m\}$ . Vế phải $m\binom{2m-1}{m-1}$ đếm tổng số cách chọn một tập con gồm số từ , sao cho trong có một số thuộc $\{m+1,\dots,2m\}$ tô màu xanh và m-1 số còn lại tô màu đỏ. Một tập như vậy có thể được chọn bằng cách chọn một tập con kích thước $j\geq 1$ từ $\{m+1,\dots,2m\}$ trước, tô một phần tử màu xanh, phần còn lại đỏ, và chọn một tập con kích thước m-j từ $\{1,\dots,m\}$ . Như thế ta chứng minh được một đẳng thức … khác:

$\sum_{j=1}^m j\binom{m}{j} \binom{m}{m-j} = m\binom{2m-1}{m-1}$

Chuyện này khá thường xảy ra khi làm nghiên cứu và giảng dạy. Các “khám phá” nho nhỏ như vậy là các bài tập về nhà tốt. Đẳng thức trên, sau khi viết lại một chút, dễ thấy là trường hợp đặc biệt của đẳng thức Chu-Vandermonde mà ta đã đề cập trong phần 1 chuỗi bài này.

Hừm, quay lại với đẳng thức đầu tiên. Làm thế nào để “phiên dịch” vế trái? Trước hết, ta viết lại đẳng thức để vế phải có diễn dịch “sạch” hơn.

$\sum_{j=1}^m 2j \binom{2m}{m+j} = 2m\binom{2m-1}{m}$

Vế phải đếm tổng số tập hợp $T\subset S$ gồm m+1 phần tử trong đó có một phần tử được tô màu đỏ. Vế trái đếm tổng số các tấp hợp $R\subseteq S$ thỏa mãn: (a) $|R| \geq m+1$ , và (b) một trong số 2(|R|-m) phần tử lớn nhất của được tô màu đỏ.

Tôi tìm được một song ánh (bijection) từ bộ các tập vào bộ các tập , nhưng song ánh này hơi phức tạp. Cũng có thể dùng nguyên lý involution của Garcia-Milne, nhưng như vậy song ánh cũng không được trực tiếp.

Lạ thật, một đẳng thức đơn giản như vậy mà tôi không tìm được một song ánh đơn giản. Bạn có tìm được không?

Chủ đề : Combinatorics. Bookmark the permalink. Trackbacks are closed, but you can post a comment.

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

Post a Comment

Thông điệp ngắn

Phản hồi mới

Bài mới

Thư khố

Chuyên Mục

Báo chí

Bảo mật

Blog Việt

Chưa phân loại

Giáo dục

Kỹ thuật

Khoa học khác

Kinh tế, luật pháp, xã hội

Lý thuyết & thuật toán

Toán học

Vật Lý