Nobodyv3

Trong thư viện có 12 quyển sách gồm 3 quyển Toán giống nhau, 3 quyển Lý giống nhau, 3 quyển Hóa giống nhau và 3 quyển Sinh giống nhau. Xác suất 3 quyển sách thuộc cùng 1 môn không được xếp liền nhau ?

Áp dụng nguyên lý bù trừ, ta lập được hàm sinh :
$$ \left(\frac {x^3}{3!}- x\right)^4= \frac {1}{1296}x^{12}- \frac {1}{54}x^{10} + \frac {1}{6}x^8 - \frac {2}{3}x^6+x^4$$ Thế các $x^k$ bằng các $k!$ ta có số các cách xếp thỏa yêu cầu :
$$\begin {align*}
&\frac {1}{1296}12! - \frac {1}{54}10!
+ \frac {1}{6}8! - \frac {2}{3}6! + 4!\\
&=369600-67200+6720-480+24\\
&=\boldsymbol {308664}
\end{align*}$$
Cách khác : Không dùng hàm sinh mà sử dụng trực tiếp nguyên lý bù trừ, ta có số cách xếp thỏa đề bài :$$\begin {align*}
&\binom{12}{3,3,3,3}-4\binom{10}{1,3,3,3}+6\binom{8}{1,1,3,3}\\
&-4\binom{6}{1,1,1,3}+\binom{4}{1,1,1,1}\\
&=369600-4\cdot16800+6\cdot1120-4\cdot120+24\\
&=\boldsymbol {308664}
\end{align*}$$
@chanhquocnghiem Thank you so much .
Kết quả trùng khớp với kết quả của anh.

Đề bài :"...Xác suất để không có 2 quyển sách nào thuộc cùng 1 môn được xếp liền nhau ?"
Cách khác :
Bài toán đã cho tương đương với : Có bao nhiêu từ aaabbbcccddd sao cho không có 2 chữ cái giống nhau nào đứng liền kề nhau.
Ta có hàm sinh cho các cách viết các Smirnov words ( là các từ mà trong đó không có 2 chữ cái giống nhau nào đứng liền kề nhau ) :
$$f(a,b,c,d,x)=\left(1-\frac{ax}{1+ax} -\frac{bx}{1+bx}-\frac{cx}{1+cx} -\frac{dx}{1+dx} \right) ^{-1}$$Với sự trợ giúp của WA, ta tính được số các từ Smirnov cũng là số cách xếp sách thỏa đề bài :
$$\begin {align*}
[a^3b^3c^3d^3x^{12}]f(a,b,c,d,x)&= [a^3b^3c^3d^3x^{12}]\left(1-\frac{ax}{1+ax} -\frac{bx}{1+bx}-\frac{cx}{1+cx} -\frac{dx}{1+dx} \right) ^{-1}\\
&=\boldsymbol {41304}
\end {align*}$$
Ngoài ra, ta cũng có thể giải bằng cách sử dụng đa thức Laguerre ( các bạn tham khảo các bài viết của anh @chanhquocnghiem nhé ).

Đề bài :"...Xác suất để không có 2 quyển sách nào thuộc cùng 1 môn được xếp liền nhau ?"
Gọi $A$ là biến cố cần tính xác suất.
Áp dụng nguyên lý bù trừ, ta xây dựng được hàm sinh cho các cách xếp :
$$\begin{align*} f(x)&=\left(\frac{x^3}{3!}-\binom{2}{1}\frac {x^2}{2!}+\binom{2}{2}\frac {x^1}{1!}\right)^4\\
&=\frac{1}{1296}x^{12}-\frac{1}{54}x^{11}+\frac{5}{27}x^{10}-x^9\\
&+\frac{19}{6}x^8-6x^7+\frac{20}{3}x^6-4x^5+x^4
\end{align*}$$Thế các $x^k$ bằng $k!$ ta có số các cách xếp sách thỏa yêu cầu :
$$\begin{align*}
\Rightarrow &\;\frac{12!}{1296}-\frac{11!}{54}+\frac{5\cdot 10!}{27}-9!\\
&+\frac{19\cdot 8!}{6}-6\cdot7!+\frac{20\cdot 6!}{3}-4\cdot 5!+4!\\
=&\;369600-739200+672000-362880\\
&+127680-30240+4800-480+24\\
=&\;41304
\end{align*}$$XS cần tìm :
$$P(A)=\frac { 41304 }{\frac {12!}{(3!)^4}}= \boldsymbol {\frac {1721}{15400}} $$

2/ Xét các số có m chữ số , với $1\leq m\leq k$ và số $10^k$ có k+1 chữ số, tổng chữ số là 1:
- Hàm sinh cho chữ số ngoài cùng bên trái :$\frac {x(1-x^9)}{1-x}$.
- Hàm sinh cho m-1 chữ số còn lại : $\left (\frac {1-x^{10}}{1-x}\right) ^{m-1}$
- Thêm $\frac {1}{1-x}$ để tính tổng các hệ số.
- Cộng thêm 1: là mã hóa số $10^k$.
Vậy ta có :
$$\begin{align*}
[x^s]&\sum_{m=1}^k \frac{x(1-x^9)}{1-x}\left(\frac{1-x^{10}}{1-x}\right)^{m-1}\frac{1}{1-x}+1\\
&=[x^{s-1}]\frac{1-x^9}{(1-x)^2}\sum_{m=1}^k\left(\frac{1-x^{10}}{1-x}\right)^{m-1}+1\\
&=[x^{s-1}]\frac{1-x^9}{(1-x)^2}\sum_{m=0}^{k-1}\left(\frac{1-x^{10}}{1-x}\right)^{m}+1\\
&=[x^{s-1}]\frac{1-x^9}{(1-x)^2}\,\frac{1-\left(\frac{1-x^{10}}{1-x}\right)^k}{1-\frac{1-x^{10}}{1-x}}+1\\
&=[x^s]\left(\frac{\left(1-x^{10}\right)^k}{(1-x)^{k+1}}-\frac{1}{1-x}\right)+1\\
&=[x^s]\frac{\left(1-x^{10}\right)^k}{(1-x)^{k+1}}\\
&=[x^s]\sum_{j=0}^\infty\binom{-(k+1)}{j}(-x)^j\left(1-x^{10}\right)^k\\
&=\sum_{j=0}^s\binom{k+j}{k}[x^{s-j}]\left(1-x^{10}\right)^k\\
&=\sum_{j=0}^s\binom{k+s-j}{k}[x^j]\sum_{l=0}^k\binom{k}{l}(-1)^lx^{10l}\\
&=\sum_{j=0}^{\lfloor s/10\rfloor}\binom{k+s-10j}{k}[x^{10j}]\sum_{l=0}^k\binom{k}{l}(-1)^lx^{10l}\\
&\,\,=\sum_{j=0}^{\lfloor s/10\rfloor}(-1)^j \binom{k}{j} \binom{k+s-10j}{k}
\end{align*}$$

1/ Với $ 0\leq s\leq 45$ ta có:
$$\begin{align*}
\Rightarrow [x^s]\left(\frac{1-x^{10}}{1-x}\right)^5
&=[x^s](1-x^{10})^5\sum_{i=0}^{\infty}\binom{-5}{i}(-x)^i\\
&=[x^s]\sum_{j=0}^{5}\binom{5}{j}(-1)^jx^{10j}\sum_{i=0}^{\infty}\binom{i+4}{4}x^i\\
&=\sum_{j=0}^{\lfloor s/10\rfloor}\binom{5}{j}(-1)^j[x^{s-10j}]\sum_{i=0}^{\infty}\binom{i+4}{4}x^i\\
&=\sum_{j=0}^{\lfloor s/10\rfloor}(-1)^j\binom{5}{j}\binom{s-10j+4}{4}
\end{align*}$$

cho X là tập hợp các số tự nhiên có 5 chữ số. xác xuất để tìm đc số với các chữ số đứng sau lớn hơn hoặc bằng chữ số đứng trước và 3 chữ số ở giữa đôi 1 khác nhau .

Nếu các số có dạng $\overline{abcde}$ thì theo đề bài ta có
$$1\leq a\leq b<c<d\leq e \leq 9\Leftrightarrow 1\leq a< b+1<c+1<d+1< e+2 \leq 11$$
Do đó XS cần tính là :
$$\frac {\binom {11}{5}}{9\cdot10^4}=\frac {462}{90000}=\frac {77}{15000}$$

Em xin trình bày luôn :
.....Vẫn sử dụng các đặt để, lập luận đã posted ở trên, ta thấy $A_1$ chỉ có thể nối với $A_2, A_4,...,A_{2n}$. Một khi $A_{1}$ nối với $ A_{2m}$ thì $2(m-1)$ điểm $A_2, A_3,...,A_{2m-1}$ nối với nhau từng cặp theo $c_{m-1}$ cách, và $2(n-m)$ điểm $A_{m+1}, A_{m+2},...,A_{2n}$ phải được nối với nhau từng cặp theo $c_{n-m}$ cách. Cho nên, đặt $c_0=1$ thì ta có hệ thức truy hồi cho dãy $ \left \{ c_n \right \} $ là:
$$c_n=c_0c_{n-1}+c_1c_{n-2}+c_2c_{n-3}+...+c_{n-1}c_0$$ $(*)$
Giải $(*)$, đặt $f(x)=c_0+c_1x+c_2x^2+...$ thì :
$$f(x)^2=(c_0c_0)+(c_0c_1+c_1c_0)x+(c_0c_2+c_1c_1+c_2c_0)x^2+...=c_1+c_2x+c_3x^2+...$$
$\Rightarrow xf(x)^2=f(x)-1$. Giải phương trình bậc 2 theo $f(x)$:
$\Rightarrow f(x)=\frac {1\pm \sqrt{1-4x}}{2x}$. Nhận thấy để có $\lim_{x\rightarrow 0}f(x)=c_0$ thì $f(x)=\frac {1-\sqrt{1-4x}}{2x}$ và sử dụng khai triển $$(1-x)^{1/2}=1-\sum_{n=1}^{\infty }\frac {2}{n}\cdot \frac {(2n-2)!}{(2^n(n-1)!)^2}$$ ta có :
$\begin {align*}
f(x)&=\frac {1}{2x}\left (1-\sqrt {1-4x}\right )\\
&=\frac {1}{2x}\sum_{n=1}^{\infty }\frac {2}{n}\binom {2n-2}{n-1}x^n\\
&=\sum_{n=1}^{\infty }\frac {1}{n}\binom {2n-2}{n-1}x^{n-1}\\
&=\sum_{n=0}^{\infty }\frac {1}{n+1}\binom {2n}{n}x^{n}
\end{align*}$
Suy ra : $\boldsymbol {c_n=\frac {1}{n+1}\binom {2n}{n}}$
Số này thấy quen quen ....

Phần cuối hơi vắn tắt nên để giải thích rõ hơn, ta làm lại từ từ nhé. ( kẻo bị tẩu hỏa nhập ma, mất hết 20 năm võ công khổ luyện!).
Xin tiếp theo từ $f(x)=\frac {1-\sqrt {1-4x}}{2x}$
Khai triển Taylor của $\sqrt{1-4x}$:
$$\begin {align*}
\sqrt {1-4x}&=1+\sum_{n=1}^{\infty }\binom {1/2}{n}\left ( -4 \right )^nx^n\\
\text{mà  }\binom {1/2}{n} &=\frac {\frac {1}{2}\cdot\frac {-1}{2}\cdot\frac {-3}{2}\cdots\frac {-2n+3}{2}}{n!}\\
&=(-1)^{n-1}\frac {1\cdot 1\cdot 3\cdot 5\cdot 7\cdots (2n-3)}{2^nn!}\\
&=(-1)^{n-1}\frac {1\cdot 2\cdot 3\cdot 4\cdot 5\cdots (2n-2)}{2^nn!}\cdot \frac {1}{2\cdot 4\cdot 6\cdots (2n-2)}\\
&=(-1)^{n-1}\frac {(2n-2)!}{2^nn!}\cdot \frac {1}{2^{n-1}(n-1)!}\\
&=(-1)^{n-1}\frac {(2n-2)!}{2^n(n-1)!n}\frac {1}{2^{n-1}(n-1)!}\\
\Rightarrow \sqrt {1-4x}&=1+\sum_{n=1}^{\infty }\binom {1/2}{n}(-4)^nx^n\\
&=1+\sum_{n=1}^{\infty }\left ( (-1)^{n-1}\binom {2n-2}{n-1}\frac {1}{n2^{2n-1}} \right )(-4)^nx^n\\
&=1-2\sum_{n=1}^{\infty }\frac {1}{n}\binom {2n-2}{n-1}x^n\\
\text{do đó  }f(x)&=\frac {1-\sqrt{1-4x}}{2x}\\
&=\frac {1-\left ( 1-2\sum_{n=1}^{\infty }\frac {1}{n}\binom {2n-2}{n-1}x^n \right )}{2x}\\
&=\sum_{n=1}^{\infty }\frac {1}{n}\binom {2n-2}{n-1}x^{n-1}\\
&=\sum_{n=0}^{\infty }\frac {1}{n+1}\binom {2n}{n}x^n\\
\Rightarrow c_n&=\boldsymbol {\frac {1}{n+1}\binom {2n}{n}}
\end{align*}$$

2/ Gọi $a_n$ là số các xâu thỏa yêu cầu và $x_n, y_n, z_n$ lần lượt là số các xâu kết thúc bằng 0,1,2 thỏa yêu cầu đề bài. Rõ ràng:
$\begin {align*}
x_{n+1}&=y_n+z_n\\
y_{n+1}&=x_n+y_n+z_n\\
z_{n+1}&=x_n+y_n+z_n
\end{align*}$
Cho nên :
$y_n=z_n,\;x_{n+1}=2y_n,\;y_{n+1}=x_n+2y_n$.
Từ : $y_{n+1}-2y_n-2y_{n-1}=0 \Rightarrow \alpha, \beta =1\pm \sqrt 3\Rightarrow y_n=A\left ( 1+ \sqrt 3 \right )^n+B\left ( 1- \sqrt 3 \right )^n$
Do $y_2=3,\;y_3=8$ nên:
$A=\frac {1+\sqrt3}{4\sqrt3},\;B=\frac {1-\sqrt3}{4\sqrt3}\Rightarrow y_n=\frac {1}{4\sqrt3}\left (\alpha ^{n+1}-\beta^{n+1} \right )$ do $ a_n = x_n + y_n + z_n = 2y_{n-1} + 2y_n $ ta có
$\begin{align*}
a_n &= \frac{1}{2\sqrt{3}}\left(\alpha^n(1+\alpha) - \beta^n(1+\beta)\right)\\
&= \left(\frac{2+\sqrt{3}}{2\sqrt{3}}\right)(1+\sqrt3)^n -\left(\frac{2-\sqrt{3}}{2\sqrt{3}}\right)(1-\sqrt3)^n\\
&=\boldsymbol {\frac {1}{6}\left ( \left ( 3+2\sqrt3 \right )\left ( 1+\sqrt 3 \right )^n+\left ( 3-2\sqrt3 \right )\left ( 1-\sqrt3 \right )^n \right )}
\end{align*}$
Edited.

1/ Với một xâu bất kỳ thỏa đề bài, ta thêm một bit 1 vào đầu xâu và một bit 0 vào cuối xâu thì ta có xâu mới kích thước n+2 và vẫn có đúng m xâu con 01. Gọi vị trí trong xâu mà ở đó, bit 0 chuyển qua bit 1 hoặc ngược lại, là "vị trí chuyển " thì lúc này, xâu có n+1 chỗ trống và 2m+1 "vị trí chuyển ". Do đó số các xâu thỏa yêu cầu là $\boldsymbol {\binom {n+1}{2m+1}}$
Hoặc là :
Gọi vị trí trong xâu mà ở đó, bit 0 chuyển qua bit 1 hoặc ngược lại là "vị trí chuyển " thì lúc này, xâu có n-1 chỗ trống và có các trường hợp sau :
- Xâu bắt đầu và kết thúc bằng bit 1: có 2m "vị trí chuyển " .
- Xâu bắt đầu bằng bit 1 và kết thúc bằng bit 0: có 2m+1 "vị trí chuyển " .
- Xâu bắt đầu và kết thúc bằng bit 0: có 2m "vị trí chuyển " .
- Xâu bắt đầu bằng bit 0 và kết thúc bằng bit 1: có 2m-1 "vị trí chuyển " .
Do đó số các xâu thỏa đề bài là :
$\begin {align*}
a_n&=\binom {n-1}{2m}+\binom {n-1}{2m+1}+\binom {n-1}{2m}+\binom {n-1}{2m-1}\\&=\binom {n}{2m+1}+\binom {n}{2m}\\&=\boldsymbol {\binom {n+1}{2m+1}}
\end{align*}$

(Làm cho nó ra kết quả luôn)
$\left\{\begin{matrix}a_0=1=F_2\\a_1=2=F_3\\a_n=a_{n-1}+a_{n-2},\forall n\geqslant 2 \end{matrix}\right.\Rightarrow a_n=F_{n+2},\forall n\in \mathbb{N}$
(với $F_k$ là số Fibonacci thứ $k$)

Tức là :
$$a_n=\frac{1}{\sqrt5}\left (\frac {1+\sqrt 5}{2}  \right )^{n+2}- \frac{1}{\sqrt5} \left (\frac {1-\sqrt 5}{2} \right )^{n+2}$$
Hoặc là nếu muốn n ở số mũ hơn là n + 2 thì sau một vài phép tính đại số, ta có:
$$a_n=\frac{5+3\sqrt 5}{10}\left (\frac {1+\sqrt 5}{2}  \right )^{n}+ \frac{5-3\sqrt 5}{10} \left (\frac {1-\sqrt 5}{2} \right )^{n}$$

3/ Từ hàm sinh :
$f(x)=\left ( \frac {e^x+e^{-x}}{2} \right )e^{3x}=\frac {1}{2}\left ( e^{4x}+e^{2x} \right )$
suy ra số các xâu thỏa yêu cầu là $\boldsymbol {\frac {1}{2}\left ( 4^{n}+2^{n} \right )}$
hoặc giải theo cách "truyền thống " bằng cách lập hệ thức truy hồi...

1/ Tính số các xâu nhị phân kích thước n có đúng m xâu con 01.
2/ Tính số các xâu tam phân kích thước n mà không có 2 chữ số 0 đứng kề nhau.
3/ Tính số các xâu tứ phân kích thước n có số các chữ số 0 là số chẵn.

Em xin trình bày luôn :
.....Vẫn sử dụng các đặt để, lập luận đã posted ở trên, ta thấy $A_1$ chỉ có thể nối với $A_2, A_4,...,A_{2n}$. Một khi $A_{1}$ nối với $ A_{2m}$ thì $2(m-1)$ điểm $A_2, A_3,...,A_{2m-1}$ nối với nhau từng cặp theo $c_{m-1}$ cách, và $2(n-m)$ điểm $A_{m+1}, A_{m+2},...,A_{2n}$ phải được nối với nhau từng cặp theo $c_{n-m}$ cách. Cho nên, đặt $c_0=1$ thì ta có hệ thức truy hồi cho dãy $ \left \{ c_n \right \} $ là:
$$c_n=c_0c_{n-1}+c_1c_{n-2}+c_2c_{n-3}+...+c_{n-1}c_0$$ $(*)$
Giải $(*)$, đặt $f(x)=c_0+c_1x+c_2x^2+...$ thì :
$$f(x)^2=(c_0c_0)+(c_0c_1+c_1c_0)x+(c_0c_2+c_1c_1+c_2c_0)x^2+...=c_1+c_2x+c_3x^2+...$$
$\Rightarrow xf(x)^2=f(x)-1$. Giải phương trình bậc 2 theo $f(x)$:
$\Rightarrow f(x)=\frac {1\pm \sqrt{1-4x}}{2x}$. Nhận thấy để có $\lim_{x\rightarrow 0}f(x)=c_0$ thì $f(x)=\frac {1-\sqrt{1-4x}}{2x}$ và sử dụng khai triển $$(1-x)^{1/2}=1-\sum_{n=1}^{\infty }\frac {2}{n}\cdot \frac {(2n-2)!}{(2^n(n-1)!)^2}$$ ta có :
$\begin {align*}
f(x)&=\frac {1}{2x}\left (1-\sqrt {1-4x}\right )\\
&=\frac {1}{2x}\sum_{n=1}^{\infty }\frac {2}{n}\binom {2n-2}{n-1}x^n\\
&=\sum_{n=1}^{\infty }\frac {1}{n}\binom {2n-2}{n-1}x^{n-1}\\
&=\sum_{n=0}^{\infty }\frac {1}{n+1}\binom {2n}{n}x^{n}
\end{align*}$
Suy ra : $\boldsymbol {c_n=\frac {1}{n+1}\binom {2n}{n}}$
Số này thấy quen quen ....

Có phải ý bạn là : Hỏi có bao nhiêu cách nối các cặp điểm (mỗi điểm chỉ nối với duy nhất $1$ điểm khác) sao cho trong $n$ đoạn thẳng tạo thành, không có cặp đoạn thẳng nào có điểm chung ?
Nếu là như vậy thì xin giải như sau...
--------------------------------------------------------
Đặt tên các điểm đã cho theo chiều kim đồng hồ là $A_1,A_2,...,A_{2n}$
Xét một cách nối thỏa mãn yêu cầu đề bài, trong đó $A_1$ nối với $A_k$.
Nhận xét rằng $A_1$ và $A_k$ chia đường tròn thành 2 cung và số các điểm $A_i$ trên mỗi cung (nằm giữa $A_1$ và $A_k$) đều phải là số chẵn.
Do đó, $k$ chỉ có thể là $2,4,6,...,2n$
Với mỗi giá trị của $k$ chỉ có $1$ cách nối. Vậy có tất cả $n$ cách nối thỏa mãn yêu cầu đề bài.

Em thì thấy bài toán rối hơn nhiều!
Gọi $c_n$ là số cách nối $2n$ điểm thỏa yêu cầu. Ta cho n vài giá trị nho nhỏ (để đếm đủ trên 10 đầu ngón tay), nối $A_1$ với các $A_{2n}$ rồi đếm " thủ công " thì thấy $c_n$ có các giá trị như sau :
( Ghi chú: ký hiệu $(A_i-A_j)$ là nối điểm $A_i$ với $A_j$.)
$- n=0: 1 $ cách
$- n=1:[( A_1-A_2)]\Rightarrow 1$ cách
$$- n=2: [(A_1-A_4)(A_2-A_3)] , [(A_1-A_2)(A_3-A_4)] \Rightarrow 2$$ cách
$$- n=3:[ (A_1-A_6)(A_2-A_5)(A_3-A_4)],[(A_1-A_6
)(A_2-A_3)(A_4-A_5) ] ,[(A_1-A_4)(A_2-A_3)(A_5-A_6) ],[(A_1-A_2)(A_3-A_4)(A_5-A_6) ],[(A_1-A_2)(A_3-A_6)(A_4-A_5) ] \Rightarrow 5$$ cách
$- n=4 \Rightarrow 14 $ cách (số cách nối hơi bị nhiều nên xin phép không liệt kê các cách nối trong trường hợp này)
...vv.....
Như vậy, với mỗi giá trị $k$ sẽ có số các cách nối khác nhau do đó khả năng $c_n\neq n$ là rất lớn!.

2/ Theo chiều kim đồng hồ, ta gọi chiều dài 4 chân bàn sau khi cưa là $a, b,c,d \;(1\leq a,b,c,d\leq 8)$.Độ nghiêng của chiếc bàn theo hướng bắc-nam sẽ được xác định bởi hiệu giữa các độ dài a,b và d,c và theo hướng đông - tây bởi hiệu giữa các độ dài b,c và a,d. Từ đó để bàn không bị khập khễnh ta phải có:
$ a-d=b-c\Leftrightarrow
b-a=c-d\Leftrightarrow a+c=b+d $.
Ta có $L=a+c=b+d$. Số các cặp thứ tự $(x,y)$ sao cho $L=x+y$ và $1\leq x,y\leq 8$ là $S_L= 8-\left | L-9 \right |$ (tương tự như tính số cách gieo 2 xúc xắc 8 mặt có tổng số chấm là L). Nên số cách chọn (a,c) cũng như (b,d) là $S_L$, do đó số cách chọn (a,b,c,d) là $S_{L}^{2}$. Cộng các giá trị có thể có của $L$:
$$\begin {align*}
S_{2}^{2}+...+S_{16}^{2}&=(8-\left | 2-9 \right |)^2+...+(8-\left | 16-9 \right |)^2\\
&=1^2+2^2+...+7^2+8^2+7^2+...+2^2+1^2\\
&=2(1^2+...+7^2)+8^2\\
&=2\cdot \frac {7\cdot 8\cdot 15}{6}+8^2\\
&=344
\end{align*}$$
Xác suất cần tìm là :
$\frac {344}{8^4}=\boldsymbol {\frac {43}{512}}$