Bài toán: Có bao nhiêu hoán vị khác nhau từ chữ: TOANHOCTUOITRE, trong đó các chữ số giống nhau không đứng cạnh nhau.
Lời giải
Gọi:
\mathsf{S} là tập hợp tất cả các cách sắp xếp khác nhau.
\mathsf{T}, \mathsf{O} lần lượt là tập hợp các cách sắp xếp các chữ T, O đứng cạnh nhau;
\mathsf{T}_2, \mathsf{O}_2 lần lượt là tập hợp các cách sắp xếp 2 chữ T, O đứng cạnh nhau;
\mathsf{T}_3, \mathsf{O}_3 lần lượt là tập hợp các cách sắp xếp 3 chữ T, O đứng cạnh nhau
\mathsf{W} là tập hợp tất cả các cách sắp xếp hai chữ cái giống nhau đứng cạnh nhau.
Vì có đúng 14 chữ cái, trong đó có 3 chữ T, 3 chữ O, nên n(\mathsf{S})=\frac{14!}{3!.3!}.
Để ba chữ T đứng cạnh nhau, ta chỉ cần coi cụm TTT là một chữ cái. Ta còn 12 chữ cái. Khi đó n(\mathsf{T}_3)=\frac{12!}{3!}.
Tương tự n(\mathsf{O}_3)=\frac{12!}{3!}.
Để hai chữ T đứng cạnh nhau ta chỉ cần coi cụm TT là một chữ cái. Ta còn 13 chữ cái. Khi đó n(\mathsf{T}_2)=\frac{13!}{3!}.
Tương tự n(\mathsf{O}_2)=\frac{13!}{3!}.
Vậy
n(\mathsf{O})= n(\mathsf{O}_2)-n(\mathsf{O}_3)= \frac{13!}{3!}-\frac{12!}{3!}=2.12!=n(\mathsf{T}).
Để hai chữ T đứng cạnh nhau và hai chữ O đứng cạnh nhau, ta chỉ cần coi các cụm TT, OO là các chữ cái. Ta còn 12 chữ cái. Khi đó n(\mathsf{T}_2 \cap \mathsf{O}_2)=12!.
Tương tự
n(\mathsf{T}_3 \cap \mathsf{O}_3)=10!; \quad n(\mathsf{T}_2 \cap \mathsf{O}_3)=n(\mathsf{T}_3 \cap \mathsf{O}_2)=11!.
Do đó
\begin{align*} n(\mathsf{T}\cap \mathsf{O})&=n(\mathsf{T}_2\cap \mathsf{O}_2)-n(\mathsf{T}_3\cap \mathsf{O}_2)-n(\mathsf{T}_2\cap \mathsf{O}_3)+n(\mathsf{T}_3\cap \mathsf{O}_3) \\&=12!.-2.11!.+10!=111.10!\end{align*}
Theo nguyên lý bù trừ, ta có:
\begin{align*}n(\mathsf{W}) &=& n\left (\mathsf{T}\cup\mathsf{O}\right ) \\& =& n\left (\mathsf{T}\right )+n\left (\mathsf{O}\right ) -n\left (\mathsf{T}\cap\mathsf{O}\right ) \\&=& 2.2.12!-111.10!=417.10!\end{align*}
Vậy số hoán vị cần tìm là
n=n(\mathsf{S})-n(\mathsf{W})=908409600
0 comments:
Đăng nhận xét