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

Ngô Quang Hưng | 30 tháng 09, 2008 | Bản để in Bản để in

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 T gồm m số từ S, sao cho trong T 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 T 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 R được tô màu đỏ.

Tôi tìm được một song ánh (bijection) từ bộ các tập R vào bộ các tập T, 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 | Bình luận »

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

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