Đến nội dung

Hình ảnh

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.

- - - - -

  • Please log in to reply
Chủ đề này có 8 trả lời

#1
anhtuan962002

anhtuan962002

    Hạ sĩ

  • Thành viên
  • 92 Bài viết

Mọi người giúp em giải chi tiết bài này ạ (được nhiều cách càng tốt).Em cảm ơ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.



#2
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
Đây là 1 cách : (và nhờ anh @chanhquocnghiem biểu diễn các cách giải khác: sử dụng Laguerre polynomials chẳng hạn)
Đề bài yêu cầu tính số các từ Smirnov. (Smirnov words ( hay Carlitz words ) là các từ mà trong đó các chữ cái giống nhau không đứng ở vị trí liên tiếp).
Giải :
Ta có hàm sinh cho số Smirnov words thuộc bảng n chữ cái là $\left(1-\frac{nz}{1+z}\right)^{-1}$. Ở đây, xét bảng chữ cái $V=\left \{ T,O,A,N,H,C,U,I,R,E \right \}$ với $n=10$ chữ cái.
Ta có số Smirnov words cũng là số hoán vị thỏa yêu cầu là :
$$\begin{align*} &{[T^3O^3ANHCUIRE]\left(1-\sum_{a\in V}\frac{a}{1+a}\right)^{-1}}\\ &\qquad=[T^3O^3ANHCUIRE]\sum_{k=0}^{\infty}\left(\sum_{a\in V}\frac{a}{1+a}\right)^k\\\ &\qquad=[T^3O^3ANHCUIRE]\sum_{k=10}^{14}\left(\sum_{a\in V}\frac{a}{1+a}\right)^k\\\ &\qquad=[T^3O^3ANHCUIRE]\sum_{k=10}^{14}\left(T\left(1-T+T^2\right)\right.\\
&\qquad\qquad\qquad\qquad\qquad\qquad\qquad \left.+O(1-O+O^2)\right. \\ &\qquad\qquad\qquad\qquad\qquad\qquad\qquad \left.+A+N+H+C+U+I+R+E\right)^k\\ &\qquad= 3628800-79833600+638668800-2075673600+2421619200\\
&\qquad=\color{blue}{908409600} \end{align*}$$

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 03-08-2023 - 10:36

===========
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...

#3
chanhquocnghiem

chanhquocnghiem

    Thiếu tá

  • Thành viên
  • 2494 Bài viết

Mọi người giúp em giải chi tiết bài này ạ (được nhiều cách càng tốt).Em cảm ơ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.

Phương pháp đa thức Laguerre :

Ta có $10$ loại chữ cái : $T,O,A,N,H,C,U,I,R,E$

Số lượng mỗi loại là $n_1=n_2=3$ ; $n_3=n_4=n_5=...=n_{10}=1$

Một hoán vị không hợp lệ khi chứa $2$ chữ cái liên tiếp giống nhau $\rightarrow m_1=m_2=...=m_{10}=2$

Đa thức cho mỗi chữ $T$ và $O$ là $P_{2,3}(t)=\left [ x^3 \right ]\exp\left ( \frac{t(x-x^2)}{1-x^2} \right )=\frac{t^3}{6}-t^2+t$

Đa thức cho mỗi chữ còn lại là $P_{2,1}(t)=\left [ x^1 \right ]\exp\left ( \frac{t(x-x^2)}{1-x^2} \right )=t$

Số hoán vị thỏa mãn yêu cầu là

$\int_{0}^{\infty}e^{-t}\left ( \frac{t^3}{6}-t^2+t \right )^2t^8dt=908409600$.
 


...

Ðêm nay tiễn đưa

Giây phút cuối vẫn còn tay ấm tay
Mai sẽ thấm cơn lạnh khi gió lay
Và những lúc mưa gọi thương nhớ đầy ...

 

http://www.wolframal...-15)(x^2-8x+12)


#4
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3916 Bài viết
Có cách nào sơ cấp hơn không?

#5
E. Galois

E. Galois

    Chú lùn thứ 8

  • Quản lý Toán Phổ thông
  • 3861 Bài viết
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})=\dfrac{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)=\dfrac{12!}{3!}$. 
Tương tự $n(\mathsf{O}_3)=\dfrac{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)=\dfrac{13!}{3!}$. 
Tương tự $n(\mathsf{O}_2)=\dfrac{13!}{3!}$.
Vậy
$$n(\mathsf{O})= n(\mathsf{O}_2)-n(\mathsf{O}_3)= \dfrac{13!}{3!}-\dfrac{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$$
 
 

Bài viết đã được chỉnh sửa nội dung bởi E. Galois: 03-08-2023 - 21:58

1) Xem cách đăng bài tại đây
2) Học gõ công thức toán tại: http://diendantoanho...oạn-thảo-latex/
3) Xin đừng đặt tiêu đề gây nhiễu: "Một bài hay", "... đây", "giúp tớ với", "cần gấp", ...
4) Ghé thăm tôi tại 
http://Chúlùnthứ8.vn

5) Xin đừng hỏi bài hay nhờ tôi giải toán. Tôi cực gà.


#6
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết

Có cách nào sơ cấp hơn không?

Một chốc nữa, em tranh thủ bài giải dựa trên nguyên lý bù trừ :-)
========
Vâng, em xin trình bày ạ.
Để thuận tiện trong việc trình bày, trong lời giải này em ký hiệu chữ cái $T, \,O$ tương ứng là $a,\,b$ và qui ước :
- Dựa trên nguyên lý bù trừ, em xét các trường hợp khác nhau của từ không hợp lệ ( sau này gọi là "từ xấu ").
- Các trường hợp khác nhau được ngăn cách bằng dấu " | ".
- Những từ xấu không chồng lên nhau được ngăn cách bằng khoảng trống.
Vậy theo nguyên lý bù trừ ta có :
$$\begin{align*}
& \left ( \right )-(aa\,\mid bb)\\
&\qquad +(aaa\,\mid\,aa\,bb\,\mid\,bbb)-(aaa\,bb\,\mid\,aa\,bbb)\\&\qquad +(aaa\,bbb)\\
&\Rightarrow \binom{14}{3,3}-2\binom{13}{1,1,3}+2\binom{12}{1,3}\\
&\qquad +\binom{12}{1,1,1,1}-2\binom{11}{1,1,1}+\binom{10}{1,1}\\
&\qquad =\color {blue}908409600
\end{align*}$$
Nhờ WA check lại :
https://www.wolframa...6+12!-2*11!+10!

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 04-08-2023 - 00:39

===========
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...

#7
chanhquocnghiem

chanhquocnghiem

    Thiếu tá

  • Thành viên
  • 2494 Bài viết

Có cách nào sơ cấp hơn không?

Gọi $S_k$ là số cách sắp xếp sao cho có ít nhất $k$ loại chữ cái chiếm $2$ vị trí liên tiếp. Ta tính $S_k$ theo cách sau :

    - Chọn $k$ loại chữ cái trong số $2$ loại chữ cái ($T$ và $O$) : $C_2^k$ cách.

    - Với mỗi loại chữ cái (trong $k$ loại đã chọn), ta ghép $2$ chữ cái giống nhau, xem như $1$ chữ cái đặc biệt. Như vậy, từ $14$ chữ cái ban đầu, nay chỉ còn $14-k$ chữ cái. Ta gọi 2 chữ cái, ví dụ $T$ và $TT$ là 2 chữ cái liên hợp. Nếu chúng nằm cạnh nhau thì gọi là cặp chữ cái liên hợp. Sắp xếp ngẫu nhiên $14-k$ chữ cái đó.

Số cách để có ít nhất $j$ cặp chữ cái liên hợp nào đó là $M_j=\frac{2^j(14-k-j)!}{6^{2-k}}$

$\Rightarrow S_k=C_2^k\sum_{j=0}^{k}(-1)^jC_k^j\frac{M_j}{2^j}=\frac{C_2^k}{6^{2-k}}\sum_{j=0}^{k}(-1)^jC_k^j(14-k-j)!$

$\Rightarrow$ đáp án bài toán là $\frac{14!}{6^2}+\sum_{k=1}^{2}(-1)^kS_k=\frac{1}{6^2}\sum_{k=0}^{2}C_2^k(-6)^k\left [ \sum_{j=0}^{k}C_k^j(-1)^j(14-k-j)! \right ]=$

$=\frac{14!-12(13!-12!)+36(12!-2.11!+10!)}{36}=908409600$.

 


...

Ðêm nay tiễn đưa

Giây phút cuối vẫn còn tay ấm tay
Mai sẽ thấm cơn lạnh khi gió lay
Và những lúc mưa gọi thương nhớ đầy ...

 

http://www.wolframal...-15)(x^2-8x+12)


#8
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3916 Bài viết
Cách của thầy @E. Galois chuẩn, dễ hiểu và ít tính toán hơn cả!

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 03-08-2023 - 23:06


#9
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
Kiểm tra :
https://www.wolframa...6+12!-2*11!+10!

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 04-08-2023 - 00:31

===========
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...




0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh