Nobodyv3

Chọn ngẫu nhiên 2 ô vuông trên bàn cờ vua 8x8. Hỏi xác suất để chúng có :
a) một cạnh chung.
b) một đỉnh chung.

Ta có :
$$\begin {align*}
&1,1,1,2,2,2,3,3,3\to\frac{9!}{3!3!3!}\\
&122,1,1,2,3,3,3\to\frac{7!}{2!3!}\\
&122,233,1,1,3\to\frac{5!}{2!}\\
&12233,1,1,2,3\to\frac{5!}{2!}\\
&122,233,311\to 3!\\
&1223311,2,3\to 3!\\
&122,233,311\to 3!
\end {align*}$$
Theo nguyên lý bù trừ, số các hoán vị thỏa đề bài là :
$$\begin {align*}&\frac{9!}{3!\cdot3!\cdot3!}-\binom{3}{1}\frac{7!}{3!\cdot2!}\\
&\quad +\binom{3}{2}\left(\frac{5!}{2!}+\frac{5!}{2!}-3!-3!\right)\\
&\quad -\binom{3}{3}3!=\color {blue} {738}
\end{align*}$$

@chanhquocnghiem cám ơn anh.
Ngoài ra, có nhiều cách khác : dùng bổ đề  Burnside, dùng số Bell...và em xin trình bày một cách nữa là dùng số Sterling numbers loại 2: $S(n,k)$.
Nếu nhóm 5 thừa số nguyên tố : $2,3,5,7,13$ thành nhiều nhất là 4 tập, thì được như sau :
$$\begin{align*} \sum_{k=1}^{4}S(5,k)&=\sum_{k=1}^{4}\frac{1}{k!}\sum_{i=0}^{k}(-1)^{k-i}\binom{k}{i}i^5\\
&=1+15+25+10\\
&=\color{blue}{51}\end{align*}$$

Có bao nhiêu cách viết số $2730$ thành tích 4 số nguyên dương mà thứ tự của chúng không quan trọng.

Có bao nhiêu hoán vị của xâu $111222333$ sao cho không chứa xâu con $122$, $233$, hoặc $311$.

Hàm sinh cho các Smirnov words trên tập $\left \{ 0,1,2,3 \right \}$ là $\left ( 1-\frac{4x}{1+x} \right )^{-1}=1+4x+12x^2+36x^3+108x^4+\cdots \qquad  (1)$
Ta tìm các xâu không chứa $00$: từ Smirnov words ta giữ lại các $0$ còn các $1,2,3$ có thể thay với số lượng không ràng buộc thì (1) cho ta:
$$\begin{align*} A(x)&=\left(1-\frac{x}{1+x}-\frac{\frac{3x}{1-x}}{1+\frac{x}{1-x}}\right)^{-1} \\
&=\frac{1+x}{1-3x-3x^2}\\
&= \cdots+ 132543135x^{14}+\boldsymbol {502509177x^{15}}+1905156936x^{16}+  \cdots  \end{align*}$$ Vậy có $\color {blue}{502509177} $ xâu thỏa đề bài.

Có bao nhiêu xâu tứ phân kích thước 15 lập từ $\left \{ 0,1,2,3 \right \}$ không có 2 chữ số 0 liên tiếp.

Giải :
Gọi :
$a_n$ là số các xâu kích thước n không chứa $aaa$,
$b_n$ là số các xâu kích thước n không chứa $bbbb$ ,
$c_n$ là số các xâu kích thước n không chứa $aaa$ và $bbbb$.
Theo nguyên lý bù trừ, số xâu cần tính là :
$d_n=2^n-a_n-b_n+c_n, n\geq 0\qquad(1) $
Hàm sinh cho các Smirnov words trên tập $\left \{ a,b \right \}$ là $\left ( 1-\frac{2x}{1+x} \right )^{-1}=1+2x+2x^2+2x^3+...\qquad (2)$
- Xâu con $aaa$:
Thiết lập hàm sinh $A(x)=\sum_{n=0}^\infty a_nx^n$ như sau : ta tìm các xâu không chứa $aaa$, từ Smirnov words ta thay mỗi $a$ bằng $a$ hoặc $aa$ còn mỗi $b$ có thể thay với số lượng không ràng buộc:
$$\begin{align*} &a:\quad x\quad\to\quad x+x^2\\ &b:\quad x\quad\to\quad x+x^2+x^3+\cdots = \frac{x}{1-x} \end{align*}$$Thay vào (2):$$\begin{align*} A(x)&=\left(1-\frac{x+x^2}{1+x+x^2}-\frac{\frac{x}{1-x}}{1+\frac{x}{1-x}}\right)^{-1} \\
&=\frac{1-x^3}{1-2x+x^4} \end{align*}$$- Xâu con $bbbb$:
Thiết lập hàm sinh $B(x)=\sum_{n=0}^\infty b_nx^n$ như sau :ta tìm các xâu không chứa $bbbb$, từ Smirnov words ta thay mỗi $b$ bằng $b$ hoặc $bb$ hoặc $bbb$ còn mỗi $a$ có thể thay với số lượng không ràng buộc :$$\begin{align*} &a:\quad x\quad\to\quad x+x^2+x^3+\cdots = \frac{x}{1-x}\\ &b:\quad x\quad\to\quad x+x^2+x^3 \end{align*}$$Thay vào (2):
$$\begin{align*} B(x)&=\left(1-\frac{\frac{x}{1-x}}{1+\frac{x}{1-x}}-\frac{x+x^2+x^3}{1+x+x^2+x^3}\right)^{-1}\\
& =\frac{1-x^4}{1-2x+x^5}\end{align*}$$- Xâu con $aaa,bbbb$:
Thiết lập hàm sinh $C(x)=\sum_{n=0}^\infty c_nx^n$ như sau : ta tìm các xâu không chứa $aaa$ và $bbbb$, từ Smirnov words ta thay mỗi $a$ bằng $a$ hoặc $aa$ và mỗi $b$ bằng $b$ hoặc $bb$ hoặc $bbb$:
$$\begin{align*} &a:\quad x\quad\to\quad x+x^2\\ &b:\quad x\quad\to\quad x+x^2+x^3 \end{align*}$$Thay vào (2):$$\begin{align*} C(x)&=\left(1-\frac{x+x^2}{1+x+x^2}-\frac{x+x^2+x^3}{1+x+x^2+x^3}\right)^{-1}\\ &=\frac{1+2x+3x^2+3x^3+2x^4+x^5}{1-x^2-2x^3-2x^4-x^5} \end{align*}$$Và hàm sinh cho $2^n$ là $$\begin{align*} \frac{1}{1-2x}=1+2x+4x^2+8x^3+\cdots \end{align*}$$
Cuối cùng, theo (1) ta có hàm sinh $D(x)$:
$$\begin{align*}D(x)&=\frac{1}{1-2x}-A(x)-B(x)+C(x)\\
&=\frac{1}{1-2x}-\frac{1-x^3}{1-2x+x^4}-\frac{1-x^4}{1-2x+x^5}\\
&+\frac{1+2x+3x^2+3x^3+2x^4+x^5}{1-x^2-2x^3-2x^4-x^5}\\ &=\cdots +34261x^{17}+75713x^{18}+165571x^{19}\\
&+\boldsymbol {358847x^{20}}+771762x^{21}+1648716x^{22} +\cdots \end{align*}$$Vậy có $\color {blue }{ 358847}$ xâu thỏa đề bài.
N.B.: Smirnov words là các từ không có chữ cái giống nhau đứng liên tiếp.

Gọi :
$a_n$ là số các xâu kích thước n không chứa $aaa$,
$b_n$ là số các xâu kích thước n không chứa $bbbb$ ,
$c_n$ là số các xâu kích thước n không chứa $aaa$ và $bbbb$.
Theo nguyên lý bù trừ, số xâu cần tính là :
$$d_n=2^n-a_n-b_n+c_n,\quad n\geq 0\qquad (1)$$Hàm sinh cho các Smirnov words trên tập $\left \{ a,b \right \}$ là $$\left ( 1-\frac{2x}{1+x} \right )^{-1}=1+2x+2x^2+2x^3+...\qquad (2)$$

( Còn tiếp)

Có bao nhiêu xâu kích thước 20 lập từ $\left \{ a,b \right \}$ có chứa xâu con $aaa$ và $bbbb$.

Mấy cái này trong sách giáo khoa có đầy đủ lắm. Nhưng nói theo kiểu của sách thì chắc cậu chẳng hiểu gì đâu
Muốn dễ hiểu chứ gì ? Vậy mình sẽ lấy ví dụ trong thực tế học đường (bảo đảm dễ hiểu lắm luôn)
Ví dụ 1 :
Giả sử lớp cậu có $18$ bạn nam và $22$ bạn nữ. Tất cả các bạn nam đều đã "thầm yêu một ai đó" (mấy cô cậu bây giờ yêu sớm lắm). Giả sử mỗi bạn nam chỉ yêu $1$ bạn nữ trong lớp (không ai yêu người ngoài lớp) và không có chuyện nam - nam yêu nhau.
Tập hợp $X$ chính là $18$ bạn nam, tập hợp $Y$ là $22$ bạn nữ.
Với mỗi nhân vật nam (thuộc $X$), ta đều có $1$ nhân vật nữ (thuộc $Y$) là "người mà bạn ấy thầm yêu". Nhà toán học bảo là "có một ÁNH XẠ từ tập $X$ đến tập $Y$
Ví dụ chàng $A$ thầm yêu nàng $Z$ thì nhà toán học bảo "$Z$ là ảnh của $A$ ; $A$ là nghịch ảnh (hay tạo ảnh) của $Z$"
Có thể xảy ra mấy trường hợp sau :
a) Không có $2$ (hay nhiều) chàng nào cùng yêu một nàng. Nhà toán học nói rằng đó là một ĐƠN ÁNH.
b) Có thể có (hoặc không có) vài chàng cùng yêu một nàng, và tất cả những nàng không được ai yêu "buồn quá" nên xin chuyển sang lớp khác (khi đó tập $Y$ giảm đi một số người). Khi đó nhà toán học lại bảo đây là một TOÀN ÁNH.
c) Nếu không có $2$ chàng nào cùng yêu một nàng và cũng không có nàng nào không được ai yêu (khi đó một số nàng đã chuyển sang lớp khác nên số nam nữ bằng nhau). Lúc này nhà toán học nói rằng có một SONG ÁNH trong lớp của bạn (nghe hoảng hồn chưa )
 
Ví dụ 2 :
Thầy giáo phát bài kiểm tra môn Toán (về Ánh xạ chẳng hạn).
Tổ cậu có $12$ người. Điểm bài kiểm tra là số nguyên từ $0$ đến $10$.
Tập hợp $X$ là $12$ người trong tổ cậu ; tập hợp $Y$ là $11$ số tự nhiên từ $0$ đến $10$ (điểm bài kiểm tra)
Với mỗi người trong tổ (thuộc $X$) đều có $1$ con số (thuộc $Y$) là điểm kiểm tra của người đó. "Có một ÁNH XẠ từ $X$ đến $Y$"
Giả sử bạn cậu (là bạn cậu, chứ không phải cậu, tên $A$ chẳng hạn) "được" $0$ điểm thì "$0$ là ảnh của $A$ ; $A$ là nghịch ảnh của $0$"
Cũng có thể có mấy trường hợp sau :
a) Hôm làm kiểm tra, tổ cậu có $4$ bạn "trốn học có phép" nên không làm bài. Như vậy tập $X$ chỉ còn $8$ người. Giả sử trong $8$ người này, không có $2$ người nào có cùng số điểm. "Ta có một ĐƠN ÁNH" (lời nhà toán học)
b) Hôm làm kiểm tra tổ đi đầy đủ. Kết quả bài làm của tổ, từ $0$ đến $10$, điểm nào cũng có (thậm chí cậu và bạn $A$ của cậu có cùng số điểm). "Đây là một TOÀN ÁNH"
c) Bạn $A$ của cậu "được" $0$ điểm, xấu hổ quá, đòi bố mẹ xin chuyển trường và đã được chấp thuận ngay (vì bệnh thành tích, trường chẳng quyến luyến gì). Bây giờ tập $X$ chỉ còn $11$ người. Giả sử kết quả kiểm tra, từ $0$ đến $10$ điểm nào cũng có thì "Trong tổ của cậu có một SONG ÁNH"
 
Giờ thì cậu đã ngộ ra chưa ?

Thế thì nhà toán học nói gì về 2 trường hợp cực đoan sau:
d1) Trong tập $X$ có cậu có tính trăng hoa một lúc yêu 2,3 cô,
d2) và cũng có cậu mặc cảm không dám yêu ai...
N.B.xin cà khịa 1 tí...:-)

Cuối tuần và để nâng cấp cuộc chơi, em xin đề nghị bài toán :
Có bao nhiêu cách xếp khác nhau của từ TALENTENGINEER, trong đó các chữ cái giống nhau không đứng cạnh nhau.
N.B. Nếu có thể, xin trình bày cách sơ cấp, cách thấp cấp... :-) để tiếp cận bài toán (hoặc một cách nào khác cũng welcome).
Mong các chuẩn kỹ sư tài năng (bao gồm cả những ai suýt là talent engineer...) tham gia, giải trí vui là chính.
Nếu thấy bổ ích, xin thầy (cô), anh (chị) và các bạn like, subscribe, share. Thank for watching...:-) (Sorry, xem mãi rồi lậm...)

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 2:
Ta có :
$f(x)=\left ( \binom{10}{1}x+\binom{10}{2}x^2+\binom{10}{3}x^3+\binom{10}{4}x^4 \right )\left ( \binom{10}{1}x+\binom{10}{2}x^2+\binom{10}{3}x^3 \right )\left ( \binom{10}{1}x+\binom{10}{2}x^2 \right )$
$\Longrightarrow 6![x^6]f(x)=\boldsymbol {579600}$

OMG, hàm sinh này copy ở đâu mà paste vô đây??? Sorry các bạn, chắc bị sock vì tên các nhân vật lẫy lừng trong các bài toán này!!! Các bạn xem giúp lại nhé, hàm sinh là :
$$\begin {align*}
f(x)&=\left ( 1+\binom{5}{1}x+\binom{5}{2}x^2+\binom{5}{3}x^3+\binom{5}{4}x^4 \right )\\
&\times \left ( 1+\binom{4}{1}x+\binom{4}{2}x^2+\binom{4}{3}x^3\right )\\
&\times \left ( 1+\binom{3}{1}x+\binom{3}{2}x^2 \right)\\
\Rightarrow 6![x^6]f(x)&=579600
\end{align*}$$

@Nobodyv3 Em chú ý giữa left(….right) không được ngắt hàng. Giải pháp thay bằng Big( và Big) nó được hiểu là ký hiệu mà không phải môi trường.

Báo cáo với thầy, em vừa học được 1 chiêu cũ người mới ta :
Ngoài giải pháp sử dụng [ \Bigg (....xuonghang...\Bigg ( ] ta cũng có thể dùng:
[\left (...xuonghang\right. $\backslash\backslash$
\left. ...xuonghang\right.$\backslash\backslash$
...............
\left. ...\right)]
Thí dụ :
$$\begin{align*}
f(x)&=\left( x+\frac{x^2}{2!}+\left ( \binom{3}{0}+\binom{3}{1} \right )\frac{x^3}{3!}\right.\\
&\left.+\left (\binom{4}{0}+\binom{4}{1} \right )\frac{x^4}{4!} +\left (\binom{5}{0}+\binom{5}{1}+\binom{5}{2} \right )\frac{x^5}{5!}\right.\\
&\left.+\left (\binom{6}{0}+\binom{6}{1}+\binom{6}{2}\right )\frac{x^6}{6!}\right.\\
&\left.+\left (\binom{7}{0}+\binom{7}{1}+\binom{7}{2}+\binom{7}{3}\right )\frac{x^7}{7!}\right )e^{3x}\\
&=\sum_{n\geq 0}\left( x+ \frac{x^2}{2!}+\frac{4x^3}{3!}+ \frac{5x^4}{4!}+\frac{16x^5}{5!}\right.\\
&\qquad\quad \left.+\frac{22x^6}{6!}+ \frac{64x^7}{7!} \right )\frac {3^nx^n}{n!}\\
\end{align*}$$
======
Mong ước phổ biến giải pháp này đến các bạn quan tâm, xem như lời tri ân cụ thể đến thầy @hxthanh.