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

[HUYVAN]

Tìm số tất cả các tập hợp con khác rỗng của tập ={1,2,...,n} sao cho trong mỗi tập con đó không có hai số nào liên tiếp nhau.

[HUYVAN]

Bài này quy nạp theo n là ra ngay.

Bạn post lời giải lên đi!

[chuyentoan]

Ký hiệu http://dientuvietnam...mimetex.cgi?f(n) là số tập con của http://dientuvietnam...mimetex.cgi?S_n mà không có hai số nào liên tiếp nhau. Ta phải tìm một hệ thức truy hồi cho dãy http://dientuvietnam...mimetex.cgi?f(n). Vậy là xong

[HUYVAN]

Ký hiệu http://dientuvietnam...mimetex.cgi?f(n) là số tập con của http://dientuvietnam...mimetex.cgi?S_n mà không có hai số nào liên tiếp nhau. Ta phải tìm một hệ thức truy hồi cho dãy http://dientuvietnam...mimetex.cgi?f(n). Vậy là xong

Tìm hệ thức truy hồi đó như thế nào?

[manutd]

gọi tập các tập con của http://dientuvietnam...mimetex.cgi?S_n thỏa mãn là http://dientuvietnam...imetex.cgi?X_n. Xét một tập http://dientuvietnam...n/mimetex.cgi?X thuộc http://dientuvietnam...imetex.cgi?X_n. Nếu phần tử lớn nhất của http://dientuvietnam...n/mimetex.cgi?X bằng http://dientuvietnam...n/mimetex.cgi?n thì http://dientuvietnam...n/mimetex.cgi?X không chứa http://dientuvietnam...mimetex.cgi?n-1 suy ra http://dientuvietnam...metex.cgi?X/{n} thuộc http://dientuvietnam...tex.cgi?X_{n-2}, trường hợp còn lại http://dientuvietnam.net/cgi-bin/mimetex.cgi?X thuộc http://dientuvietnam.net/cgi-bin/mimetex.cgi?X_{n-1}. Thành thử ta có công thức truy hồi http://dientuvietnam.net/cgi-bin/mimetex.cgi?f(n)=f(n-1)+f(n-2)

[HUYVAN]

suy ra http://dientuvietnam...metex.cgi?X/{n} thuộc http://dientuvietnam...tex.cgi?X_{n-2}

Chỗ này là sao?

[lehoan]

Bài toán tổng quát:Cho số nguyên dương http://dientuvietnam...n/mimetex.cgi?k tìm số tập hợp con http://dientuvietnam...n/mimetex.cgi?A của http://dientuvietnam.net/cgi-bin/mimetex.cgi?\{1,2,...,n\} sao cho không có hai phần tử http://dientuvietnam...n/mimetex.cgi?p và http://dientuvietnam...mimetex.cgi?k=1 là bài toán ban đầu của bạn.

Bây giờ với mỗi tập http://dientuvietnam...n/mimetex.cgi?A có tính chất trên thì ta sắp thứ tự các phần tử trong http://dientuvietnam...n/mimetex.cgi?A là http://dientuvietnam.net/cgi-bin/mimetex.cgi?A=\{p_1<p_2<...<p_m\}. Khi đó ta có http://dientuvietnam...gi?q_i=p_i-(i-1)k ta có http://dientuvietnam...cgi?q_{i 1}>q_i suy ra http://dientuvietnam.net/cgi-bin/mimetex.cgi?B=\{q_1;q_2;...;q_m\} là tập con của http://dientuvietnam.net/cgi-bin/mimetex.cgi?\{1;2;...;n-(m-1)k\}.

Như vậy có tất cả tập con