Chủ đề này có 4 trả lời

[laquochiep3665]

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.

[toannguyenebolala]

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

[toannguyenebolala]

Khỉ gió, hình như sai chỗ nào rồi thì phải, ai chỉnh lại với ạ   

[hxthanh]

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.

Xét tập con $k$ phần tử thỏa yêu cầu đề $\{a_1,a_2,...,a_k\}$
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]

Mình đã sửa lại bài