Math Labs

Bài 2

Cho nn và rr là các số nguyên với 1≤r≤n1 \le r \le n, xét tất cả (nr)\binom{n}{r} tập con gồm rr phần tử của tập {1,2,…,n}\{1,2,\dots,n\}. Mỗi tập con như vậy có một phần tử nhỏ nhất. Gọi F(n,r)F(n,r) là trung bình cộng của các phần tử nhỏ nhất đó. Chứng minh rằng F(n,r)=n+1r+1.F(n,r) = \frac{n+1}{r+1}.
Bước 1 trên 5: Viết tổng các phần tử nhỏ nhất
Bước trướcBước tiếp
Hiểu nôm na

Thay vì tính trung bình trực tiếp, hãy nhóm các tập con theo giá trị nhỏ nhất và đếm xem có bao nhiêu tập con chung một giá trị nhỏ nhất.

∑Smin⁡(S)=∑k=1nk(n−kr−1)\sum_{S} \min(S) = \sum_{k=1}^{n} k\binom{n-k}{r-1}
Phân tích chi tiết

Với kk cố định, số tập con rr phần tử của {1,…,n}\{1,\dots,n\} có phần tử nhỏ nhất bằng kk là (n−kr−1)\binom{n-k}{r-1}, vì r−1r-1 phần tử còn lại phải chọn từ n−kn-k số lớn hơn kk. Nhân với kk rồi lấy tổng theo mọi giá trị nhỏ nhất có thể ta được tổng các phần tử nhỏ nhất trên mọi tập con rr phần tử.