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
#2
Đã gửi 18-02-2013 - 18:23
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
Cảm ơn bạn rất nhiều ... Mình đã xem mà quên mất cái này ''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
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
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh