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

[ilovezu123]

Với $n$ là số nguyên dương, một tập con của tập $\begin{Bmatrix} 1,2,3,...,n \end{Bmatrix}$ được gọi là tốt nếu sau khi ta sắp xếp thứ tự tăng các phần tử của nó thì thu được các số lẻ , chẵn ,lẻ theo thứ tự.

Ví dụ các tập con tốt là $\begin{Bmatrix} 1,4,5,6 \end{Bmatrix} , \begin{Bmatrix} 3,4,7 \end{Bmatrix}$, tập rỗng,tập $\begin{Bmatrix} 2,3,4,7 \end{Bmatrix}$ không là tập tốt do bắt đầu bằng số chẵn.

Tính số tập con tốt của $\begin{Bmatrix} 1,2,3,...,n \end{Bmatrix}$

[bangbang1412]

Tập rỗng với một phần tử cũng tính chứ gì bạn ?

[ilovezu123]

Tập rỗng với một phần tử cũng tính chứ gì bạn ?

không tính tập rỗng,tính tập 1 phần tử bạn

[hxthanh]

Với $n$ là số nguyên dương, một tập con của tập $\begin{Bmatrix} 1,2,3,...,n \end{Bmatrix}$ được gọi là tốt nếu sau khi ta sắp xếp thứ tự tăng các phần tử của nó thì thu được các số lẻ , chẵn ,lẻ theo thứ tự.

Ví dụ các tập con tốt là $\begin{Bmatrix} 1,4,5,6 \end{Bmatrix} , \begin{Bmatrix} 3,4,7 \end{Bmatrix}$, tập rỗng,tập $\begin{Bmatrix} 2,3,4,7 \end{Bmatrix}$ không là tập tốt do bắt đầu bằng số chẵn.

Tính số tập con tốt của $\begin{Bmatrix} 1,2,3,...,n \end{Bmatrix}$

Gọi:

$S_n$ là tập hợp các tập con tốt của tập $\{1,2,...,n\}$ (Ta cần tính $|S_n|$)

Chia $S_n$ ra thành 2 tập hợp $S_n=E_n\cup O_n$

$E_n$ là tập bao gồm các tập con tốt có số phần tử chẵn (ta sẽ gọi tắt là các tập chẵn)

$O_n$ là tập bao gồm các tập con tốt có số phần tử lẻ (ta sẽ gọi tắt là các tập lẻ)

Ta dễ dàng lập được các đẳng thức sau:

\begin{equation} \label{e1} |S_n|=|E_n|+|O_n|\end{equation}

\begin{equation} \label{e2} |S_{2n+1}|=|S_{2n}|+|E_{2n}|+1\end{equation}

\begin{equation} \label{e3} |S_{2n+2}|=|S_{2n+1}|+|O_{2n+1}|\end{equation}

\begin{equation} \label{e4} |O_{2n+1}|=|E_{2n}|+|O_{2n}|+1=|S_{2n}|+1\end{equation}

\begin{equation} \label{e5} \Rightarrow |S_{n+2}|=|S_{n+1}|+|S_{n}|+1\end{equation}

\begin{equation} \label{e6} \Rightarrow |S_{n}|=|F_{n+2}|-1,\quad(F_n:\;\text{Dãy Fibonacci})\end{equation}

$\eqref{e1}$ là hiển nhiên.

$\eqref{e2}$ Xây dựng tập các tập con tốt của $\{1,2,...,2n, 2n+1\}$ từ $\{1,2,...,2n\}$ và phần tử $(2n+1)$

Các tập con tốt có số chẵn phần tử thì phần tử lớn nhất phải là số chẵn theo định nghĩa, mỗi tập đó được thêm phần tử$(2n+1)$ sẽ tạo được ra một tập con tốt mới! Ngoài ra thì tập $\{2n+1\}$ cũng là một tập con tốt!

$\eqref{e3}$ Xây dựng tập các tập con tốt của $\{1,2,...,2n+1, 2n+2\}$ từ $\{1,2,...,2n+1\}$ và phần tử $(2n+2)$

Các tập con tốt có số lẻ phần tử thì phần tử lớn nhất phải là số lẻ theo định nghĩa, mỗi tập đó được thêm phần tử$(2n+2)$ sẽ tạo được ra một tập con tốt mới!

$\eqref{e4}$ Bằng cách xây dựng như $\eqref{e2}$ ta thấy rằng các tập lẻ của $S_{2n}$ được bảo toàn qua $S_{2n+1}$ còn các tập chẵn của $S_{2n}$ lại được chuyển thành các tập lẻ của $S_{2n+1}$ kèm thêm tập $\{2n+1\}$

$\eqref{e5}$ là hệ quả của những đẳng thức trên

$\eqref{e6}$ là điều cần tìm