Bài toán tổ hợp liên quan đến dãy số

[Ma Tian Yu FC]

Bài 1: Tồn tại bao nhiêu hoán vị $f$ của $\left \{ 1,2,...,n \right \}$ sao cho $|f(k)-k|\leq 1$ với $k\in \left \{ 1,2,...,n \right \}$

Bài 2: Có bao nhiêu cách phủ kín hình chữ nhật $2\times n$ bởi các quân đomino $2\times 1$ và $2\times 2$

Bài 3: Có bao nhiêu cách chia hình chữ nhật $2\times n$ thành các hình chữ nhật có cạnh là các số nguyên dương
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[Lucifer1998]

Nguyên văn bởi Ma Tian Yu FC

Bài 1: Tồn tại bao nhiêu hoán vị $f$ của $\left \{ 1,2,...,n \right \}$ sao cho $|f(k)-k|\leq 1$ với $k\in \left \{ 1,2,...,n \right \}$

$f(k)$ là cái gì vậy bạn?
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[Ma Tian Yu FC]

$f(k)$ ( $k=1,2,3,...,n$ ) là hoán vị của tập $\left \{ 1,2,...,n \right \}$

Mình viết lại đề bài như thế này, chắc sẽ dễ hiểu hơn

Tìm số hoán vị $(a_1,a_2,....,a_n)$ của tập $\left \{1,2,....,n \right \}$ thỏa mãn
$|a_n-n|\leq 1$
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[vuxuandh]

Bài 1
Gọi $S(n)$ là số hoán vị thỏa mãn, $S(n) = S(n-1) + S(n - 2)$.
Domino 2.1 với 2.2 có phải L và V domino ko ah
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[Ma Tian Yu FC]

Nguyên văn bởi vuxuandh

Bài 1
Gọi $S(n)$ là số hoán vị thỏa mãn, $S(n) = S(n-1) + S(n - 2)$.
Domino 2.1 với 2.2 có phải L và V domino ko ah

Bạn có thể trình bày cụ thể bài 1 không?
Domino $2\times 1$ và $2\times 2$ không phải L, V đâu nhé bạn
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[vuxuandh]

Gọi $S(n)$ là số hoán vị thỏa mãn ứng với $n$. Ta có $f(n)=n$ hoặc $f(n) =n-1$.
Nếu $f(n)=n$, số hoán vị trường hợp này là $S(n-1)$.
Nếu $f(n)=n-1$ thì $f(n-1)=n$, số hoán vị trong trường hợp này là $S(n-2)$.
Suy ra $S(n)=S(n-1)+S(n-2)$. Đây là dãy Fibonacy.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[vuxuandh]

Bài 3
Chia hình chữ nhật $2\times n$ thành $n$ cột
Gọi $S_n$ là số cách phủ hình chữ nhật$2\times n$ bởi các hình chữ nhật cạnh nguyên, $A_n$ là số cách phủ hình chữ nhật $2\times n$ mà cột thứ $n$ nằm trong một hình chữ nhật nào đó, $B_n$ là số cách phủ hình chữ nhật $2\times n$ mà cột $n$ không nằm trong hình chữ nhật nào. Ta có:
$S_n=A_n+B_n$
$A_{n+1}=2A_n+B_n$
$B_{n+1}=A_n+4B_n$
Suy ra hệ
$S_{n+1}=3S_n+2B_n$
$B_{n+1}=S_n+3B_n$
Với chú ý $S_1=2, B_1=1$, giải hệ ta có
$$S_{n+1}=\dfrac{(3+\sqrt{2})^n .(2+\sqrt{2})+(3-\sqrt{2})^n .(2-\sqrt{2})}{2}$$
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]