Một số đẳng thức liên quan đến số Catalan

Số Catalan là chủ đề hay và khó mà nhiều bài toán đếm cho ra kết quả là số Catalan, chẳng hạn như bài toán dấu ngoặc, bài toán hành trình Dick, bài toán đoàn quân kiến,... Bài viết "Một số đẳng thức liên quan đến số Catalan" sau đây trình bày về một số đẳng thức đẹp liên quan đến số Catalan. Mời các bạn cùng tham khảo chi tiết mội dung bài viết!
Nội dung trích xuất từ tài liệu:
Một số đẳng thức liên quan đến số Catalan Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 MỘT SỐ ĐẲNG THỨC LIÊN QUAN ĐẾN SỐ C ATALAN Hoàng Minh Quân, THPT Ngọc Tảo, Hà Nội Nguyễn Văn Sơn, THPT Thường Xuân 2 - Thanh Hóa Tóm tắt nội dung Số Catalan là chủ đề hay và khó mà nhiều bài toán đếm cho ra kết quả là số Cata-lan, chẳng hạn như bài toán dấu ngoặc, bài toán hành trình Dick, bài toán đoàn quânkiến,. . . Bài viết sau đây trình bày về một số đẳng thức đẹp liên quan đến số Catalan.1 Bài toán Euler Trước hết để tìm công thức số Catalan, ta xét bài toán Euler sau:Bài toán 1.1. Một cách phân chia thành các tam giác của một đa giác lồi n cạnh Pn (n ≥ 3),là một cách chia Pn thành các tam giác (không tính đến các giao điểm của các đường chéocủa Pn ). Đặt a0 = 1 và n ≥ 1 đặt an là số cách khác nhau để phân chia thành các tam giáccủa đa giác lồi n + 2 cạnh trên mặt phẳng. Chứng minh rằng với n ≥ 1 ta có: a n = a 0 a n −1 + a 1 a n −2 + a 2 a n −3 · · · a n −2 a 1 + a n −1 a 0 .Lời giải. Hiển nhiên a1 = 1. Ta xét P4 , P5 (đa giác lồi 4 và 5 cạnh) như hình vẽ 1 1 4 1 4 2 5 2 3 2 3 3 4 1 1 1 1 2 5 2 5 2 5 2 5 3 4 3 4 3 4 3 4 1 Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Ta ký hiệu đa giác (n + 2) cạnh là Pn+2 . Ta cố định một cách chia trong Pn+2 , (n ≥ 2) . Hiển nhiên n = 1 đẳng thức đúng. Chọn một cạnh bất kỳ, ta ký hiệu cạnh đó là [1, n + 2] được nối từ điểm 1 và điểm(n + 2) của Pn+2 . Ta có cạnh [1, n + 2] thuộc vào duy nhất một tam giác trong cách chianày. Ký hiệu điểm thứ 3 của tam giác có cạnh là [1, n + 2] là r với r = 2, 3, · · · , n + 1 vàtam giác là ∆ (1, n + 2, r ) như hình bên dưới đây. 1 2 n+2 n+1 (1) (2) r Ta thấy ∆ (1, n + 2, r ) chia Pn+2 thành 2 đa giác nhỏ hơn: Đa giác r cạnh (1) và đa giác (n + 3 − r ) cạnh (2) như hình vẽ.Từ định nghĩa, đa giác r cạnh (1) có thể được chia thành các tam giác bằng ar+2 cách,trong khi đó đa giác (n + 3 − r ) cạnh (2) được chia thành các tam giác bằng an+1−r cáchđộc lập nhau. Do đó, theo quy tắc nhân số các tam giác khác nhau được chia thành củaPn+2 bởi tam giác ∆ (1, n + 2, r ) là: ar−2 an+1−r . Do giá trị của r chạy từ 2 đến (n + 1) nên theo quy tắc cộng ta có n +1 n −1 an = ∑ ar−2 an+1−r hay an = ∑ ak an−1−k với n ≥ 1. r =2 k =0 n −1Ta sẽ chứng minh an = ∑ ak an−1−k , bằng kỹ thuật hàm sinh. k =0 ∞ Đặt A( x ) = ∑ an xn là hàm sinh của dãy (an ) thì: n =0 ∞ ∞ ! n −1 A ( x ) − a0 = ∑ ak x n = ∑ ∑ a k a n −1− k xn n =1 n =1 k =0 = ( a0 a0 ) x + ( a0 a1 + a1 a0 + a1 a0 ) x 2 + ( a0 a1 + a1 a1 + a2 a0 ) x 3 + · · · = a0 + a1 x + a2 x 2 + a3 x 3 + · · · · a0 x + a1 x 2 + a2 x 3 + · · · = x ( A ( x ))2 . 2Do đó, vì a0 = 1 nên x ( A( x )) − A( x ) + 1 = 0. √ 1± 1 − 4x 1 h 1 ...