Đến nội dung

Hình ảnh

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

- - - - -

  • Please log in to reply
Chủ đề này có 6 trả lời

#1
wannable

wannable

    Lính mới

  • Thành viên mới
  • 4 Bài viết

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.

 



#2
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết

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 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}$

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 28-08-2021 - 14:18

===========
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...

#3
Serine

Serine

    Hạ sĩ

  • Thành viên
  • 91 Bài viết

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


#4
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết

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 thử liệt kê với $n$ nho nhỏ nhé.
$n=3:$ có các tập thỏa yc là :$\left \{ \right \},\left \{ 1 \right \},\left \{ 2 \right \},\left \{ 3 \right \},\left \{1,3 \right \}\Rightarrow S_{3}=5$
$n=4:$ có các tập thỏa yc là :$\left \{ \right \},\left \{ 1 \right \},\left \{ 2 \right \},\left \{ 3 \right \},
\left \{4 \right \}, \left \{1,3 \right \},\left \{1,4 \right \},\left \{2,4 \right \} \Rightarrow S_{4}=8.$
..v.v...
Bạn thử dùng kết quả của bạn để tính xem dư, thiếu ra sao ...
===========
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...

#5
wannable

wannable

    Lính mới

  • Thành viên mới
  • 4 Bài viết

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 ạ 



#6
netcomath

netcomath

    Binh nhất

  • Thành viên mới
  • 21 Bài viết

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



#7
Serine

Serine

    Hạ sĩ

  • Thành viên
  • 91 Bài viết

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 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh