1/ Tính số tập con của $ \left \{ 1,2,...,n \right \} $ không chứa 2 số liên tiếp.
#1
Đã gửi 31-07-2023 - 17:58
2/ Từ tập $ \left \{ 1,2,...,n \right \} $ tính số cách chọn 2 tập con rời nhau và khác trống.
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...
#2
Đã gửi 01-08-2023 - 13:57
2/Em lập luận như sau :
Xét một cặp 2 tập con rời nhau bất kỳ, có thứ tự $(A,B)$ thuộc $ \left \{ 1,2,...,n \right \} $ và ta sẽ biểu diễn bằng các xâu $e_1e_2....e_n $ trên $ \left \{ 0,1,2\right \} $ được định nghĩa như sau :
$e_k=\begin {cases}0,&\text{ nếu $k \notin A\cap B$ }\\
1,&\text{ nếu $k \in A$}\\
2&\text{ nếu $k \in B$ }
\end {cases}$
Ta có $A= \left \{ \right \} $ nếu và chỉ nếu xâu biểu diễn là xâu trên $ \left \{ 0,2\right \} $ và $B= \left \{ \right \} $ nếu và chỉ nếu xâu biểu diễn là xâu trên $ \left \{ 0,1\right \} $. Trong số $3^n$ xâu kích thước n, có $2^n$ xâu trên $ \left \{ 0,1\right \} $,có $2^n$ xâu trên $ \left \{ 0,2\right \} $ và có 1 xâu trên $ \left \{ 0\right \}$. Do đó, số cặp tập con thứ tự, rời nhau thuộc $ \left \{ 1,2,....,n\right \} $ là $3^n-2\cdot2^n+1$ suy ra số tập con không thứ tự thỏa yêu cầu là $$\color {blue} {\frac {1}{2}(3^n+1)-2^n}$$
Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 01-08-2023 - 16:04
- E. Galois, hxthanh và chanhquocnghiem thích
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
Đã gửi 01-08-2023 - 16:07
1/ Tính số tập con của $ \left \{ 1,2,...,n \right \} $ không chứa 2 số liên tiếp.
Trước hết, ta tính số tập con của $\left \{ 1,2,3,...,n \right \}$ có đúng $k$ số và không chứa 2 số liên tiếp.
Giả sử $k$ số đó là $x_{1},x_{2},x_{3},...,x_{k}$ thỏa mãn $1\leqslant x_{1}< x_{2}< x_{3}<...< x_{k}\leqslant n$
với $\left | x_i-x_j \right |\geqslant 2$
Đặt $a_{i}=x_{i}-(i-1)$ suy ra $1\leqslant a_1< a_2< a_3<...< a_k\leqslant n-k+1$
Số cách chọn $k$ số từ tập đã cho chính là số cách chọn $k$ số $a_{i}$ và bằng $C_{n-k+1}^{k}$
Vậy số tập con có đúng $k$ số và không chứa 2 số liên tiếp là $C_{n-k+1}^{k}$.
$\Rightarrow$ số tập con không chứa 2 số liên tiếp là $\sum_{k=0}^{\left \lfloor \frac{n+1}{2} \right \rfloor}C_{n-k+1}^k$
...
Ðêm nay tiễn đưa
Giây phút cuối vẫn còn tay ấm tay
Mai sẽ thấm cơn lạnh khi gió lay
Và những lúc mưa gọi thương nhớ đầy ...
#4
Đã gửi 01-08-2023 - 16:26
$\color {blue} {\frac{1}{\sqrt5}\left ( \left ( \frac{1+\sqrt5}{2} \right )^{n+2}-\left ( \frac{1-\sqrt5}{2} \right )^{n+2} \right ) } $
Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 02-08-2023 - 08:01
- chanhquocnghiem yêu thích
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
Đã gửi 01-08-2023 - 16:30
Gọi $S_n$ là số cần tìm1/ Tính số tập con của $ \left \{ 1,2,...,n \right \} $ không chứa 2 số liên tiếp.
Số tập con thoả mãn mà không chứa $n$ chính là $S_{n-1}$
Số tập con thoả mãn mà chứa $n$ chính là $S_{n-2}$
Nghĩa là $S_n=S_{n-1}+S_{n-2}$
Với $n=1$ thì $S_1=2$ ($\{1\}$ và $\emptyset$)
Do đó $S_n=F_{n+2}$
- E. Galois, chanhquocnghiem, Nobodyv3 và 1 người khác yêu thích
#6
Đã gửi 01-08-2023 - 16:33
2/ Từ tập $ \left \{ 1,2,...,n \right \} $ tính số cách chọn 2 tập con rời nhau và khác trống.
Xét 2 tập con rời nhau (không giao nhau) $A$ và $B$.
Mỗi phần tử có $3$ khả năng : hoặc thuộc $A$, hoặc thuộc $B$, hoặc không thuộc $A\cup B$
$\Rightarrow$ có tất cả $3^n$ cách chọn 2 tập con $A$ và $B$ rời nhau. Trong đó :
+ Có $2^n$ cách mà trong đó tập $A$ rỗng.
+ Có $2^n$ cách mà trong đó tập $B$ rỗng.
+ Có $1$ cách mà trong đó cả $A$ và $B$ đều rỗng.
Vậy số cách chọn 2 tập con rời nhau, không phân biệt thứ tự và khác rỗng là $\frac{3^n-2.2^n+1}{2}$.
- E. Galois, hxthanh, Nobodyv3 và 1 người khác yêu thích
...
Ðêm nay tiễn đưa
Giây phút cuối vẫn còn tay ấm tay
Mai sẽ thấm cơn lạnh khi gió lay
Và những lúc mưa gọi thương nhớ đầy ...
#7
Đã gửi 01-08-2023 - 16:47
@chanhquocnghiem Thử vài giá trị n=1,2,3 em thấy kết quả hình như chưa ổn lắm...
Tdụ : n=3:
$\sum_{k=0}^{\left \lfloor \frac{n+1}{2} \right \rfloor}C_{n-k+1}^k=\sum_{k=0}^{2}C_{4-k}^k=C_4^0+C_3^1+C_2^2=1+3+1=5$
Đúng là có $5$ tập con không chứa 2 số liên tiếp mà, đó là các tập :
$\left \{ 1 \right \},\left \{ 2 \right \},\left \{ 3 \right \},\left \{ 1,3 \right \}$ và tập rỗng.
...
Ðêm nay tiễn đưa
Giây phút cuối vẫn còn tay ấm tay
Mai sẽ thấm cơn lạnh khi gió lay
Và những lúc mưa gọi thương nhớ đầy ...
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh