Tìm số cách chia tập $S_{n}$

[Lucifer1998]

Tìm số cách chia tập $S_{n}=\left \{ 1,2,...,n \right \}$ thành 3 tập con khác rỗng (hợp với nhau bằng $S_{n}$ và đôi một rời nhau) sao cho mỗi tập con không chứa 2 số nguyên liên tiếp.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[tikita]

Nguyên văn bởi Lucifer1998

Tìm số cách chia tập $S_{n}=\left \{ 1,2,...,n \right \}$ thành 3 tập con khác rỗng (hợp với nhau bằng $S_{n}$ và đôi một rời nhau) sao cho mỗi tập con không chứa 2 số nguyên liên tiếp.

Gọi $x_n, (n\geq 3)$ là số cách chia $S_n$ thành 3 tập con khác rỗng rời nhau sao cho không có tập con nào chứa hai số nguyên liên tiếp. Ta tính $x_n$ theo $x_{n-1}$ như sau:

• Cứ mỗi cách chia $S_{n-1}$ thành ba tập $A,B,C$ thỏa yêu cầu bài toán, bằng cách thêm vào phần tử $n$ vào một trong hai tập không chứa $n-1$ thì ta được một cách chia cho tập $S_n$. Do đó trong trường hợp này có $2x_{n-1}$ cách chia.

• Nếu $S_{n-1}$ không chia thành 3 tập con thỏa yêu cầu bài toán, thì có duy nhất một cách chia $S_{n-1}$ thành 2 tập con rời nhau sao cho mỗi tập không chứa hai số nguyên liên tiếp. Lấy tập còn lại là $\{n\}$, thì ta được 1 cách chia $S_n$ thỏa yêu cầu bài toán.

Vì vậy ta được $x_3=1$ và $x_{n}=2x_{n-1}+1,\forall n\geq 4.$
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]