cho tập $A=\left \{ 1;2;3;...;n \right \}$ hỏi có bao nhiêu tập con của A khác rỗng không có 2 số liền kề nhau.
cho tập $A=\left \{ 1;2;3;...;n \right \}$ hỏi có bao nhiêu tập con của A khác rỗng không có 2 số liền kề nhau.
#1
Đã gửi 14-09-2017 - 18:30
#2
Đã gửi 14-09-2017 - 22:57
cho tập $A=\left \{ 1;2;3;...;n \right \}$ hỏi có bao nhiêu tập con của A khác rỗng không có 2 số liền kề nhau.
Trước hết, ta sẽ chứng minh rằng số tập hợp con, kể cả tập rỗng của một tập hợp n phần tử là $2^{n}$
Áp dụng Nhị thức Newton, ta có $(1+x)^{n}=\sum_{k=0}^{n}C_{n}^{k}x^{k}=C_{n}^{0}+C_{n}^{1}x+...+C_{n}^{n}x^n$
Mà số tập hợp con của một tập hợp n phần tử (kể cả tập rỗng) là $C_{n}^{0}+C_{n}^{1}+...+C_{n}^{n}=(1+1)^{n}=2^n$.
Giờ ta sẽ đi tìm số tập hợp con của A có 2 số liền kề nhau. Nhận thấy:
*Số tập hợp con có 2 phần tử: $C_{n-2}^{0}+C_{n-3}^{0}+...+C_{0}^{0}$
*Số tập hợp con có 3 phần tử: $C_{n-2}^{1}+C_{n-3}^{1}+...C_{0}^{1}$
...
*Số tập hợp con có n-1 phần tử: $C_{n-2}^{n-3}+C_{n-3}^{n-3}$
*Số tập hợp con có n phần tử: $C_{n-2}^{n-2}$
Vậy, số tập con thuộc loại này là $(C_{n-2}^{0}+C_{n-2}^{1}+...+C_{n-2}^{n-2})+(C_{n-3}^{0}+C_{n-3}^{1}+...+C_{n-3}^{n-3})+...+C_{0}^{0}=2^{n-2}+2^{n-3}+...+2^{0}=2^{n-1}-1$
Như vậy, có tất cả $2^n-(2^{n-1}-1)-1=2^{n}-2^{n-1}=2^{n-1}$ tập hợp con của A thỏa mãn yêu cầu bài toán
Bài viết đã được chỉnh sửa nội dung bởi toannguyenebolala: 15-09-2017 - 11:37
"Đừng khóc, Alfred! Anh cần có đủ nghị lực để chết ở tuổi hai mươi"
#3
Đã gửi 14-09-2017 - 23:06
Khỉ gió, hình như sai chỗ nào rồi thì phải, ai chỉnh lại với ạ
"Đừng khóc, Alfred! Anh cần có đủ nghị lực để chết ở tuổi hai mươi"
#4
Đã gửi 14-09-2017 - 23:59
Xét tập con $k$ phần tử thỏa yêu cầu đề $\{a_1,a_2,...,a_k\}$cho tập $A=\left \{ 1;2;3;...;n \right \}$ hỏi có bao nhiêu tập con của A khác rỗng không có 2 số liền kề nhau.
Ta có:$1\leq a_1<a_2-1<...<a_k-k+1\leq n-k+1$
Có $C_{n-k+1}^k$ tập con như vậy.
Số tập con cần tìm là
$S=\sum_{1\leq k \leq \left\lfloor\frac{n+1}{2}\right\rfloor} C_{n+1-k}^k=F_{n+2}-1$
($\{F_n\}$ là dãy Fibonacci, Bạn tự tính nhé!)
- toannguyenebolala yêu thích
#5
Đã gửi 15-09-2017 - 11:38
Mình đã sửa lại bài
"Đừng khóc, Alfred! Anh cần có đủ nghị lực để chết ở tuổi hai mươi"
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh