Đến nội dung

Hình ảnh

Có bao nhiêu cách xếp $a,a,a,a,b,b,b,b,c,c,c,c$

* * * * * 1 Bình chọn

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

#1
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 928 Bài viết
Có bao nhiêu cách xếp $a,a,a,a,b,b,b,b,c,c,c,c$ sao cho:
a/ Không chữ cái nào chiếm 4 vị trí liên tiếp
b/ Không chữ cái nào chiếm 3 vị trí liên tiếp.
c/ Không chữ cái nào chiếm 2 vị trí liên tiếp.
(Edited)

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 11-11-2022 - 08:58

<p>
advice
Once is chance. Twice is coincidence. Thrice is a pattern.

#2
chanhquocnghiem

chanhquocnghiem

    Thiếu tá

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

Có bao nhiêu cách xếp $a,a,a,a,b,b,b,b,c,c,c,c$ sao cho:
a/ Không chữ cái nào chiếm 4 vị trí liên tiếp

a) Số cách sắp xếp ngẫu nhiên $12$ chữ cái đã cho là $M=\frac{12!}{(4!)^3}=\frac{12!}{24^3}$.

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

    - Chọn $k$ loại chữ cái trong số $3$ loại chữ cái : $C_3^k$ cách.

    - Với mỗi loại chữ cái (trong $k$ loại đã chọn), ta ghép $4$ chữ cái giống nhau, xem như $1$ chữ cái đặc biệt. Như vậy, từ $12$ chữ cái ban đầu, nay chỉ còn $12-3k$ chữ cái

    - Sắp xếp ngẫu nhiên $12-3k$ chữ cái đó : Có $\frac{(12-3k)!}{(4!)^{3-k}}=\frac{24^k(12-3k)!}{24^3}$ cách

    $\Rightarrow M_k=C_3^k\ \frac{24^k(12-3k)!}{24^3}$

    Và số cách sắp xếp thỏa mãn điều kiện đề bài là

    $M-M_1+M_2-M_3=\frac{12!}{24^3}+\sum_{k=1}^{3}C_3^k\frac{(-1)^k24^k(12-3k)!}{24^3}=\frac{1}{24^3}\sum_{k=0}^{3}C_3^k(-24)^k(12-3k)!=32844$.
 


...

Ðê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)


#3
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 928 Bài viết
Em đang tập tễnh sử dụng đa thức Laguerre để giải.
Định lý : Cho $m_1,...,m_k, n_1,...,n_k$ là các số nguyên không âm và $p_{m,n}(t)$ là đa thức $\sum_{n=0}^{\infty }p_{m,n}(t)x^n=\exp\left ( \frac{t\left ( x-x^m \right )}{1-x^m} \right )$ thì số các từ có $k $ loại chữ cái trong đó chữ cái $i$ có đúng $n_i$ lần và không có từ con $i^{m_i}$ là $\int_{0}^{\infty }e^{-t}\prod_{j=1}^{k}p_{m_j,n_j}(t)dt .$
Áp dụng vào bài toán.
a/ Ở đây các từ không hợp lệ khi chứa các từ con $ \left \{ aaaa,bbbb,cccc \right \}. $
Ta có :$m_1= m_2=m_3=4 , n_1= n_2=n_3=4 $ nên :
$\begin {align*}
p_{4,4}(t)&=\left [ x^4 \right ]\exp\left ( \frac{t(x-x^4)}{1-x^4} \right )\\
&=\left [ x^4 \right ]\left ( ...+\left ( \frac{1}{24}t^4-t\right )x^4+... \right )\\
&=\frac{1}{24}t^4-t
\end {align*}$
Suy ra :
$\int_{0}^{\infty }e^{-t}\left ( \frac{1}{24}t^4-t\right )^3dt=\boldsymbol {32844}$
b/ Ở đây các từ không hợp lệ khi chứa các từ con $ \left \{ aaa,bbb,ccc \right \}. $
Ta có :$m_1= m_2=m_3=3 , n_1= n_2=n_3=4 $ nên :
$\begin {align*}
p_{3,4}(t)&=\left [ x^4 \right ]\exp\left ( \frac{t(x-x^3)}{1-x^3} \right )\\
&=\left [ x^4 \right ]\left ( ...+\left ( \frac{1}{24}t^4-t^2+t \right )x^4+... \right )\\
&=\frac{1}{24}t^4-t^2+t
\end {align*}$
Suy ra :
$\int_{0}^{\infty }e^{-t}\left ( \frac{1}{24}t^4-t^2+t \right )^3dt=\boldsymbol {21084}$
<p>
advice
Once is chance. Twice is coincidence. Thrice is a pattern.

#4
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 928 Bài viết
Nhân đây, em xin dùng cách tiếp cận này để giải bài toán quen thuộc sau :
Có bao nhiêu cách sắp xếp từ $MISSISSIPPI$ sao cho các chữ cái giống nhau không đứng kề nhau.

Giải :
- Đa thức cho chữ cái $I, S$:
$\begin {align*}
p_{2,4}(t)&=\left [ x^4 \right ]\exp\left ( \frac{t(x-x^2)}{1-x^2} \right )\\
&=\left [ x^4 \right ]\left ( ...+\left ( \frac{1}{24}t^4-\frac{1}{2}t^3+\frac{3}{2}t^2-t\right )x^4+... \right )\\
&=\frac{1}{24}t^4-\frac{1}{2}t^3+\frac{3}{2}t^2 -t
\end {align*}$
- Đa thức cho chữ cái $P$:
$\begin {align*}
p_{2,2}(t)&=\left [ x^2 \right ]\exp\left ( \frac{t(x-x^2)}{1-x^2} \right )\\
&=\left [ x^2 \right ]\left ( ...+\left(\frac{1}{2}t^2-t\right )x^2+... \right )\\
&=\frac{1}{2}t^2 -t
\end {align*}$
- Đa thức cho chữ cái $M$:
$\begin {align*}
p_{2,1}(t)&=\left [ x^1 \right ]\exp\left ( \frac{t(x-x^2)}{1-x^2} \right )\\
&=\left [ x^1\right ]\left ( ...+tx^1+... \right )\\
&=t
\end {align*}$
Vậy :
$\int_{0}^{\infty }e^{-t}\left ( \frac{1}{24}t^4-\frac{1}{2}t^3+\frac{3}{2}t^2 - t \right )^2\left (\frac{1}{2}t^2 - t \right ) (t) dt=\boldsymbol {2016}$

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 08-11-2022 - 01:08

<p>
advice
Once is chance. Twice is coincidence. Thrice is a pattern.

#5
chanhquocnghiem

chanhquocnghiem

    Thiếu tá

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

Có bao nhiêu cách xếp $a,a,a,a,b,b,b,b,c,c,c,c$ sao cho:
b/ Không chữ cái nào chiếm 3 vị trí liên tiếp.

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 $3$ 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ố $3$ loại chữ cái : $C_3^k$ cách.

    - Với mỗi loại chữ cái (trong $k$ loại đã chọn), ta ghép $3$ chữ cái giống nhau, xem như $1$ chữ cái đặc biệt. Như vậy, từ $12$ chữ cái ban đầu, nay chỉ còn $12-2k$ chữ cái. Ta gọi 2 chữ cái, ví dụ $a$ và $aaa$ 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 $12-2k$ 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(12-2k-j)!}{24^{3-k}}$

$\Rightarrow S_k=C_3^k\sum_{j=0}^{k}(-1)^jC_k^j\frac{M_j}{2^j}=\frac{C_3^k}{24^{3-k}}\sum_{j=0}^{k}(-1)^jC_k^j(12-2k-j)!$

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


Bài viết đã được chỉnh sửa nội dung bởi chanhquocnghiem: 08-11-2022 - 22:24

...

Ðê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)


#6
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 928 Bài viết
@chanhquocnghiem: Kết quả trùng khớp! Thank you.
<p>
advice
Once is chance. Twice is coincidence. Thrice is a pattern.

#7
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 928 Bài viết
Để cho trọn vẹn, em xin bổ sung thêm câu:
c/ Không chữ cái nào chiếm 2 vị trí liên tiếp.
<p>
advice
Once is chance. Twice is coincidence. Thrice is a pattern.

#8
chanhquocnghiem

chanhquocnghiem

    Thiếu tá

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

Có bao nhiêu cách xếp $a,a,a,a,b,b,b,b,c,c,c,c$ sao cho:
c/ Không chữ cái nào chiếm 2 vị trí liên tiếp.

Một cách sắp xếp không thỏa mãn khi có chứa một "từ con" thuộc $\left \{ aa,bb,cc \right \}$.

$m_1=m_2=m_3=2$ ; $n_1=n_2=n_3=4$

$p_{2,4}(t)=\left [ x^4 \right ]\exp\left [ \frac{t(x-x^2)}{1-x^2} \right ]=\frac{t^4}{24}-\frac{t^3}{2}+\frac{3t^2}{2}-t$

Số cách sắp xếp thỏa mãn là :

$\int_{0}^{\infty}e^{-t}\left ( \frac{t^4}{24}-\frac{t^3}{2}+\frac{3t^2}{2}-t \right )^3dt=1092$.

 

--------------------------------------------------------------------

Bài này liệu có thể giải theo cách truyền thống được không nhỉ ? Bạn nào có nhã hứng thử nghĩ xem !
 


...

Ðê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)


#9
Nobodyv3

Nobodyv3

    Generating Functions Faithful

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

Một cách sắp xếp không thỏa mãn khi có chứa một "từ con" thuộc $\left \{ aa,bb,cc \right \}$.
$m_1=m_2=m_3=2$ ; $n_1=n_2=n_3=4$
$p_{2,4}(t)=\left [ x^4 \right ]\exp\left [ \frac{t(x-x^2)}{1-x^2} \right ]=\frac{t^4}{24}-\frac{t^3}{2}+\frac{3t^2}{2}-t$
Số cách sắp xếp thỏa mãn là :
$\int_{0}^{\infty}e^{-t}\left ( \frac{t^4}{24}-\frac{t^3}{2}+\frac{3t^2}{2}-t \right )^3dt=1092$.

--------------------------------------------------------------------
Bài này liệu có thể giải theo cách truyền thống được không nhỉ ? Bạn nào có nhã hứng thử nghĩ xem !

- Wow, nhạy quá hen!
- Em dùng hàm sinh giải câu c/ được không anh? Em quen rồi...
Ta có hàm sinh cho số cách sắp xếp các từ thỏa yêu cầu như sau:
$\begin {align*}
f(x)&=\left ( \frac{x^{4}}{4!}-\binom{3}{1}\frac{x^{3}}{3!}+\binom{3}{2}\frac{x^2}{2!}-\binom{3}{3}\frac{x}{1!} \right )^3\\
&=\frac{x^{12}}{13824}-\frac{x^{11}}{384}+\frac{5x^{10}}{128}
-\frac{61x^9}{192}+\frac{49x^8}{32}\\&-\frac{9x^7}{2}
+8x^6-\frac{33x^5}{4}+\frac{9x^4}{2}-x^3
\end{align*}$
Thay các $x^k$ bằng các $k!$ ta được :
$\frac{12!}{13824}-\frac{11!}{384}+\frac{5\cdot10!}{128}-\frac{61\cdot9!}{192}+\frac{49\cdot8!}{32}-\frac{9\cdot7!}{2}+8\cdot6!-\frac{33\cdot5!}{4}+\frac{9\cdot4!}{2}-3!=\boldsymbol {1092}$

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 11-11-2022 - 15:47

<p>
advice
Once is chance. Twice is coincidence. Thrice is a pattern.




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

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