zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

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

Chia sẻ: Huyết Thiên Thần | Ngày: | Loại File: PDF | Số trang:9

Báo xấu

22
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ân kiế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éo củ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ác củ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 chia nà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ủa Pn+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 −1 Ta 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 . 2 Do đó, vì a0 = 1 nên x ( A( x )) − A( x ) + 1 = 0. √ 1± 1 − 4x 1 h 1 i ta nhận được nghiệm của phương trình là A( x ) = = 1 ± (1 − 4x ) 2 . 2x 2x 2
Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 1 Hệ số của x n (n 6= 1) trong khai triển (1 − 4x ) 2 là 1 1 1 1 −1 · −2 ··· −n+1 2 2 2 2 Cn1 (−4)n = (−4)n 2 n! n n 1 1 · 1 · 3 · 5 · · · (2n − 3) = (−4) (−1)n−1 2 n! ((2n − 2)! = − 2n n! · 2 · 4 · 6 · · · (2n − 2) 2 (2n − 2)! = · n ( n − 1) ! ( n − 1) ! 2 − · C2n(−n1−1) . n 1 h 1 i Vì an ≥ 1, nên từ A( x ) = 1 ± (1 − 4x ) 2 suy ra 2x ∞ 1 h i 1 2 n −1 ∑ 1 A( x ) = 1 − (1 − 4x ) 2 = C2 ( n − 1 ) x n . 2x 2x n =1 n 1 2 Do đó, với n ≥ 1 ta có an = · Cn = Cn . 2 n + 1 2n 1 Số Cn = Cn gọi là số Catalan thứ n. n + 1 2n Có rất nhiều bài toán tổ hợp có kết quả là số Catalan. Đây là kết quả do nhà toán học Eugène Catalan (1814 - 1894) phát hiện và mang tên ông. Sau đây là một số đẳng thức đẹp liên quan đến số Catalan. Bài toán 1.2. Cho số tự nhiên n 6= 1. Chứng minh rằng n n −1 1 C2n − C2n = Cn . n + 1 2n Lời giải. Ta có n − Cn −1 = (2n)! (2n)! C2n 2n − n! · n! (n − 1)! · (n + 1)! (2n)! [(n + 1) − n] 1 (2n)! = = · n! · (n + 1)! n + 1 n! · n! 1 = Cn . n + 1 2n Bài toán 1.3. Chứng minh rằng với mọi số nguyên không âm n, ta có n n Cn = 2C2n − C2n +1 . 3
Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Lời giải. Ta có n − Cn −1 = 2 · (2n)! (2n + 1)! C2n 2n − n! · n! n! · (n + 1)! 2 · (n + 1) · (2n)! (2n + 1)! = − n! · (n + 1)! n! · (n + 1)! (2n + 1)! + (2n)! (2n + 1)! = − n! · (n + 1)! n! · (n + 1)! (2n)! = n! · (n + 1)! 1 (2n)! = · = Cn . n + 1 n! · n! Bài toán 1.4. Chứng minh rằng với mọi số nguyên dương n, ta có n n Cn = 4C2n −1 − C2n+1 . Lời giải. Ta có n n 4(2n − 1)! (2n + 1)! 4C2n −1 − C2n+1 = − n! · (n − 1)! n! · (n + 1)! 4n(n + 1) · (2n − 1)! (2n + 1)! = − n! · (n + 1)! n! · (n + 1)! 1 2n · (2n + 2)(2n − 1)! − (2n + 1)! = · n+1 n! · n! 1 (2n + 2)(2n)! − (2n + 1)(2n)! = · n+1 n! · n! 1 (2n)! = · = Cn . n + 1 n! · n! Bài toán 1.5. Chứng minh rằng với mọi số nguyên dương n, ta có n +1 n +1 Cn = C2n +1 − 2C2n . Lời giải. Ta có n +1 n +1 (2n − 1)! 2(2n)! C2n +1 − 2C2n = − (n + 1)! · n! (n + 1)! · (n − 1)! (2n + 1)! 2(2n)! · n = − (n + 1)! · n! (n + 1)! · n! (2n + 1)! − 2(2n)! · n = (n + 1)! · n! (2n)! [(2n + 1) − 2n] = (n + 1)! · n! 1 (2n)! = · = Cn . n + 1 n! · n! 4
Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Bài toán 1.6. Chứng minh rằng với mọi số nguyên dương n ≥ 2, ta có 2 n −2 Cn+1 = 2Cn + · C2n . n Lời giải. Ta có 2 n −2 1 n −2 2 n −2 2Cn + · C2n =2 · C2n + · C2n n n+1 n 2 (2n)! 2 (2n)! = · + · n + 1 n! · n! n (n − 2)! · (n + 2)! 2 · (2n)! 2(n − 1) · (2n)! = + (n + 1)! · n! n! · n! 1 (2n)! · (2n + 4 + 2n − 2) = · n+2 n! · (n + 1)! 1 (2n)! · 2 · (2n + 1) = · n+2 n! · (n + 1)! 1 (2n)! · 2 · (n + 1)(2n + 1) = · n+2 ( n + 1) ! · ( n + 1) ! 1 (2n)!(2n + 2)(2n + 1) = · n+2 ( n + 1) ! · ( n + 1) ! 1 (2n + 2)! = · n + 2 ( n + 1) ! · ( n + 1) ! 1 n +1 = · C2n +2 = Cn +1 . n+2 Bài toán 1.7. Chứng minh rằng với mọi số nguyên dương n ≥ 1, ta có 2n−1 C2n = C2n 2n 4n − C4n − C4n . Lời giải. Ta có 2n−1 (4n)! C2n 4n − C4n = C2n 4n − (2n − 1)!(2n + 1)! 1 (2n) · (4n)! = C2n 4n − · 2n + 1 (2n)! · (2n)! 2n 2n 2n 2n 2n = C4n − · C4n = C4n 1 − 2n + 1 2n + 1 1 = · C2n 4n = C2n . 2n + 1 Bài toán 1.8. Chứng minh rằng với mọi số nguyên dương 1 ≤ k ≤ n, ta có n 2 ∑k Ckn = n · (2n − 1)! · Cn . k =1 5
Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Lời giải. Khai triển (1 + x )n = C0n + C1n x + C2n x2 + · · · + Cnn x n . Lấy đạo hàm hai vế ta được n(1 + x )n−1 = C1n + 2C2n x + · · · nCnn−1 Tương đương nx (1 + x )n−1 = C1n x + 2C2n x2 + · · · + nCnn x n . 1 n −1 1 n 1 2 n Thay x bởi ta có 1+ = C1n + 2 C2n + · · · + n Cnn . x x x x x x Đem quy đồng ta được n n(1 + x )n−1 = nCnn + (n − 1)Cnn−1 x + · · · + 2C2n x n−2 + C1n x n−1 = ∑ kCkn xk (1) k =1 n Mặt khác (1 + x )n = ∑ Ckn xk (2) k =0 Từ (1) và (2) nhân tương ứng các vế, ta có " # " # n n n(1 + x )2n−1 = ∑ kCkn xn−k · ∑ kCkn xk k =1 k =0 So sánh hệ số của xn ở hai vế ta có n 2 n(2n − 1)! n(2n − 1)(2n − 2)! ∑ Ckn = nC2n k n −1 = n!(n − 1)! = n ( n − 1) ! ( n − 1) ! k =1 1 (2n − 2)! = n(2n − 1) · · n ( n − 1) ! ( n − 1) ! = n(2n − 1)Cn−1 . Bài toán 1.9. Chứng minh rằng với mọi số nguyên dương 0 ≤ k ≤ n, ta có 1 n +1 h k i2 2 k∑ k −1 Cn = C n − C n . =0 Lời giải. 1 n +1 h k i2 2 k∑ k −1 Đặt f (n) = C n − C n =0 Ta có tính chất của tam giác PasCal như sau 2 2 2 Ckn+1 = Ckn−1 + Ckn ⇔ Ckn+1 = Ckn−1 + 2Cnk−1 Ckn + Ckn 2 2 2 Suy ra Ckn+1 − Ckn − Ckn−1 = 2Ckn−1 Ckn 6
Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Do đó n +1 h i2 n +1 2 2 f (n) = ∑ Ckn − Ckn−1 = ∑ Ckn − 2Ckn Ckn−1 + Ckn−1 k =0 k =0 n +1 2 n +1 2 n +1 2 = 2 ∑ Ckn +2 ∑ Ckn−1 − ∑ Ckn+1 k =0 k =0 k =0 n 2 n 2 n +1 2 = 2 ∑ Ckn + 2 ∑ Ckn − ∑ Ckn+1 k =0 k =0 k =0 n n n +1 = 2C2n + 2C2n − C2n +2 h i n n −1 n = 4C2n − 2 C2n + C2n n n −1 = C2n − 2C2n n n −1 = 2 C2n − C2n . n − Cn −1 = 1 n . Theo kết quả Bài toán 1, ta có C2n 2n C2n n + 1 n − Cn−1 = 2 1 Cn = 2C . Vậy ta có f (n) = 2 C2n n 2n n + 1 2n 1 1 n + 1 2 Do đó Cn = f (n) = ∑ Ckn − Cnk−1 . 2 2 k =0 Nhận xét 1.1. Trong lời giải Bài toán 8, ta đã sử dụng đẳng thức Lagrange: Đẳng thức Lagrange phát biểu như sau: Với mọi số nguyên dương 0 ≤ k ≤ n, ta có n 2 ∑ Ckn = C2n n (Đây là đẳng thức quen thuộc dễ chứng minh). k =0 Bài toán 1.10. Chứng minh rằng với mọi số nguyên dương 1 ≤ k ≤ n, ta có b n−2 1 c 2 n − 2k k ∑ n .Cn = Cn−1 k =0 Lời giải. b n−2 1 c h i2 n−2k k Đặt f (n) = ∑ n .Cn = Cn−1 . Ta dễ thấy k =0 2 1 n n − 2k 1 n 2 n n 2 k 2 2 k f (n) = ∑ k · Cn = ∑ Ckn − 2 ∑ Ckn · + 2 ∑ Ckn · 2 2 k =0 n 2 k =0 k =0 n k =0 n n n n 1 2 2 = ∑ Ckn − 2 ∑ Ckn .Cnk− − 1 + 2 ∑ Cn −1 1 k −1 2 k =0 k =0 k =0 n n − 1 n −1 1 2 2 = ∑ Ckn − 2 ∑ Ckn+1 · Ckn−1 + 2 ∑ Ckn−1 2 k =0 k =0 k =0 1 n n n −1 = C2n − 2 · C2n −1 + 2C2n−2 2 2n − 1 2(2n − 1) n −1 = C2n−2 − +2 n n 1 n −1 = C2n −2 = Cn −1 . n 7
Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Bài toán 1.11. Chứng minh rằng với mọi số nguyên dương 1 ≤ k ≤ n, ta có n (−1)k k 22n+1 ∑ 2k + 1 n (n + 1)(n + 2)Cn+1 . C = k =0 Lời giải. n Ta có khai triển (1 − x2 )n = ∑ (−1)k Ckn x2k . k =0 Z1 Z1 n Do đó (1 − x2 )n dx = ∑ (−1)k Ckn x2k dx. 0 0 k =0 π 2 n 1 Z Tương đương cos2n+1 tdt = ∑ (−1)k Ckn · 2k + 1 0 k =0 n 1 · 2 · 4 · 6 · · · (2n) (−1)k k Tương đương =∑ C . 1 · 3 · 5 · · · (2n + 1) k =0 2k + 1 n Viết lại thành n (−1)k k n!2n ∑ 2k + 1 nC = 1 · 3 · 5 · · · (2n + 1) k =0 n!2n [2 · 4 · 6 · · · (2n + 2)] (2n + 2)! 2 2n + 1 n!(n + 1)! = (2n + 2)! + 2 1 ( n + 1) ! ( n + 1) ! ( n + 2) 2n = (n + 1)(n + 2)(2n + 2)! 22n+1 = . (n + 1)(n + 2)Cn+1 1 (2n + 2)! Vì Cn+1 = · . n + 2 ( n + 1) ! ( n + 1) ! 2 Bài tập tương tự Một số đẳng thức sau đây bạn đọc có thể chứng minh trực tiếp, hoặc các kết quả của nó được tìm ra từ những bài toán đếm mà có. Việc chứng minh trực tiếp hay nghiên cứu, tìm tòi để tìm ra các đẳng thức này xin được dành cho bạn đọc. Bài 2.1. Với mọi số nguyên dương n ta có 1 n Cn = · C2n +1 . 2n + 1 1 n . Chứng minh rằng Bài 2.2. Cho số Catalan Cn = · C2n n+1 n−1 h i2 C2n−1 = ∑ n − k −1 C2n −1 − C n − k −2 2n−1 . k =0 8
Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 1 n . Chứng minh rằng Bài 2.3. Cho số Catalan Cn = · C2n n+1 n k2 ∑n n −1 C2n − k −1 = Cn +1 − Cn . k =1 1 n . Đẳng thức sau đề cập đến trong một bài báo Bài 2.4. Cho số Catalan Cn = · C2n n+1 của David Callan năm 2010: n 1 ∑ 2n − 2k + 1 C2n k n−k −2k+1 C2k = Cn . k =0 1 Bài 2.5. Cho số Catalan Cn = · Cn . Đẳng thức sau được Arthur Cayley và Krikman n + 1 2n tìm ra năm 1859: 1 · 3 · 5 · · · (2n − 3) n−1 Cn −1 = ·2 . 1·2·3···n Tài liệu [1] Nguyễn Văn Mậu, Chuyên đề chọn lọc tổ hợp và toán rời rạc, NXBGD 2010. [2] Ngô Thị Nhã, Nguyễn Văn Lợi, Các bài toán nổi tiếng về dãy Catalan, Tạp chí Toán học Tuổi trẻ. [3] Richard P. Stanley, Enumerative Combinatorics. 9

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.