Đến nội dung

Hình ảnh

1/ Tính số tập con của $ \left \{ 1,2,...,n \right \} $ không chứa 2 số liên tiếp.

- - - - -

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

#1
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
1/ Tính số tập con của $ \left \{ 1,2,...,n \right \} $ không chứa 2 số liên tiếp.
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
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
@E. Galois : Welcome back, thầy!
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

===========
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
chanhquocnghiem

chanhquocnghiem

    Thiếu tá

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

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 ...

 

http://www.wolframal...-15)(x^2-8x+12)


#4
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
1/ Cho $A\subset\left \{ 1,2,...,n \right \} $...blablabla....kết quả là
$\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

===========
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
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3915 Bài viết

1/ Tính số tập con của $ \left \{ 1,2,...,n \right \} $ không chứa 2 số liên tiếp.

Gọi $S_n$ là số cần tìm
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}$

#6
chanhquocnghiem

chanhquocnghiem

    Thiếu tá

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

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


...

Ðê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 ...

 

http://www.wolframal...-15)(x^2-8x+12)


#7
chanhquocnghiem

chanhquocnghiem

    Thiếu tá

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

@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 ...

 

http://www.wolframal...-15)(x^2-8x+12)





1 người đang xem chủ đề

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