Có bao nhiêu cách nối thành các cặp điểm sao cho khi tất cả các cặp điểm được nối với nhau
#1
Đã gửi 14-05-2023 - 19:03
- hxthanh yêu thích
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...
#2
Đã gửi 15-05-2023 - 10:32
Có 2n điểm phân biệt nằm trên một đường tròn. Hỏi có bao nhiêu cách nối thành các cặp điểm sao cho khi tất cả các cặp điểm được nối với nhau bằng các đoạn thẳng thì n đoạn thẳng này không cắt nhau đôi một.
Có phải ý bạn là : Hỏi có bao nhiêu cách nối các cặp điểm (mỗi điểm chỉ nối với duy nhất $1$ điểm khác) sao cho trong $n$ đoạn thẳng tạo thành, không có cặp đoạn thẳng nào có điểm chung ?
Nếu là như vậy thì xin giải như sau...
--------------------------------------------------------
Đặt tên các điểm đã cho theo chiều kim đồng hồ là $A_1,A_2,...,A_{2n}$
Xét một cách nối thỏa mãn yêu cầu đề bài, trong đó $A_1$ nối với $A_k$.
Nhận xét rằng $A_1$ và $A_k$ chia đường tròn thành 2 cung và số các điểm $A_i$ trên mỗi cung (nằm giữa $A_1$ và $A_k$) đều phải là số chẵn.
Do đó, $k$ chỉ có thể là $2,4,6,...,2n$
Với mỗi giá trị của $k$ chỉ có $1$ cách nối. Vậy có tất cả $n$ cách nối thỏa mãn yêu cầu đề bài.
...
Ðê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 ...
#3
Đã gửi 15-05-2023 - 17:06
Em thì thấy bài toán rối hơn nhiều!Có phải ý bạn là : Hỏi có bao nhiêu cách nối các cặp điểm (mỗi điểm chỉ nối với duy nhất $1$ điểm khác) sao cho trong $n$ đoạn thẳng tạo thành, không có cặp đoạn thẳng nào có điểm chung ?
Nếu là như vậy thì xin giải như sau...
--------------------------------------------------------
Đặt tên các điểm đã cho theo chiều kim đồng hồ là $A_1,A_2,...,A_{2n}$
Xét một cách nối thỏa mãn yêu cầu đề bài, trong đó $A_1$ nối với $A_k$.
Nhận xét rằng $A_1$ và $A_k$ chia đường tròn thành 2 cung và số các điểm $A_i$ trên mỗi cung (nằm giữa $A_1$ và $A_k$) đều phải là số chẵn.
Do đó, $k$ chỉ có thể là $2,4,6,...,2n$
Với mỗi giá trị của $k$ chỉ có $1$ cách nối. Vậy có tất cả $n$ cách nối thỏa mãn yêu cầu đề bài.
Gọi $c_n$ là số cách nối $2n$ điểm thỏa yêu cầu. Ta cho n vài giá trị nho nhỏ (để đếm đủ trên 10 đầu ngón tay), nối $A_1$ với các $A_{2n}$ rồi đếm " thủ công " thì thấy $c_n$ có các giá trị như sau :
( Ghi chú: ký hiệu $(A_i-A_j)$ là nối điểm $A_i$ với $A_j$.)
$- n=0: 1 $ cách
$- n=1:[( A_1-A_2)]\Rightarrow 1$ cách
$$- n=2: [(A_1-A_4)(A_2-A_3)] , [(A_1-A_2)(A_3-A_4)] \Rightarrow 2$$ cách
$$- n=3:[ (A_1-A_6)(A_2-A_5)(A_3-A_4)],[(A_1-A_6
)(A_2-A_3)(A_4-A_5) ] ,[(A_1-A_4)(A_2-A_3)(A_5-A_6) ],[(A_1-A_2)(A_3-A_4)(A_5-A_6) ],[(A_1-A_2)(A_3-A_6)(A_4-A_5) ] \Rightarrow 5$$ cách
$- n=4 \Rightarrow 14 $ cách (số cách nối hơi bị nhiều nên xin phép không liệt kê các cách nối trong trường hợp này)
...vv.....
Như vậy, với mỗi giá trị $k$ sẽ có số các cách nối khác nhau do đó khả năng $c_n\neq n$ là rất lớn!.
Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 15-05-2023 - 18:00
- hxthanh và chanhquocnghiem thích
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...
#4
Đã gửi 15-05-2023 - 22:09
.....Vẫn sử dụng các đặt để, lập luận đã posted ở trên, ta thấy $A_1$ chỉ có thể nối với $A_2, A_4,...,A_{2n}$. Một khi $A_{1}$ nối với $ A_{2m}$ thì $2(m-1)$ điểm $A_2, A_3,...,A_{2m-1}$ nối với nhau từng cặp theo $c_{m-1}$ cách, và $2(n-m)$ điểm $A_{m+1}, A_{m+2},...,A_{2n}$ phải được nối với nhau từng cặp theo $c_{n-m}$ cách. Cho nên, đặt $c_0=1$ thì ta có hệ thức truy hồi cho dãy $ \left \{ c_n \right \} $ là:
$$c_n=c_0c_{n-1}+c_1c_{n-2}+c_2c_{n-3}+...+c_{n-1}c_0$$ $(*)$
Giải $(*)$, đặt $f(x)=c_0+c_1x+c_2x^2+...$ thì :
$$f(x)^2=(c_0c_0)+(c_0c_1+c_1c_0)x+(c_0c_2+c_1c_1+c_2c_0)x^2+...=c_1+c_2x+c_3x^2+...$$
$\Rightarrow xf(x)^2=f(x)-1$. Giải phương trình bậc 2 theo $f(x)$:
$\Rightarrow f(x)=\frac {1\pm \sqrt{1-4x}}{2x}$. Nhận thấy để có $\lim_{x\rightarrow 0}f(x)=c_0$ thì $f(x)=\frac {1-\sqrt{1-4x}}{2x}$ và sử dụng khai triển $$(1-x)^{1/2}=1-\sum_{n=1}^{\infty }\frac {2}{n}\cdot \frac {(2n-2)!}{(2^n(n-1)!)^2}$$ ta có :
$\begin {align*}
f(x)&=\frac {1}{2x}\left (1-\sqrt {1-4x}\right )\\
&=\frac {1}{2x}\sum_{n=1}^{\infty }\frac {2}{n}\binom {2n-2}{n-1}x^n\\
&=\sum_{n=1}^{\infty }\frac {1}{n}\binom {2n-2}{n-1}x^{n-1}\\
&=\sum_{n=0}^{\infty }\frac {1}{n+1}\binom {2n}{n}x^{n}
\end{align*}$
Suy ra : $\boldsymbol {c_n=\frac {1}{n+1}\binom {2n}{n}}$
Số này thấy quen quen ....
Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 15-05-2023 - 23:21
- hxthanh yêu thích
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...
#5
Đã gửi 16-05-2023 - 08:15
#6
Đã gửi 16-05-2023 - 13:29
Hello thầy.Một ví dụ rất hay của “Barcelona” number
Welcome back.
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
Đã gửi 20-05-2023 - 19:50
Phần cuối hơi vắn tắt nên để giải thích rõ hơn, ta làm lại từ từ nhé. ( kẻo bị tẩu hỏa nhập ma, mất hết 20 năm võ công khổ luyện!).Em xin trình bày luôn :
.....Vẫn sử dụng các đặt để, lập luận đã posted ở trên, ta thấy $A_1$ chỉ có thể nối với $A_2, A_4,...,A_{2n}$. Một khi $A_{1}$ nối với $ A_{2m}$ thì $2(m-1)$ điểm $A_2, A_3,...,A_{2m-1}$ nối với nhau từng cặp theo $c_{m-1}$ cách, và $2(n-m)$ điểm $A_{m+1}, A_{m+2},...,A_{2n}$ phải được nối với nhau từng cặp theo $c_{n-m}$ cách. Cho nên, đặt $c_0=1$ thì ta có hệ thức truy hồi cho dãy $ \left \{ c_n \right \} $ là:
$$c_n=c_0c_{n-1}+c_1c_{n-2}+c_2c_{n-3}+...+c_{n-1}c_0$$ $(*)$
Giải $(*)$, đặt $f(x)=c_0+c_1x+c_2x^2+...$ thì :
$$f(x)^2=(c_0c_0)+(c_0c_1+c_1c_0)x+(c_0c_2+c_1c_1+c_2c_0)x^2+...=c_1+c_2x+c_3x^2+...$$
$\Rightarrow xf(x)^2=f(x)-1$. Giải phương trình bậc 2 theo $f(x)$:
$\Rightarrow f(x)=\frac {1\pm \sqrt{1-4x}}{2x}$. Nhận thấy để có $\lim_{x\rightarrow 0}f(x)=c_0$ thì $f(x)=\frac {1-\sqrt{1-4x}}{2x}$ và sử dụng khai triển $$(1-x)^{1/2}=1-\sum_{n=1}^{\infty }\frac {2}{n}\cdot \frac {(2n-2)!}{(2^n(n-1)!)^2}$$ ta có :
$\begin {align*}
f(x)&=\frac {1}{2x}\left (1-\sqrt {1-4x}\right )\\
&=\frac {1}{2x}\sum_{n=1}^{\infty }\frac {2}{n}\binom {2n-2}{n-1}x^n\\
&=\sum_{n=1}^{\infty }\frac {1}{n}\binom {2n-2}{n-1}x^{n-1}\\
&=\sum_{n=0}^{\infty }\frac {1}{n+1}\binom {2n}{n}x^{n}
\end{align*}$
Suy ra : $\boldsymbol {c_n=\frac {1}{n+1}\binom {2n}{n}}$
Số này thấy quen quen ....
Xin tiếp theo từ $f(x)=\frac {1-\sqrt {1-4x}}{2x}$
Khai triển Taylor của $\sqrt{1-4x}$:
$$\begin {align*}
\sqrt {1-4x}&=1+\sum_{n=1}^{\infty }\binom {1/2}{n}\left ( -4 \right )^nx^n\\
\text{mà }\binom {1/2}{n} &=\frac {\frac {1}{2}\cdot\frac {-1}{2}\cdot\frac {-3}{2}\cdots\frac {-2n+3}{2}}{n!}\\
&=(-1)^{n-1}\frac {1\cdot 1\cdot 3\cdot 5\cdot 7\cdots (2n-3)}{2^nn!}\\
&=(-1)^{n-1}\frac {1\cdot 2\cdot 3\cdot 4\cdot 5\cdots (2n-2)}{2^nn!}\cdot \frac {1}{2\cdot 4\cdot 6\cdots (2n-2)}\\
&=(-1)^{n-1}\frac {(2n-2)!}{2^nn!}\cdot \frac {1}{2^{n-1}(n-1)!}\\
&=(-1)^{n-1}\frac {(2n-2)!}{2^n(n-1)!n}\frac {1}{2^{n-1}(n-1)!}\\
\Rightarrow \sqrt {1-4x}&=1+\sum_{n=1}^{\infty }\binom {1/2}{n}(-4)^nx^n\\
&=1+\sum_{n=1}^{\infty }\left ( (-1)^{n-1}\binom {2n-2}{n-1}\frac {1}{n2^{2n-1}} \right )(-4)^nx^n\\
&=1-2\sum_{n=1}^{\infty }\frac {1}{n}\binom {2n-2}{n-1}x^n\\
\text{do đó }f(x)&=\frac {1-\sqrt{1-4x}}{2x}\\
&=\frac {1-\left ( 1-2\sum_{n=1}^{\infty }\frac {1}{n}\binom {2n-2}{n-1}x^n \right )}{2x}\\
&=\sum_{n=1}^{\infty }\frac {1}{n}\binom {2n-2}{n-1}x^{n-1}\\
&=\sum_{n=0}^{\infty }\frac {1}{n+1}\binom {2n}{n}x^n\\
\Rightarrow c_n&=\boldsymbol {\frac {1}{n+1}\binom {2n}{n}}
\end{align*}$$
- perfectstrong yêu thích
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...
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh