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

[Nobodyv3]

1/ Có bao nhiêu xâu kích thước n lập từ $\left \{ 0,1,2,3 \right \} $ sao cho tổng số chữ số 0 và số chữ số 1 là số chẵn. (Tdụ : trong xâu có p số 0 và q số 1 thì p+q là số chẵn) .
2/ Có bao nhiêu cách xếp n bạn ngồi trên n cái ghế xung quanh 1 bàn tròn, biết rằng các bạn chỉ có thể di chuyển đổi chỗ xa nhất là đến ghế liền kề với ghế mình đang ngồi.

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 18-06-2023 - 11:24

[Nobodyv3]

1/ Hàm sinh cho số các xâu có chẵn chữ số 0 và chẵn chữ số 1:
$$\begin {align*}
\frac {(e^{x}+e^{-x})^2}{4}e^{2x}&=\frac {1}{4}(e^{4x}+2e^{2x}+1)\\
&=\frac {1}{4}\sum_{n=0}^{\infty }(4^n+2.2^n)\frac {x^n}{n!}+\frac {1}{4}\\
&=\frac {1}{4}\sum_{n=1}^{\infty }(4^n+2.2^n) \frac {x^n}{n!}+1\\
\Rightarrow &E_n=\frac {4^n+2.2^n}{4}\qquad (n=1,2,...)
\end{align*}$$Hàm sinh cho số các xâu có lẻ chữ số 0 và lẻ chữ số 1:
$$\begin{align*}
\frac {(e^{x}-e^{-x})^2}{4}e^{2x}&=\frac {1}{4}(e^{4x}-2e^{2x}+1)\\
&=\frac {1}{4}\sum_{n=0}^{\infty }(4^n-2.2^n)\frac {x^n}{n!} +\frac {1}{4}\\
&=\frac {1}{4}\sum_{n=1}^{\infty }(4^n-2.2^n)\frac {x^n}{n!}\\
\Rightarrow &O_n=\frac {4^n-2.2^n}{4}\qquad (n=1,2,...)
\end{align*}$$Suy ra số các xâu thỏa yêu cầu là :
$$E_n+O_n=\frac {2.4^n}{4}=\boldsymbol {2^{2n-1}}$$

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 20-06-2023 - 21:06

[Nobodyv3]

1/ Cách khác :
Không xét ràng buộc thì hàm sinh cho chữ số 0 và chữ số 1 là $\left ( 1+x+\frac{x^2}{2!}+... \right )^2=e^{2x}$ và để thỏa ràng buộc thì hàm sinh cho 2 chữ số này là $\frac {e^{2x}+e^{-2x}}{2} $ Do đó hàm sinh cho số các xâu thỏa yêu cầu là :
$\begin {align*}
f(x)&=\frac {e^{2x}+e^{-2x}}{2}e^{2x}\\
&=\frac{e^{4x}+1}{2}\\
&= \sum_{n\geq 0}\frac {4^n}{2}\frac {x^n}{n!}+\frac {1}{2}\\
&= \sum_{n\geq 1}\frac {4^n}{2}\frac {x^n}{n!}+1\\
\Rightarrow\; &\boldsymbol {a_n =\frac {4^n}{2}=2^{2n-1}}\qquad (n=1,2,...)
\end{align*}$

[Nobodyv3]

2/ Đánh số các bạn và ta có 3 trường hợp :
- Bạn 1 ngồi yên : có $b_{n-1}$ cách xếp.
- Bạn 1 và 2 tráo chỗ ngồi với nhau : có $b_{n-2}$ cách.
- Tất cả các bạn cùng chuyến qua ghế bên phải hoặc cùng chuyển qua ghế bên trái của mình : có 2 cách.
Do đó:
$a_n=b_{n-1}+b_{n-2}+2$ với $b_1=1,\, b_2=2$
Vậy ta có số cách ngồi thỏa yêu cầu là :
$\boldsymbol {a_n=b_n+2=F_{n+1}+2}$ trong đó $F_n$ là số hạng thứ n trong dãy Fibonacci được định nghĩa $F_1=F_2=1, \, F_{n+1}=F_n+F_{n-1}$.

[chanhquocnghiem]

1/ Có bao nhiêu xâu kích thước n lập từ $\left \{ 0,1,2,3 \right \} $ sao cho tổng số chữ số 0 và số chữ số 1 là số chẵn. (Tdụ : trong xâu có p số 0 và q số 1 thì p+q là số chẵn)

Với mỗi $k$ ($0\leqslant k\leqslant \frac{n}{2}$) :

- Chọn $2k$ vị trí trong số $n$ vị trí : Có $C_n^{2k}$ cách.

- Mỗi vị trí (trong $2k$ vị trí đã chọn) điền chữ số $0$ hoặc $1$ : Có $2^{2k}$ cách.

- Mỗi vị trí còn lại điền chữ số $2$ hoặc $3$ : Có $2^{n-2k}$ cách.

$\Rightarrow$ Số xâu thỏa mãn yêu cầu đề bài là

$a_n=(C_n^0+C_n^2+C_n^4+...).2^{2k}.2^{n-2k}=2^{n-1}.2^n=2^{2n-1}$.