Tìm số các hoán vị $(a_1, a_2,..., a_{2009})$ của $(1, 2, 3,..., 2009)$ thỏa mãn tính
chất: tồn tại đúng một chỉ số $i\in \{1,2,3,...,2008\}$ sao cho $a_i > a_{i+1}$.
#2
Đã gửi 04-05-2008 - 19:18
MyLoveIs4Ever
-
- Thành viên
-
- 441 Bài viết
Sĩ quan
Cho đến n cho đánh đỡ mỏi tay :
Giả sử số hoán vị cần tìm là $ S_n $
Chia $ S_n $ ra làm 2 tập
. Tập gồm các hoán vị có $ a_n=n $ : cái nì có $ S_{n-1} $
. Tập gồm các hoán vị có $ n $ ở vị trí thứ k ( tức a_k ) thì mỗi trường hợp có số hoán vị là số cach sắp xếp $ n-k $ số sau $ n $ ( $ k $ chạy từ 1 -> n-1
HAY TA Có; : $ S_n= S_{n-1}+2^{n-1}-1 $ Dùng sai phân để tìm ^^!
Giả sử số hoán vị cần tìm là $ S_n $
Chia $ S_n $ ra làm 2 tập
. Tập gồm các hoán vị có $ a_n=n $ : cái nì có $ S_{n-1} $
. Tập gồm các hoán vị có $ n $ ở vị trí thứ k ( tức a_k ) thì mỗi trường hợp có số hoán vị là số cach sắp xếp $ n-k $ số sau $ n $ ( $ k $ chạy từ 1 -> n-1
HAY TA Có; : $ S_n= S_{n-1}+2^{n-1}-1 $ Dùng sai phân để tìm ^^!
Bài viết đã được chỉnh sửa nội dung bởi MyLoveIs4Ever: 04-05-2008 - 21:49
#3
Đã gửi 04-05-2008 - 23:21
zaizai
-
- Thành viên
-
- 1380 Bài viết
Tiến sĩ diễn đàn toán
Trình bày rõ ràng hơn đc ko? 
#4
Đã gửi 05-05-2008 - 03:08
ctlhp
-
- Thành viên
-
- 375 Bài viết
Đức Thành
bài này giải vậy là đúng rồi j nữa khi $ n$ vị trí $ 1\leq k<n$ thì số xếp chính là số cách chọn $ k$ số bất kỳ từ $\ n-1$ thằng còn lại (=$ C^{k}_{n-1}$ xếp theo chiều tăng từ trái qua phải ở block 1. sau đấy đám còn lại cũng xếp theo chiều tăng từ trái qua phải ở block 2. 2 block ngăn cách bởi $ n$ khi đó $ S_{n}=S_{n-1}+\sum_{k =1}^{n-1}\ C_{n-1}^{k}=S_{n-1}+2^{n-1}-1$
khi $ n$ vị trí $ 1\leq k<n$ thì số xếp chính là số cách chọn $ k$ số bất kỳ từ $\ n-1$ thằng còn lại (=$ C^{k}_{n-1}$ xếp theo chiều tăng từ trái qua phải ở block 1. sau đấy đám còn lại cũng xếp theo chiều tăng từ trái qua phải ở block 2. 2 block ngăn cách bởi $ n$ khi đó $ S_{n}=S_{n-1}+\sum_{k =1}^{n-1}\ C_{n-1}^{k}=S_{n-1}+2^{n-1}-1$
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh
