Đáp án của BTC
$\fbox{Đề bài:}$
Từ các chữ số $\{1,2,3,4,5,6,7\}$ lập các số tự nhiên có $4$ chữ số dạng $\overline{abcd}$ sao cho $a>b>c>d$
Tính tổng của tất cả các số tạo thành.
Lời giải:
Ta "tổng quát" hoá bài toán luôn một thể
Cho tập $E=\{1,2,..,n\};\;\;(n\le 9)$. Mỗi tổ hợp gồm $i\;$ phần tử $(1\le i\le n)$ của $E$ là $\{a_1,...,a_i\}$ được sắp giảm dần $(a_1>...>a_i)$ để tạo thành số $\overline{a_1...a_i}$.
Tính $S_{i,n}$ là tổng của tất cả các số đó.
-------
Ta tính tổng $S_{i,n}$ theo nhóm các số có chữ số đầu tiên là $k$
Nếu số có chữ số đầu tiên là $k$ thì $i-1$ chữ số tiếp theo sẽ có các chữ số nhỏ hơn $k$, nghĩa là nó là một tổ hợp $i-1$ phần tử của tập $\{k-1,...,1\}$ được sắp thứ tự giảm dần.
Có $C_{k-1}^{i-1}$ số như vậy. Do đó ta có:
$\Rightarrow S_{i,n}=\sum\limits_{k=i}^n\left(10^{i-1}kC_{k-1}^{i-1}+S_{i-1,k-1}\right)\quad(1)$
$\bullet\quad\text{với } i=1$
ta có: $S_{1,n}=1+2+...+n=C_{n+1}^2\quad(2)$
$\bullet\quad\text{với } i=2$
Theo $(1)$ ta có:
$S_{2,n}=\sum\limits_{k=2}^n\left(10kC_{k-1}^1+S_{1,k-1}\right)$
$S_{2,n}=\sum\limits_{k=2}^n\left(20C_k^2+C_k^2\right)=\sum\limits_{k=2}^n\left(21C_k^2\right)\quad(\text{theo $(2)$ })$
$S_{2,n}=21\sum\limits_{k=2}^n \left(C_{k+1}^3-C_k^3\right)=21C_{n+1}^3\quad(3)$
Từ $(2)$ và $(3)$ ta dự đoán được công thức tổng quát
$\boxed{S_{i,n}=\overline{i...1}C_{n+1}^{i+1} \qquad(4)}$
Thật vậy, ta chứng minh $(4)$ bằng quy nạp theo $i$
Rõ ràng $(4)$ đúng với $i=1,2$
Giả sử $(4)$ đúng đến $i-1$ ta chứng minh $(4)$ cũng đúng với $i$
Từ (1) ta có:
$S_{i,n}=\sum\limits_{k=i}^n\left(10^{i-1}kC_{k-1}^{i-1}+S_{i-1,k-1}\right)$
$S_{i,n}=\sum\limits_{k=i}^n\left(10^{i-1}kC_{k-1}^{i-1}+\overline{i-1 ... 1}C_k^i\right)\quad(\text{Theo giả thiết quy nạp})$
$S_{i,n}=\sum\limits_{k=i}^n\left(10^{i-1}iC_k^i+\overline{i-1 ... 1}C_k^i\right)$
$S_{i,n}=\sum\limits_{k=i}^n\left(\overline{i...1}C_k^i\right)$
$S_{i,n}=\overline{i...1}\sum\limits_{k=i}^n\left(C_{k+1}^{i+1}-C_{k}^{i+1}\right)$
$S_{i,n}=\overline{i...1}C_{n+1}^{i+1}$
Vậy theo nguyên lý quy nạp $(4)$ đúng với mọi $i\le n\le 9$
Áp dụng vào bài toán, ta có:
$S_{4,7}=4321C_8^5=241\,976$