Chủ đề này có 9 trả lời

[Nobodyv3]

1/(bài toán thường gặp) Có bao nhiêu cách chọn 3 số từ tập ${1,2,...,3n}$ sao cho tổng 3 số này chia hết cho 3.
2/ Gọi $ A$ là một bảng chữ cái được tạo thành từ $n$ cặp chữ cái giống nhau $a_{1}, a_{1};
a_{2}, a_{2}; a_{3}, a_{3}; ..; a_{n}, a_{n}$. Các cặp khác nhau chứa các chữ cái khác nhau. Hãy viết biểu thức tính số các từ sử dụng tất cả $2n$ chữ cái trong bảng $A$ sao cho không có chữ cái liền kề nào giống nhau.

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 26-10-2022 - 14:04

[Nobodyv3]

1/ Đặt
$A=\left \{ m\mid1\leq m\leq 3n,m\equiv 0\pmod3 \right \} ;\\
B=\left \{ m\mid1\leq m\leq 3n,m\equiv 1\pmod3 \right \} ;\\
C=\left \{ m\mid1\leq m\leq 3n,m\equiv 2\pmod3 \right \}$
suy ra $\left | A \right |=\left | B \right |=\left | C \right |=n.$
Tổng 3 số $a+b+c\equiv 0\pmod3$ khi và chỉ khi $a,b,c\in A$ hoặc $a,b,c\in B$ hoặc $a,b,c\in C$ hoặc $a,b,c\in$ mỗi tập khác nhau. Vậy số cách chọn thỏa yêu cầu là :$3C_{n}^{3}+n^3=\boldsymbol {\frac{n\left ( 3n^2-3n+2 \right )}{2}}$

[Nobodyv3]

2/( Đây là tổng quát hóa bài toán tại:
https://diendantoanh...à-không-có-2-s/
và mình sẽ dùng bài này để test công thức vừa tính được.)
========
Bài 2: Giải:
Số các từ sử dụng toàn bộ $2n$ chữ cái của bảng A là $\frac{(2n)!}{(2!)^n}=\frac{(2n)!}{2^n}.$
Gọi $A_i$ là tập các từ được lập từ $2n$ chữ cái mà trong đó 2 chữ cái $a_i$ đứng kề nhau. Như vậy, số các từ cần tìm là :
$$N=\frac{(2n)!}{2^n}-\left | A_1\cup A_2\cup ...\cup A_n \right |$$
Theo nguyên lý bù trừ ta có :
$\begin {align*}
\left | A_1\cup A_2\cup ...\cup A_n \right |&=\sum_{i=1}^{n}\left | A_i \right |-\sum_{1\leq i< j\leq n}\left | A_i\cap A_j \right |+...\\
&+(-1)^{k-1}\sum_{1\leq i_1<...< i_k\leq n }\left | A_{i_1}\cap A_{i_2}\cap ...\cap A_{i_k} \right |+...\\
&+(-1)^{n-1}\left | \bigcap_{i=1}^{n}A_i \right |
\end {align*}$
Ta tiến hành tính số phần tử của $A_{i_1}\cap A_{i_2}\cap ...\cap A_{i_k}$: nếu một từ thuộc tập này thì nó cũng thuộc mỗi tập $A_{i_1}, A_{i_2},..., A_{i_k}$ và do đó các chữ cái $a_{i_1}, a_{i_1};a_{i_2}, a_{i_2};...,a_{i_k}, a_{i_k}$ đứng kề nhau. Ta xét cách tạo ra các từ có $k$ cặp chữ cái kề nhau như sau: Bằng cách lấy ra $ k$ " bản sao" của các chữ cái $a_{i_1},a_{i_2},..., a_{i_k}$ ta được các từ có kích thước $2n-k$, sau đó ta đưa các "bản sao " này vào lại nhưng ở vị trí kề bên các chữ cái mà chúng sẽ tạo nên $k$ cặp chữ cái kề nhau và cuối cùng ta được từ có kích thước $2n$ mà trong đó có ít nhất $k$ cặp chữ cái kề nhau. Cho nên ta có :
$\left | A_{i_1}\cap A_{i_2}\cap ...\cap A_{i_k} \right |=\frac{(2n-k)!}{(2!)^{n-k}}=\frac{2^k(2n-k)!}{2^n}.$
Do các chỉ số $i_1, i_2,...,i_k $ thỏa $1\leq i_1< i_2<...<i_k\leq n$ nên có $\binom{n}{k}$ cách chọn các chỉ số này và cuối cùng ta có số các từ thỏa yêu cầu là :
$N=\frac{(2n)!}{2^n}-\binom{n}{1}\frac{2(2n-1)!}{2^n}+\binom{n}{2}\frac{2^2(2n-2)!}{2^n}-...+\frac{(-1)^n2^nn!}{2^n}=\binom{n}{0}\frac{2^0(2n-0)!}{2^n}-\binom{n}{1}\frac{2^1(2n-1)!}{2^n}+\binom{n}{2}\frac{2^2(2n-2)!}{2^n}-...+\frac{(-1)^n2^nn!}{2^n}$
hay gọn hơn :
$\boldsymbol {N=\frac{1}{2^n}\sum_{k=0}^{n}\binom{n}{k}(-1)^k2^k(2n-k)!}$
Edited theo anh @chanhquocnghiem.
_______________
TEST:
Đề bài :(link bên trên)
có thể lập được bao nhiêu chữ số gồm 8 chữ số từ 1,2,3,4 mỗi chữ số có mặt 2 lần và không có 2 số giống nhau đứng cạnh nhau

Test công thức trên nhé!
$N=\frac{1}{2^4}\left ( 8!- 4\cdot2\cdot7!+6\cdot4\cdot6!-4\cdot8\cdot5!+16\cdot4! \right )=\boldsymbol {864} $
Kết quả khớp với đáp án của các cây Đa, cây Đề!

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 28-10-2022 - 07:57

[chanhquocnghiem]

$N=\frac{1}{2^n}\left ( \sum_{k=0}^{n}C_n^k(-2)^k(2n-k)! \right )$ (ghi kết quả này cho nó "đẹp")

Thực tế dùng công thức $N=\frac{1}{2^n}\left ( \sum_{k=2}^{n}C_n^k(-2)^k(2n-k)! \right )$ để tính cho nhanh.

Bài viết đã được chỉnh sửa nội dung bởi chanhquocnghiem: 28-10-2022 - 07:31

[Nobodyv3]

$N=\frac{1}{2^n}\left ( \sum_{k=2}^{n}C_n^k(-2)^k(2n-k)! \right )$.

À, $k$ chạy từ $0$ đến $n$ và công thức này được chứng minh ra sao, anh nhỉ...

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 28-10-2022 - 07:41

[chanhquocnghiem]

Hình như còn thiếu vài số hạng thì phải... ? và chứng minh công thức này được không anh.

$N=\frac{1}{2^n}\left [ (2n)!-\sum_{k=1}^{n}C_n^k(-1)^{k-1}2^k(2n-k)! \right ]=\frac{1}{2^n}\left [ (2n)!+\sum_{k=1}^{n}C_n^k(-1)^k2^k(2n-k)! \right ]=\frac{1}{2^n}\left [ (2n)!+\sum_{k=1}^{n}C_n^k(-2)^k(2n-k)! \right ]=\frac{1}{2^n}\left ( \sum_{k=0}^{n}C_n^k(-2)^k(2n-k)! \right )=\frac{1}{2^n}\left ( \sum_{k=2}^{n}C_n^k(-2)^k(2n-k)! \right )$
 

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

[chanhquocnghiem]

À, $k$ chạy từ $0$ đến $n$ và công thức này được chứng minh ra sao, anh nhỉ...

Vì 2 số hạng đầu tiên của tổng (ứng với $k=0$ và $k=1$) triệt tiêu lẫn nhau nên có thể cho $k$ chạy từ $0$ hay từ $2$ cũng như nhau thôi
 

[Nobodyv3]

[quote name="chanhquocnghiem" post="735501" timestamp="1666918575" date="Hôm nay, 07:56"]
Vì 2 số hạng đầu tiên của tổng (ứng với $k=0$ và $k=1$) triệt tiêu lẫn nhau nên có thể cho $k$ chạy từ $0$ hay từ $2$ cũng như nhau thôi
Đúng vậy.

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

[Nobodyv3]

$N=\frac{1}{2^n}\left [ (2n)!-\sum_{k=1}^{n}C_n^k(-1)^{k-1}2^k(2n-1)! \right ]=\frac{1}{2^n}\left [ (2n)!+\sum_{k=1}^{n}C_n^k(-1)^k2^k(2n-1)! \right ]=\frac{1}{2^n}\left [ (2n)!+\sum_{k=1}^{n}C_n^k(-2)^k(2n-1)! \right ]=\frac{1}{2^n}\left ( \sum_{k=0}^{n}C_n^k(-2)^k(2n-1)! \right )=\frac{1}{2^n}\left ( \sum_{k=2}^{n}C_n^k(-2)^k(2n-1)! \right )$

Ý em là tò mò muốn biết từ đâu ra được công thức này.(còn em phải lập luận nhiều, tính toán nhiêu khê... mới ra được công thức trên!)

[chanhquocnghiem]

Ý em là tò mò muốn biết từ đâu ra được công thức này.(còn em phải lập luận nhiều, tính toán nhiêu khê... mới ra được công thức trên!)

Sorry, mình gõ nhầm nhé, $(2n-k)!$ chứ không phải $(2n-1)!$ (đã sửa ở trên)