Cho số nguyên dương n và tập hợp S=(1,2,3,...,n). Tìm số các tập con của S không chứa hai số nguyên dương liên tiếp.
Cho số nguyên dương n và tập hợp S=(1,2,3,...,n). Tìm số các tập con của S không chứa hai số nguyên dương liên tiếp.
Số tập con của $ \left \{ 1,2,...,n \right \} $không chứa 2 số nguyên dương liên tiếp cũng chính là số xâu nhị phân kích thước nCho số nguyên dương n và tập hợp S=(1,2,3,...,n). Tìm số các tập con của S không chứa hai số nguyên dương liên tiếp.
Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 28-08-2021 - 14:18
Số tập con của $ \left \{ 1,2,...,n \right \} $không chứa 2 số nguyên dương liên tiếp cũng chính là số xâu nhị phân kích thước n
không có 2 bit 1 liên tiếp. Gọi $S_{n}$ là số xâu nhị phân kích thước n có tính chất như thế thì ta có : $S_{1}=2; S_{2}=3$ và $S_{n}= S_{n-1}+ S_{n-2}$ với $ n\geq 3$.
Thiếu thì phải ạ
TH1: tập con của tập $S_{n+1}$ không chứa n+1: $S_n$
TH2: tập con của tập $S_{n+1}$ chứa $n+1$
Ghép số $n+1$ vào các tập con thỏa điều kiện nhưng không chứa n: được $S_{n-1}$ tập
Tập {n+1}
Nghĩa là: $S_{n+1}=S_n+S_{n-1}+1$
$S_{1}=1; S_{2}=2$
Bài viết đã được chỉnh sửa nội dung bởi Serine: 28-08-2021 - 14:50
Ta thử liệt kê với $n$ nho nhỏ nhé.Thiếu thì phải ạ
TH1: tập con của tập $S_{n+1}$ không chứa n+1: $S_n$
TH2: tập con của tập $S_{n+1}$ chứa $n+1$
Ghép số $n+1$ vào các tập con thỏa điều kiện nhưng không chứa n: được $S_{n-1}$ tập
Tập {n+1}
Nghĩa là: $S_{n+1}=S_n+S_{n-1}+1$
$S_{1}=1; S_{2}=2$
ta
Số tập con của $ \left \{ 1,2,...,n \right \} $không chứa 2 số nguyên dương liên tiếp cũng chính là số xâu nhị phân kích thước n
không có 2 bit 1 liên tiếp. Gọi $S_{n}$ là số xâu nhị phân kích thước n có tính chất như thế thì ta có : $S_{1}=2; S_{2}=3$ và $S_{n}= S_{n-1}+ S_{n-2}$ với $ n\geq 3$. Đây là hệ thức truy hồi tính số Fibonacci nên ta có số tập con thỏa yêu cầu đề bài là :
$S_{n}=F_{n+2}=\frac{\varphi ^{n+2}-\psi ^{n+2}}{\sqrt5}$
với $\varphi =\frac{1+\sqrt5}{2}$ và $\psi =\frac{1-\sqrt5}{2}$
tại sao S1=2 ạ
Số tập con của $ \left \{ 1,2,...,n \right \} $không chứa 2 số nguyên dương liên tiếp cũng chính là số xâu nhị phân kích thước n
không có 2 bit 1 liên tiếp. Gọi $S_{n}$ là số xâu nhị phân kích thước n có tính chất như thế thì ta có : $S_{1}=2; S_{2}=3$ và $S_{n}= S_{n-1}+ S_{n-2}$ với $ n\geq 3$. Đây là hệ thức truy hồi tính số Fibonacci nên ta có số tập con thỏa yêu cầu đề bài là :
$S_{n}=F_{n+2}=\frac{\varphi ^{n+2}-\psi ^{n+2}}{\sqrt5}$
với $\varphi =\frac{1+\sqrt5}{2}$ và $\psi =\frac{1-\sqrt5}{2}$
Cho mình hỏi vì sao có: Sn=Fn+2
Cho mình hỏi vì sao có: Sn=Fn+2
$S_1=F_3, S_2=F_4$
$S_{n}= S_{n-1}+ S_{n-2}$
$F_{n}= F_{n-1}+ F_{n-2}$
$\Rightarrow S_n=F_{n+2}$
0 thành viên, 0 khách, 0 thành viên ẩn danh