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

[Trần Đức Anh @@]

Problem: $a_n$ kí hiệu là số tập con không rỗng của $S$ thỏa mãn rằng:
(i) $S\subseteq${$1$, $2$, $...$, $n$};
(ii) tất cả các phần tử của $S$ đều cung tính chẵn, lẻ.
(iii) mỗi phân tử $k\in{S}$ thỏa mãn $k\geq2|S|$.
Tìm công thức tường minh cho $a_n$

Bài viết đã được chỉnh sửa nội dung bởi Trần Đức Anh @@: 15-07-2012 - 20:36

[Stranger411]

Problem: $a_n$ kí hiệu là số tập con không rỗng của $S$ thỏa mãn rằng:
(i) $S\subseteq${$1$, $2$, $...$, $n$};
(ii) tất cả các phần tử của $S$ đều cung tính chẵn, lẻ.
(iii) mỗi phân tử $k\in{S}$ thỏa mãn $k\geq2|S|$.
Tìm công thức tường minh cho $a_n$

Bài này lâu rồi, sử dụng phép chia nhóm là được

Ta có: $ a_{2m-1}= 2(F_{m+1}-1) $ và $ a_{2m}= F_{m+3}-2 $
với $m\ge1$ và $F_{m}$ là số Fibonacci thứ $m$.

Lời giải:
Đặt $T_{n}=\{S\in\{1,2,\cdots,n\}\}$ thỏa $(ii)$ và $(iii)$
Chia $ T_{n+4} $ thành 3 tập con:

Phần 1: $A_{n+4}=\{S\in T_{n+4}\ ;\ 1,2\notin S,\ \forall k\in S, k\geq 2|S|+2\}$
Xây dựng $ f\ :\ \mathcal{P}(\{1,2,\cdots,n+2\})\rightarrow\mathcal{P}(\{1,2,\cdots,n+4\}) $ thỏa:
$$f(\{x_{1},x_{2},\cdots,x_{k}\}) =\{x_{1}+2,x_{2}+2,\cdots,x_{k}+2\}$$
Ta được: $ f(T_{n+2}) = A_{n+4} $ nên $ |A_{n+4}|=|T_{n+2}|$

Phần 2: $ B_{n+4}=\{S\in T_{n+4}\ ;\ 1,2\notin S,\ \exists k\in S, k < 2|S|+2\} $
Tương tự, ta được:
$f(\phi) =\{3\}$
$f\left( {\left\{ {{x_1},{x_2},...,{x_k}} \right\}} \right) = \left\{ {{x_1} + 4,{x_2} + 4,...,{x_k} + 4,2k} \right\}$
nếu các phần tử cùng chẳn.
$f\left( {\left\{ {{x_1},{x_2},...,{x_k}} \right\}} \right) = \left\{ {{x_1} + 4,{x_2} + 4,...,{x_k} + 4,2k+1} \right\}$
nếu các phần tử cùng lẽ.
Suy ra: $|B_{n+4}|=|T_{n}|+1 $

Phần 3: $ C_{n+4}=\{ S\in T_{n+4}\ ;\ 1\in S\ \mathrm{or}\ 2\in S\} $
Tương tự, ta có: $ |T_{n+4}|=|T_{n+2}|+|T_{n}|+2 $

Từ đó, ta chứng minh được: $ a_{2m-1}= 2(F_{m+1}-1) $ và $ a_{2m}= F_{m+3}-2 $

Bài viết đã được chỉnh sửa nội dung bởi Stranger411: 03-08-2012 - 13:54