Xem mẫu
- 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
nguon tai.lieu . vn
