Cho $n$ là số nguyên dương. Có bao nhiêu cách nối $2n$ điểm trên một đường tròn bằng $n$ dây cung sao cho không có hai dây cung nào cắt nhau
Cho $n$ là số nguyên dương. Có bao nhiêu cách nối $2n$ điểm trên một đường tròn bằng $n$ dây cung sao cho không có hai dây cung nào cắt nhau
Bắt đầu bởi LotusSven, 16-02-2013 - 23:16
#2
Đã gửi 18-02-2013 - 18:23
hxthanh
-
- Hiệp sỹ
-
- 3921 Bài viết
Tín đồ $\sum$
Dễ nhận thấy rằng nếu ta nối 2 điểm bất kỳ của đường tròn sao cho "ở giữa" 2 điểm đó có một số lẻ điểm khác thì sẽ không bao giờ thỏa yêu cầu đề bài.
Vì vậy ta sẽ phải nối sao cho giữa hai điểm bất kỳ có một số chẵn điểm khác, ta gọi dây cung nối như vậy là dây cung đúng!
Gọi cách nối $2n$ điểm thỏa đề bài là $S_n$, quy ước $S_0=1$
Một dây cung đúng bất kỳ chia tập hợp điểm trên đường tròn làm $2$ nửa, với $2k$ điểm một bên và $2n-2-2k$ điểm nửa còn lại
Như vậy ta có:
\begin{equation}\label{eq1} S_n=\sum_{k=0}^{n-1}S_kS_{n-1-k}\end{equation}
Dễ dàng nhận ra \eqref{eq1} chính là hệ thức truy hồi của số Catalan $\complement_n$
Do đó: $S_n=\complement_n=\dfrac{{2n\choose n}}{n+1}=\dfrac{(2n)!}{n!(n+1)!}$
Công việc còn lại dành cho bạn
Vì vậy ta sẽ phải nối sao cho giữa hai điểm bất kỳ có một số chẵn điểm khác, ta gọi dây cung nối như vậy là dây cung đúng!
Gọi cách nối $2n$ điểm thỏa đề bài là $S_n$, quy ước $S_0=1$
Một dây cung đúng bất kỳ chia tập hợp điểm trên đường tròn làm $2$ nửa, với $2k$ điểm một bên và $2n-2-2k$ điểm nửa còn lại
Như vậy ta có:
\begin{equation}\label{eq1} S_n=\sum_{k=0}^{n-1}S_kS_{n-1-k}\end{equation}
Dễ dàng nhận ra \eqref{eq1} chính là hệ thức truy hồi của số Catalan $\complement_n$
Do đó: $S_n=\complement_n=\dfrac{{2n\choose n}}{n+1}=\dfrac{(2n)!}{n!(n+1)!}$
Công việc còn lại dành cho bạn
- E. Galois, perfectstrong, batigoal và 3 người khác yêu thích
#3
Đã gửi 19-02-2013 - 22:02
LotusSven
-
- Thành viên
-
- 26 Bài viết
Binh nhất
Cảm ơn bạn rất nhiều ... Mình đã xem mà quên mất cái nàyDễ nhận thấy rằng nếu ta nối 2 điểm bất kỳ của đường tròn sao cho "ở giữa" 2 điểm đó có một số lẻ điểm khác thì sẽ không bao giờ thỏa yêu cầu đề bài.
Vì vậy ta sẽ phải nối sao cho giữa hai điểm bất kỳ có một số chẵn điểm khác, ta gọi dây cung nối như vậy là dây cung đúng!
Gọi cách nối $2n$ điểm thỏa đề bài là $S_n$, quy ước $S_0=1$
Một dây cung đúng bất kỳ chia tập hợp điểm trên đường tròn làm $2$ nửa, với $2k$ điểm một bên và $2n-2-2k$ điểm nửa còn lại
Như vậy ta có:
\begin{equation}\label{eq1} S_n=\sum_{k=0}^{n-1}S_kS_{n-1-k}\end{equation}
Dễ dàng nhận ra \eqref{eq1} chính là hệ thức truy hồi của số Catalan $\complement_n$
Do đó: $S_n=\complement_n=\dfrac{{2n\choose n}}{n+1}=\dfrac{(2n)!}{n!(n+1)!}$
Công việc còn lại dành cho bạn
''2. Ứng dụng: Một số bài toán có kết quả là dãy số Catalan
- Số cách nối 2n điểm trên đường tròn bằng n dây cung không cắt nhau.''
#5
Đã gửi 29-09-2013 - 16:29
tretho97
-
- Thành viên
-
- 37 Bài viết
Binh nhất
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh
