Gọi [TEX]X_n[/TEX] là số cách sắp xếp n người thỏa mãn đề bài (coi như [TEX]X_0[/TEX]=1 vì khi không có người nào đứng thì chỉ có một cách sắp xếp duy nhất )
Giả sử chiều cao của n người trên lần lượt là [TEX]a_1;a_2;...;a_n[/TEX]sao cho với [TEX]i<j \Rightarrow a_i<a_j[/TEX]
Khi đó; giả sử người có chiều cao là [TEX]a_1[/TEX] đứng ở vị trí thứ k [tex](0\leq k\leq n)[/tex] thì mỗi người đứng ở vị trí từ 1→k luôn cao hơn tất cả những người đứng trước vì nếu ngược lại thì tồn tại một người có chiều cao nhỏ hơn a1 (vô lý) ⇒ người đứng ở vị trí thứ 1 là người cao nhất và có chiều cao [TEX]a_n[/TEX]
Tương tự; người đứng ở vị trí thứ 2 có chiều cao là [tex]a_{n-1}[/tex]
người đứng ở vị trí thứ 3 có chiều cao là [TEX]a_{n-2}[/TEX]
.............
người đứng ở vị trí thứ k - 1 có chiều cao là [tex]a_{n-k}[/tex]
Do đó với mọi [tex]0\leq k\leq n[/tex] thì chỉ có một cách sắp sếp những người đứng ở vị trí từ 1 đến k sao cho thỏa mãn đề bài. Từ đó suy ra số cách sắp xếp n người thỏa mãn đề bài khi người thấp nhất (có chiều cao [TEX]a_1[/TEX]) đứng ở vị trí thứ k chính bằng số cách sắp xếp [tex]n-k[/tex] người đứng từ vị trí thứ k+1 trở đi (=[tex]X_{n-k}[/tex] ).
Vì vậy; khi cho k lần lượt bằng [tex]n,n-1,...,1[/tex] thì ta nhận được số cách sắp xếp n người lần lượt là [tex]X_0,X_1,...,X_{n-1}[/tex]
Mà tổng số cách sắp xếp n người bằng tổng các số trên nên [tex]X_n=X_0+X_1+...+X_{n-1}[/tex]
Lại có [tex]X_0=1,X_1=1\Rightarrow X_n=2^{n-1}[/tex]
Thay n = 10 ta có [tex]X_n=2^9=512[/tex]
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
