Đến nội dung

Hình ảnh

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

- - - - -

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

#1
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
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.
===========
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
chanhquocnghiem

chanhquocnghiem

    Thiếu tá

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

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 ...

 

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


#3
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viế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.

Em thì thấy bài toán rối hơn nhiều!
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

===========
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
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
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 ....

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 15-05-2023 - 23:21

===========
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
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3915 Bài viết
Một ví dụ rất hay của “Barcelona” number

#6
Nobodyv3

Nobodyv3

    Generating Functions Faithful

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

Một ví dụ rất hay của “Barcelona” number

Hello thầy.
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
Nobodyv3

Nobodyv3

    Generating Functions Faithful

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

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 ....

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!).
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*}$$
===========
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