ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
Nguyễn Thị Thúy
CÁC TÍNH CHẤT
CỦA ĐA THỨC NARAYANA
Chuyên ngành : Phương pháp toán sơ cấp
Mã số : 60 46 01 13
LUẬN VĂN THẠC SĨ TOÁN HỌC
Người hướng dẫn khoa học
TS. Nguyễn Tiến Dũng
Thái Nguyên - 2017
1
Mục lục
Mở đầu 2
1 Giới thiệu về đa thức Narayana
1.1 Định nghĩa và tính chất cơ bản . . . . . . . . . . . . . . 1.1.1 Một số khái niệm . . . . . . . . . . . . . . . . . 1.1.2 Một số tính chất cơ bản . . . . . . . . . . . . . . 1.2 Các ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . 4 4 4 6 7
2 Các đồng nhất thức của đa thức Narayana
2.1 Công thức biểu diễn tích phân . . . . . . . . . . . . . . 2.2 Các đồng nhất thức . . . . . . . . . . . . . . . . . . . . 10 10 12
3 Một dãy số nguyên có liên quan đến đa thức Narayana 17 17 18 3.1 Định nghĩa dãy An . . . . . . . . . . . . . . . . . . . . 3.2 Tính chất của dãy An . . . . . . . . . . . . . . . . . . .
Kết luận 27
Tài liệu tham khảo 28
2
Mở đầu
Đa thức Narayana được giới thiệu và nghiên cứu bởi MacMahon (1915) và nhà toán học Ấn độ Narayana (1955). Bởi vì tính ứng dụng được trong các lĩnh vực khác nhau (đặc biệt là các bài toán đếm của lý thuyết tổ hợp), đa thức Narayana vẫn là đối tượng được quan tâm nghiên cứu trong vòng 10 năm gần đây.
Mục đích của luận văn là trình bày lại một số tính chất mới của đa thức Narayana. Nội dung của luận văn được tổng hợp từ các kết quả chính của các bài báo [9], [6].
Ngoài phần mở đầu và kết luận, bố cục Luận văn có 03 chương chính. Chương 1. Giới thiệu về đa thức Narayana
1.1. Định nghĩa và tính chất cơ bản
1.2. Các ví dụ
Chương 2. Các đồng nhất thức của đa thức Narayana
2.1. Công thức biểu diễn tích phân
2.2. Các đồng nhất thức
Chương 3. Một dãy số nguyên có liên quan đến đa thức
Narayana
3.1. Định nghĩa dãy An
3.2. Tính chất của dãy An
Bản luận văn này được hoàn thành dưới sự hướng dẫn và chỉ bảo tận tình của TS. Nguyễn Tiến Dũng. Thầy đã dành nhiều thời gian hướng dẫn cũng như giải đáp các thắc mắc của tôi trong suốt quá trình làm luận văn. Tôi muốn bày tỏ lòng biết ơn sâu sắc đến người thầy của mình.
3
Tôi xin cảm ơn Trường THPT Thái Phiên - nơi tôi đang công tác, đã giúp đỡ tạo điều kiện rất nhiều cho tôi hoàn thành khoá học này. Tôi cũng xin cảm ơn nhóm seminar của Khoa Toán - Tin trường Đại học Khoa học Thái Nguyên đã giúp tôi bổ sung, củng cố các kiến thức về Lý thuyết số và Tổ hợp.
Qua đây, tôi xin gửi tới các thầy cô Khoa Toán - Tin, Trường Đại học Khoa học Thái Nguyên cũng như các thầy cô đã tham gia giảng dạy khóa cao học K9B2 2015-2017, lời cảm ơn sâu sắc nhất đối với công lao dạy dỗ trong suốt quá trình giáo dục đào tạo của nhà trường.
Tôi xin cảm ơn gia đình, bạn bè và tất cả mọi người đã quan tâm, tạo điều kiện, động viên cổ vũ tôi để tôi có thể hoàn thành nhiệm vụ của mình.
Thái Nguyên, ngày 05 tháng 9 năm 2017
Tác giả luận văn
Nguyễn Thị Thúy
4
Chương 1
Giới thiệu về đa thức Narayana
Chương này trình bày định nghĩa và các ví dụ minh họa cho tính ứng
1.1 Định nghĩa và tính chất cơ bản
dụng được của các đa thức Narayana.
1.1.1 Một số khái niệm
Dãy Catalan Trong toán tổ hợp, số Catalan là dãy các số tự nhiên xuất hiện nhiều trong các bài toán đếm, thường bao gồm những đối tượng đệ quy. Được đặt tên theo nhà toán học người Pháp và Bỉ Eugène Charles Catalan (1814-1894). Số Catalan được định nghĩa như sau :
(cid:32) (cid:33)
=
Cn =
2n n
1 n + 1
(2n)! (n + 1)!n!
(1.1) với n ≥ 0.
(cid:33) (cid:32)
2n n
Trong đó là tổ hợp chập n của 2n phần tử.
Các giá trị của Cn với 0 ≤ n ≤ 14 được cho bởi dãy số sau : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 14858, 742900, 2674440. Dãy số Narayana Định nghĩa : Dãy số Narayna, ký hiệu N (n, k), là dãy các số nguyên
5
được cho bởi công thức sau :
N (0, 0) = 1 và N (n, k) =
, với hai giá trị nguyên dương n, k.
n k − 1
n k
1 n
(cid:32) (cid:33) (cid:32) (cid:33)
(1.2) Các giá trị đầu với n từ 1 đến 7 của các số Narayana được cho bởi bảng sau :
Bảng 1.1
3 4 5 6 7 n \ k 1 2
1 15 1
1 2 3 4 5 6 7 1 1 1 1 1 3 1 6 1 6 10 1 10 20 1 15 50 50 1 21 105 175 105 21 1
n (cid:88)
Đa thức Narayana Định nghĩa : Đối với bất kỳ số nguyên n không âm, đa thức Narayana kí hiệu là Nn(q) được xác định bởi N0(q) = 1 và
N (n, k)qk,
n > 0
Nn(q) =
k=1
với (1.3)
Với N (n, k) là số Narayana cho bởi (1.2). Các giá trị đầu với n nhận giá trị từ 1 đến 7 của dãy đa thức Narayana được cho bởi bảng sau :
+ q4
n 1 q 2 q + q2 3 q + 3q2 + q3 4 q + 6q2 + 6q3 5 q + 10q2 + 20q3 + 10 q4 + q5 6 q + 15q2 + 50q3 + 50 q4 + 15 q5 +q6 7 q + 21q2 + 105q3 + 175 q4 + 105 q5 +21 q6 +q7
6
N 0(q) = N0(q) = 1
Định nghĩa : Với mọi n ≥ 0. Các đa thức Narayana liên hợp N n(q) của Nn(q) được xác định bởi
và với n > 0, ta có
N n(q) = qnNn(q−1) = Nn(q)/q.
(1.4)
1.1.2 Một số tính chất cơ bản
Tính chất 1.
Các số Narayana là đối xứng theo dòng, tức là N (n, k) = N (n, n−k+1). Chứng minh. (cid:32) (cid:33) (cid:32) (cid:33)
n n − k
n n − k + 1
1 n
Ta có N (n, n − k + 1) =
=
= N (n, k).
n n − k
n k
1 n Tính chất 2.
(cid:32) (cid:33) (cid:32) (cid:33)
Các số Narayana cũng có thể tính bởi công thức sau :
N (n, k) =
n k − 1
n − 1 k − 1
1 k
(cid:32) (cid:33) (cid:32) (cid:33)
Chứng minh. Ta có
=
n k − 1
n − 1 k − 1
n k − 1
1 k
1 k
(n − 1)! (k − 1)!(n − k)!
(cid:32) (cid:33) (cid:32) (cid:33) (cid:33) (cid:32)
=
n k − 1 (cid:32)
1 n (cid:33) (cid:32)
n! k!(n − k)! (cid:33)
=
n k − 1
n k
1 n
= N (n, k).
(cid:33) (cid:32)
7
n (cid:88)
N (n, k) = Cn.
Nn(1) =
k=1
Tính chất 3. Narayana thứ n của 1 bằng số Catalan thứ n
Tính chất 4.
Nn(−1) =
nếu n = 2r
nếu n = 2r + 1 (cid:40) 0 (−1)r+1Cr
Chứng minh của các tính chất 3, 4 và 5 có thể tìm thấy trong [2]. Tính chất 5. Đa thức Narayana được biểu diễn một cách khác như sau :
n (cid:88)
(q − 1)k.
Nn(q) =
n + 1 k
(cid:33) (cid:33) (cid:32) (cid:32)
1 n + 1 (cid:32)
2n − k n (cid:33)
n (cid:88)
=
(q − 1)n−k.
k=0 n + k n − k
2k k
1 k + 1
k=0
(cid:33) (cid:32)
qm(q + 1)n−2m−1
N n(q) =
Cm.
n − 1 2m
m≥0
Tính chất 6. Đa thức N n(q) được biểu diễn thông qua các số Catalan bằng công thức sau : (cid:33) (cid:32) (cid:88)
1.2 Các ví dụ
Công thức biểu diễn mới này đã được chứng minh trong [8].
Ví dụ 1.
Số Narayana N (n, k) đếm số biểu thức chứa n cặp dấu ngoặc đơn và có đúng k cụm phân biệt. Chẳng hạn, ta có : + Với n cặp dấu ngoặc đơn và 1 cụm phân biệt thì có N (n, 1) = 1 cách biểu diễn : (. . . ((a)) . . .) + Có 6 cặp dấu ngoặc đơn và 2 cụm phân biệt thì có N (4, 2) = 6 cách
8
biểu diễn : (a)(((b))) ((a))((b)) ((a)((b))) (((a)(b))) (((a))(b)) (((a)))(b) Ví dụ 2. Số Narayana N (n, k) đếm số quỹ đạo (cách đi) từ trái sang phải với k đỉnh từ điểm (0, 0) đến điểm (2n, 0). Ở đó các bước đi là các véc tơ có tọa độ (1; 1) hoặc (1; −1). Các quỹ đạo đi từ điểm (0; 0) đến điểm (8; 0). Để minh họa, ta có bảng sau cho các số N (4, k).
Ví dụ 3.
Số Narayana N (n, k) đếm số cách phân hoạch một tập có n phần tử thành k tập con, trong đó các phân hoạch là không giao nhau. Lược đồ sau minh họa cho trường hợp N (4, k). + Số phân hoạch 4 phần tử thành 1 tập con : N (4, 1) = 1.
9
+ Số phân hoạch 4 phần tử thành 2 tập con không giao nhau : N (4, 2) = 6. + Số phân hoạch 4 phần tử thành 3 tập con không giao nhau : N (4, 3) = 6. + Số phân hoạch 4 phần tử thành 4 tập con khác rỗng : N (4, 4) = 1.
10
Chương 2
Các đồng nhất thức của đa thức
Narayana
2.1 Công thức biểu diễn tích phân
Chương này trình bày kết quả chính của bài báo [9].
Đa thức Legendre
n (cid:88)
n (cid:88)
=
,
Pn(x) =
n + k n − k
2k k
n k
n + k k
2
k=0
k=0
2 (2.1)
Đa thức Legendre ký hiệu là Pn(x) [9] cho bởi công thức (cid:33) (cid:32) (cid:32) (cid:33) (cid:32) (cid:32) (cid:19)k (cid:19)k (cid:33) (cid:18)x − 1 (cid:33) (cid:18)x − 1
q
q−1(cid:90)
Nn(q) = (q − 1)n+1
Pn(2x − 1)dx
0 1 (cid:90)
x − 1)dx.
= q(q − 1)n
Pn(
2q q − 1
0
Định lí 2.1. Đối với bất kỳ số nguyên n ≥ 1, ta có biểu diễn sau
Ở đó Pn(x) là đa thức Legendre, được cho bởi công thức (2.1).
11
Chứng minh.
Ta có (2.1) tương đương với
n [ ] 2 (cid:88)
(−1)k
xn−2k,
Pn(x) = 2−n
n − k k
2n − 2k n − k
k=0
(cid:32) (cid:33) (cid:32) (cid:33)
n (cid:88)
(x − 1)k.
Pn(2x − 1) =
n + k n − k
2k k
k=0
do đó (cid:32) (cid:33) (cid:32) (cid:33)
1 (cid:90)
q(q − 1)n
x − 1)dx
Pn(
2q q − 1
0
q q − 1 (cid:90)
= (q − 1)n+1
Pn(2x − 1)dx
0
q
Rõ ràng là Nn(0) = 0 với mọi n ≥ 1. Ta có
q−1(cid:90)
n (cid:88)
= (q − 1)n+1
(x − 1)kdx
2k k
n + k n − k
0
(cid:33) (cid:33) (cid:32) (cid:32)
k=0 (cid:33)
n (cid:88)
=
(q − 1)n−k
n + k n − k
k=0
(cid:33) (cid:32) (cid:32)
2k k (cid:33)
1 k + 1 (cid:32)
n (cid:88)
(−1)k
+ (q − 1)n+1
n + k n − k
1 k + 1
k=0
2k k = Nn(q) − Nn(0)(1 − q)n+1 = Nn(q).
(cid:33) (cid:32)
Định lí đã được chứng minh.
12
2.2 Các đồng nhất thức
Định lí 2.2.1. Đối với bất kỳ số nguyên n ≥ 0, ta có các đồng nhất
n (cid:88)
thức sau (cid:32) (cid:33)
Cn =
Nk(q)(1 − q)n−k,
2n + 1 n − k
2k + 1 2n + 1
k=0
(2.2)
n
n (cid:88)
(cid:32) (cid:33)
(−1)n−k
2 +1C n
q
=
Nk+1(q)(1 + q)n−k,
2
n k
k=0
(2.3)
n (cid:88)
và (cid:32) (cid:33)
(−1)n−k
Nk+1(q2)(1 − q)2(n−k),
qn+2Cn+1 =
n k
k=0
(2.4)
= 0 nếu n lẻ.
2
trong đó C n
Chúng ta sử dụng ba hệ thức nghịch đảo sau để chứng minh Định lý
n (cid:88)
n (cid:88)
An =
Ak.
Bk ⇐⇒ Bn =
2n + 1 n − k
n + k n − k
(−1)n−k 2k + 1 2n + 1
k=0
k=0
(cid:32) (cid:33) 1.1. Hệ thức nghịch đảo Legendre trong [10] (cid:33) (cid:32)
(2.5)
Công thức nghịch đảo trái trong [3]
sn (cid:88)
[ n 2 ] (cid:88)
(cid:33) (cid:33) (cid:32) (cid:32)
(−1)sn−k
Ak,
An =
Bk =⇒ Bn =
sn + p k + p
n + p sk + p
k=0
k=0
(2.6)
n (cid:88)
n (cid:88)
trong đó, với trường hợp s = 1, p = 0 dẫn đến hệ thức nghịch đảo nhị thức (cid:32) (cid:33) (cid:32) (cid:33)
(−1)n−k
An =
Bk ⇐⇒ Bn =
Ak.
n k
n k
k=0
k=0
(2.7)
n (cid:88)
Ck(q − 1)−k,
n + k n − k
Nn(q) (q − 1)n =
k=0
Bây giờ ta sẽ bắt đầu trình bày cách chứng minh Định lý 2.2.1. Chứng minh (2.2). Từ tính chất 6, ta có (cid:33) (cid:32)
13
n (cid:88)
Cn =
Nk(q)(q − 1)n−k,
2n + 1 n − k
(cid:32) (cid:33)
k=0
và sử dụng (2.5), ta có biểu thức cho các số Catalan, (−1)n−k 2k + 1 2n + 1
từ đó hoàn thành chứng minh (2.2). Chứng minh (2.3). Từ kết quả trong [2] ta có
[ n−1 2 ] (cid:88)
qk−1 =
Ckqk(1 + q)n−2k−1.
n k − 1
n − 1 2k
n k
(cid:32) (cid:32) (cid:33) (cid:32) (cid:33) (cid:33)
k=0
(cid:88) 1 n
[ n 2 ] (cid:88)
Ckqk+1(1 + q)−2k,
n 2k
Nn+1(q) (1 + q)n =
k=0
Thay n bởi n + 1, ta nhận được (cid:32) (cid:33)
Sử dụng (2.6) trong trường hợp s = 2, p = 0, ta suy ra một biểu thức khác cho số Catalan,
2n (cid:88)
(−1)k
qn+1Cn =
Nk+1(q)(1 + q)2n−k.
2n k
k=0
(cid:32) (cid:33)
Ta xét tổng
2n+2 (cid:88)
2n+1 (cid:88)
(cid:32) (cid:33)
(−1)k
fn(q) =
fiqi =
Nk+1(q)(1 + q)2n+1−k.
2n + 1 k
i=1
k=0
(2.8)
Bổ đề 3.1. Với tất cả n ≥ 0, fn(q) = 0. Chứng minh. So sánh các hệ số của hai vế trong (2.8), ta có
m (cid:88)
2n+1 (cid:88)
(−1)k
Nk+1,j
fm =
2n + 1 − k m − j
2n + 1 k
j=0
k=0
(cid:33) (cid:33) (cid:32) (cid:32)
(cid:32) (cid:33)
2n + 1 − k m − j
là một đa thức của k có bậc m + j − 2, Chú ý rằng Nk+1,j
mà không vượt quá 2n khi1 ≤ m ≤ n + 1. Từ công thức cơ bản
n (cid:88)
(x − k)r =
(−1)k
n k
n!
(cid:32) (cid:33) (cid:40) 0 nếu 0 ≤ r < n,
k=0
nếu r = n,
14
ta có thể nhận thấy mỗi tổng bên trong fm bằng không với 1 ≤ m ≤ n + 1. Lưu ý rằng fn(q) = q2n+3fn(q−1) bởi vì qn+1Nn(q−1) = Nn(q). Như vậy fm = 0 với n + 2 ≤ m ≤ 2n + 2. Do đó, fn(q) = 0 với n ≥ 0. Bằng cách kết hợp (2.8) với Bổ đề 3.1, ta có (2.3). Chứng minh (2.4). Từ kết quả trong [2] ta có
n (cid:88)
n−1 (cid:88)
q2k−2(1 + q)2n−2k =
Ck+1qk(1 + q)k.
n k − 1
n k
n − 1 k
1 n
k=1
k=0
(cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33)
Thay n bằng n + 1 ta nhận được
n (cid:88)
(1 + q)2n+2 =
Ck+1qk+2(1 + q)k,
Nn+1
n k
(1 + q)2
k=0
(cid:32) (cid:33) (cid:19) (cid:18) q2
và sử dụng (2.5), ta suy ra rằng
n (cid:88)
(−1)n−k
(1 + q)2k+2.
qn+2(1 + q)nCn+1 =
Nk+1
n k
(1 + q)2
k=0
(cid:32) (cid:33) (cid:19) (cid:18) q2
q q − 1
, sau khi rút gọn, ta có (2.4). Thay q bằng
[
]
Hệ quả. Từ Định lí 2.1.1 có thể tạo ra các đồng nhất thức đã biết hoặc mới. Ví dụ : • Chọn q = −1 trong (2.2) và sử dụng tính chất 5 ta nhận được một đồng nhất thức mới
n − 1 2 (cid:88)
(2n − 1)Cn =
2n−2r−1Cr.
2n + 1 n − 2r − 1
(−1)r 4r + 3 2n + 1
r=0
(cid:32) (cid:33)
Như vậy C2k ≡ 0mod 2 và C2k−1 ≡ Ck−1mod 2 với k ≥ 1. Và do đó, ta có thể dễ dàng nhận ra rằng Cn là lẻ khi và chỉ khi n = 2k − 1 với một số k ≥ 0. • Thay q bởi qn ở cả hai vế của (2.2), chúng ta có được đồng nhất thức
15
n (cid:88)
= 0,
(n ≥ 1).
2n + 1 n − k
(−1)k 2k + 1 2n + 1
k=0
sau : (cid:32) (cid:33)
Đồng nhất thức này đã được chứng minh bởi Chen, Li và Shapiro trong [1]. • Chọn q = 1 trong (2.3) dẫn đến một đồng nhất thức mới
2n (cid:88)
(−1)k
Cn =
Ck+122n−k.
2n k
k=0
• Chọn q = −1 trong (2.4) dẫn đến một đồng nhất thức đã biết [2]
(cid:32) (cid:33)
n (cid:88)
(−1)k
Cn+1 =
Ck+14n−k.
n k
k=0
• Chọn q = (cid:112)(−1) trong (2.4) dẫn đến đồng nhất thức Touchard [2] (cid:32)
(cid:32) (cid:33)
n (cid:88)
Cn+1 =
Ck2n−2k.
n 2k
k=0
√
√
√
2 trong (2.4). Bởi vì (1 −
2)n = (Pn + Pn−1) − Pn
2, • Cho q = trong đó Pn là số Pell thứ n (được xác định bởi các hệ thức truy hồi Pn+1 = 2Pn + Pn−1 với P−1 = 1, P0 = 0), chúng ta có đồng nhất thức mới liên quan đến số Catalan, số Narayana, và số Pell :
(cid:33)
2n (cid:88)
(−1)k
2n+1C2n+1 =
Nk+1(2)P4n−2k−1
2n k
k=0
(cid:32) (cid:33)
2n+1 (cid:88)
(−1)k
2n+1C2n+2 =
Nk+1(2)P4n−2k+2
2n + 1 k
k=0
√
√
(cid:32) (cid:33)
√
5
5
Ln − Fn
(cid:33)n+1 (cid:32)
• Cho q =
=
5 trong (2.4), theo các hệ thức
2
1 − 2
,
với Ln và Fn lần lượt là số Lucas thứ n và số Fibonacci thứ n (được xác định bởi cùng một hệ thức truy hồi Gn+1 = Gn + Gn−1 với G−1 =
16
2, G0 = 1 cho Ln và G−1 = 0, G0 = 1 cho Fn), ta có đồng nhất thức mới gồm số Catalan, số Lucas, và số Fibonacci
2n (cid:88)
(−1)k
Nk+1(5)L4n−2k−124n−2k−1,
5n+1C2n+1 =
2n k
k=0
(cid:32) (cid:33)
2n+1 (cid:88)
(−1)k
Nk+1(5)F4n−2k−124n−2k−1.
5n+1C2n+2 =
2n + 1 k
k=0
(cid:32) (cid:33)
17
Chương 3
Một dãy số nguyên có liên quan
đến đa thức Narayana
3.1 Định nghĩa dãy An
Chương này trình bày kết quả chính của bài báo [6].
(−z)m
(z + 1)N n(z) − N n+1(z) =
Am(n)N n−2m+1(z).
n − 1 2m − 1
m≥1
Ta biết rằng, đa thức (z + 1)N n(z) − N n+1(z) = (1 − z)zn−1 + . . . có thể biểu diễn một cách duy nhất theo các đa thức zmN n−2m+1(z), bậc n − 1. Do đó ta có thể định nghĩa dãy số thực Am(n) bởi (cid:33) (cid:32) (cid:88)
−
zk(z + 1)n−2k
Ck.
n − 1 2k − 1
k≥0
Từ Tính chất 3 trong Chương 1, vế trái của biểu thức trên có thể viết lại như sau : (cid:32) (cid:33) (cid:88)
Tương tự, vế phải trở thành
(−1)mzm+n(z + 1)n−2m−2r
Am(n)Cr
n − 1 2m − 1
n − 2m 2r
m≥1,r≥0
(cid:32) (cid:33) (cid:32) (cid:33) (cid:88)
18
So sánh các hệ số của zk(z + 1)n−2k ta nhận được
(−1)m
=
−Ck
Am(n)Cr,
n − 1 2m − 1
n − 2m 2r
n − 1 2k − 1
m+r=k
(cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33) (cid:88)
r (cid:88)
Cr =
Aj(n)Cr−j
2r − 1 2j − 1
j=1
và do đó (cid:33) (cid:32)
Như vậy dãy Am(n) không phụ thuộc vào n và ta viết Am thay cho Am(n). Ta có định nghĩa sau : Định nghĩa : Dãy số An là một dãy các số nguyên được tính theo công thức truy hồi sau A1 = 1 và
n−1 (cid:88)
(−1)j
(−1)n−1An = Cn +
AjCn−j, n ≥ 2.
2n − 1 2j − 1
j=1
(cid:32) (cid:33)
3.2 Tính chất của dãy An
Các giá trị của An với 1 ≤ n ≤ 14 là 1, 1, 5, 56, 1092, 32670, 1387815, 79389310, 5882844968, 548129834616, 62720089624920, 8646340208462880, 1413380381699497200, 270316008395632253340.
Định lí 3.2.1. Các số nguyên {An, n ≥ 2} là dương và tăng.
Để chứng minh Định lí 3.2.1, chúng ta cần các bổ đề sau : Bổ đề 3.1. Xét hai đa thức
zn =
zn
C(z) =
Cn (2n)!
1 n!(n + 1)!
n≥0
n≥0
(cid:88) (cid:88)
A(z) =
(−1)m−1
zm−1.
Am (2m − 1)!
m≥1
và (cid:88)
A(z)C(z) = 2
C(z).
d dz
Ta có
19
(x + i − 1) và xét đa
k (cid:81) i=1
Cho x là một số thực dương, ta kí hiệu (x)k =
H(z) =
zn.
1 n!(x)n
n≥0
thức (cid:88)
H (cid:48)(z) H(z)
cũng là một đa thức. Tính Từ trang 23 trong [7], ta biết rằng
chất của đa thức này được cho trong bổ đề sau,
H (cid:48)(z) H(z)
Bổ đề 3.2. Xét đa thức P (z) = . Ta có các hệ số của P (−z) đều
H(z) =
= 0F1(x + 1; z).
zn n!
1 (x)nn!
n≥0
dương. Chứng minh. Ta có (cid:88)
d dz 0F1(x; z) =
1 x 0F1(x + 1; z).
Ở đó oF1(x; z) được gọi là hàm giới hạn siêu bội suy biến. Bởi các tính toán đơn giản ta có
.
P (z) = 0F1(x + 1; z) x 0F1(x; z)
Như vậy
1
=
z
0F1(x + 1; z) x0F1(x; z)
x +
z
(x + 1) +
(x + 2) +
z (x + 3) + . . .
Các phân số liên tục của Gauss cổ điển [14, tr. 347] dẫn đến biểu thức sau đây cho vế phải
(−z)k2
(1 + f1z)−k1 =
f k2 1
k1 + k2 − 1 k2
k2≥0
Liên phân này có thể được viết như một chuỗi Taylor bằng cách lặp lại các công thức nhị thức thông thường (cid:32) (cid:33) (cid:88)
20
1 có dạng (c1(1 + (f2z)))−k2. Như vậy ta nhận được
ở đó f k2
P (z) =
1 x
−z (x + i − 1)(x + i)
ki + ki+1 − 1 ki+1
i≥1
(k1,k2,k3,...)
(cid:33) (cid:18) (cid:19)ki (cid:32) (cid:88) (cid:89)
trong đó các ki là các số nguyên không âm. Điều này đã làm sáng tỏ bổ đề.
Trong công thức trước, các số hạng với ki = 0 và ki + 1 > 0 là nhất
thiết phải là không. Do đó đối với n ≥ 2, ta có
pn =
(−1)n−1 x
1 (x + i − 1)(x + i)
ki + ki+1 − 1 ki+1
i≥1
κ∈Cn
(cid:33) (cid:18) (cid:19)ki (cid:32) (cid:88) (cid:89)
+
, p2 =
, p3 =
p1 =
1 x
−1 x2(x + 1)
1 x2(x + 1)2(x + 2)
1 x3(x + 1)2
với Cn là tập các dãy κ = (k1, k2, . . . , kl) của l ≤ n − 1 các số nguyên dương có tổng số đến n − 1. Có 2n−2 dãy như vậy, chẳng hạn :
Cn+1 = ∪κ∈Cn{κ1, κ2}
Với mỗi κ = (k1, k2, . . . , kl) ∈ Cn hãy kết hợp hai yếu tố Cn+1 được xác định bởi κ1 = (k1, k2, . . . , kl+1) và κ2 = (k1, k2, . . . , kl, 1). Chúng ta có
(i = 1, 2),
−(x + n − 1)(x + n)gκi ≥ gk,
Biểu thị gk, gκ1, gκ2 tương ứng với (5) của κ, κ1, κ2, ta dễ dàng có
−(x + n − 1)(x + n)pn+1 ≥ 2pn.
đẳng thức xảy ra cho κ = (1, 1, ..., 1) và i = 2. Tổng hợp tất cả các đóng góp cho (5), ta được
An = (−1)n−12(2n − 1)!pn|x=2, Chọn x = 2, phía trên ước tính cho ra An+1 > An, hoàn thành các chứng minh của Định lý 3.2.1. Bổ đề 3.3. Cho P (z) là các đa thức đã định nghĩa trong Bổ đề 3.2. Khi x > 0, ta có
zP (z)2 + z
P (z) + xP (z) = 1
d dz
Từ (4) suy ra
21
n (cid:88)
(n + x)pn+1 = −
prpn−r+1
r=1
Một cách tương đương, với bất kì số nguyên n ≥ 1, ta có
,
P (z) = 0F1(x + 1; z) x0F1(x; z)
Chứng minh. Từ mối liên hệ
P (z)2 +
d dz
ta có
P (z) (cid:18)
1
.
=
0F1(x + 1; z)2 +
x x + 1 0F1(x; z) 0F1(x + 2; z) − 0F1(x + 1; z)2
x2
0F1(x; z)2
(cid:19)
zP (z)2 + z
P (z) + xP (z) =
.
d dz
z x(x + 1)
0F1(x + 2; z) 0F1(x; z)
+ 0F1(x + 1; z) 0F1(x; z)
Do đó
z
0F1(x; z) − 0F1(x + 1; z) =
x(x + 1) 0F1(x + 2; z)
Ta có
bởi vì
−
=
.
zk k!
z x(x + 1)
zk−1 (k − 1)!
(cid:19)
1 (x + 1)k
1 (x + 2)k−1
(cid:18) 1 (x)k
Chọn x = 2 trong Bổ đề 3.3 ta nhận được định lí sau.
Định lí 3.2.2. Các số nguyên {An, n ≥ 2} dương, tăng và được cho
bởi công thức
n (cid:88)
An+1 =
ArAn−r+1.
2n + 1 2r − 1
n − r + 1 n + 2
r=1
, n ≥ 2} là dương, tăng và được cho bởi
(cid:32) (cid:33)
2An Cn
Các số {an =
n (cid:88)
an+1 =
aran−r+1.
n + 1 r + 1
n + 1 r − 1
1 2
1 n + 1
r=1
(cid:32) (cid:33) (cid:32) (cid:33)
22
cn,r =
n + 1 r + 1
n + 1 r − 1
2 n + 1
Từ công thức biểu diễn của an+1 trong Định lí 3.3.3, ta xét dãy số (cid:32) (cid:33) (cid:32) (cid:33)
−
.
cn,r =
n r − 1
n r
n r − 2
n r + 1
Dãy số này là các số nguyên dương bởi vì (cid:32) (cid:33) (cid:32) (cid:32) (cid:33) (cid:33) (cid:32) (cid:33)
Ta cần một số kết quả số học về cn,r. Cho một số r hữu tỉ, có tồn tại số nguyên a, b, m duy nhất với a và b lẻ với r = 2ma/b. Số nguyên m được coi là giá trị 2 − adic của r và ký hiệu v2(r). Một định lý cổ điển của Kummer (xuất hiện năm 1852, xem [13] cho cách chứng minh quy nạp) (cid:32) (cid:33)
a + b a
là một số nguyên cho rằng việc xác định giá trị 2 − adic của
không âm. Bổ đề 3.4.
(i) Nếu n chẵn, cn,r chẵn. (ii) Nếu n lẻ và r chẵn, cn,r là một bội số của 4. Chứng minh. (i) Vì n + 1 lẻ, ta có
≥ 1
ν2(cn,r) = 1 + ν2
+ ν2
n + 1 r + 1
n + 1 r − 1
(cid:32)(cid:32) (cid:33)(cid:33) (cid:32)(cid:32) (cid:33)(cid:33)
(ii) Bởi vì r + 1 lẻ, ta có
ν2(cn,r) = 1 + ν2
+ ν2
n r
n + 1 r − 1
(cid:32)(cid:32) (cid:33)(cid:33) (cid:32)(cid:32) (cid:33)(cid:33)
Vì r − 1 và n − r + 2 lẻ, ít nhất một số “mang” phải cần để thêm chúng tại gốc 2. Như vậy
≥ 1.
ν2
n + 1 r − 1
(cid:32) (cid:33)
23
c2p−1,p =
2p p + 1
1 p
Ta cũng xét (cid:32) (cid:33)2
4.
Bổ đề 3.5. (i) Nếu p chẵn, c2p−1,p là một bội số của 8. (ii) Nếu p lẻ và p (cid:54)= 2k − 1 cho bất kì k ≥ 1, c2p−1,p là một bội số của
(iii) Nếu p = 2k − 1 cho một số k ≥ 1, c2p−1,p lẻ.
Chứng minh.
c2p−1,p =
2p − 1 p
4p (p + 1)2
(i) Ta có (cid:32) (cid:33)2
Bởi vì p + 1 lẻ, ta có
≥ 3
ν2(c2p−1,p) = 3 + 2ν2
2p − 1 p
(cid:32)(cid:32) (cid:33)(cid:33)
(ii) Vì p lẻ, ta có
ν2(c2p−1,p) = 2ν2
2p p + 1
(cid:33)(cid:33) (cid:32)(cid:32)
p + 1 = ck+mck+m−1 . . . ck+210 . . . 00,
p − 1 = ck+mck+m−1 . . . ck+201 . . . 10.
Ta có thể viết các phép biểu diễn nhị phân của p + 1 và p − 1
Ít nhất một số "mang" là cần thiết để thêm chúng, trừ khi ck+m = ck+m−1 = . . . = ck+2 = 0, tức là p + 1 = 2k được loại trừ. Vì thế
≥ 1.
ν2
2p p + 1
(cid:33)(cid:33) (cid:32)(cid:32)
24
(iii) Khi p + 1 = 2k, các phép biểu diễn nhị phân của p + 1 và p − 1
= 0.
ν2
2p p + 1
là 10 . . . 00 và 01 . . . 10. Vì thế (cid:32)(cid:32) (cid:33)(cid:33)
Ta có định lí sau.
yj =
AjCn−j
2n − 1 2j − 1
Định lí 3.2.3. Các số {An, n ≥ 3} và {Cn, n ≥ 3} có cùng tính chẵn lẻ. Chúng là lẻ nếu và chỉ nếu n = 2k − 1 với k ≥ 2. Chứng minh. Ta tiến hành quy nạp trên n, với k = 2, C3 = 5 Giả sử ta có Cn là lẻ với n = 22k−1−1, ta chứng minh đúng với n = 2k−1 Ta biết từ [5] rằng những số Catalan {Cn, n ≥ 3} là lẻ nếu và chỉ nếu n = 2k − 1 cho một số k ≥ 2. Vì vậy ta chỉ cần chứng minh An và Cn cùng tính chẵn lẻ. Ta tiến hành quy nạp trên n. Ta sử dụng định nghĩa của An để biểu diễn (−1)nAn + Cn, như một tổng có dấu của các số hạng (cid:32) (cid:33)
với 1 ≤ j ≤ n − 1. Xét 2 trường hợp : Trường hợp 1. n = 2m cho một số m. Hiển nhiên y1 và yn−1 là lẻ. Mặt khác, tất cả {yj, 2 ≤ j ≤ n − 2} chẵn bởi vì các điều kiện n = 2m, j = 2k − 1 và n − j = 2l − 1 không thể cùng thỏa mãn nếu j (cid:54)= 1 hoặc n − j (cid:54)= 1. Trường hợp 2. n (cid:54)= 2m cho bất kỳ m. Tất cả {yj, 1 ≤ j ≤ n − 1} là chẵn. Thật vậy, nếu Aj và Cn−j lẻ, ta có j = 2k − 1 và n − j = 2l − 1 (cid:32) (cid:33)
2n − 1 2j − 1
chẵn với k, l ≥ 2, vì j và n − j không thể bằng 1. Nhưng vì
=
2n − 1 2j − 1
a + b a
do (cid:32) (cid:33) (cid:32) (cid:33)
với a = 2k+1 − 3 và b = 2l+1 − 2. Mặt khác, các phép biểu diễn nhị phân của a và b là 1 . . . 1101 (k + 1 chữ số) và 1 . . . 1110 (l + 1 chữ số). Với
25
các giá trị k, l ≥ 2, ít nhất một số "mang" là cần thiết để thêm chúng. Tổng hợp tất cả các điều kiện, An và Cn có cùng tính chẵn lẻ.
Định lí 3.2.4. Các số {an, n ≥ 2} là các số nguyên dương và tăng.
p (cid:88)
Chúng lẻ khi và chỉ khi n = 2k − 2 với một số số k ≥ 2. Giá trị của an trong 1 ≤ n ≤ 16 được cho bởi dãy số sau 2, 1, 2, 8, 52, 495, 6470, 111034, 2419928, 65269092, 2133844440, 831330904803805035352536, 202147745618247, 12336516593999598, 857054350280418290. Chứng minh. Ta dùng phương pháp quy nạp theo n. Giả sử rằng cho mọi m ≤ n, am là một số nguyên và am là lẻ nếu và chỉ nếu m = 2k − 2 với k ≥ 2 nào đó. Nếu n là chẵn, ta viết n = 2p. Từ Định lí 3.3.3 và Bổ đề 3.4 (i), ta có an+1 = a2p+1 là một số nguyên. Hơn nữa, an+1 là chẵn bởi vì ar hoặc an−r+1 là chẵn cho mỗi r. Nếu n là lẻ, ta viết n = 2p + 1. Từ Định lí 3.3.3 ta có
a2p+2 =
c2p+1,p+1a2
c2p+1,rara2p−r+2 +
p+1.
1 4
1 2
r=1
(3.1)
wp =
c2p+1,p+1a2
p+1.
1 4
Từ Bổ đề 3.4 (ii), ta có mỗi số hạng c2p+1,r hoặc ara2p−r+2 là số chẵn. Do đó, ta chỉ cần xét số hạng
Hiển nhiên wp là số nguyên khi ap+1 là số chẵn. Nếu ap+1 là số lẻ, bởi giả thiết quy nạp ta có : p + 1 = 2k − 2 với k ≥ 2 nào đó. Từ Bổ đề 3.5 (i) ta có wp và do đó a2p+2 là một số nguyên. Ta còn phải chứng minh rằng a2p+2 là lẻ nếu và chỉ nếu 2p + 2 = 2k − 2 hay p + 1 = 2k−1 − 1 với k ≥ 2 nào đó. Nếu p + 1 là chẵn, bởi Bổ đề 3.5 (i) ta có wp và do đó a2p+2 là chẵn. Nếu p + 1 là lẻ và p + 1 (cid:54)= 2k − 1 với mọi k thì theo Bổ đề 3.5 (ii), suy ra wp là chẵn. Như vậy khả năng duy nhất cho wp là lẻ xảy ra khi p + 1 = 2k − 1 với k nào đó.
26
a2 p+1 =
1 4
(cid:19)2 là lẻ. Từ Định lí 3.2.4, Ap+1 và Cp+1 là lẻ. Do đó (cid:18)Ap+1 Cp+1
Áp dụng Bổ đề 3.5 (iii) ta kết luận wp là lẻ. Định lí đã được chứng minh xong.
27
Kết luận
Luận văn trình bày một số tính chất mới của các đa thức Narayana. Nội dung của luận văn được tổng hợp từ hai bài báo [2] và [3] đã xuất bản trong những năm gần đây. Cụ thể hơn, trong luận văn này, chúng tôi
(1) trình bày định nghĩa và tổng hợp các ví dụ minh họa cho tính ứng
dụng của đa thức Narayana.
(2) trình bày công thức biểu diễn tích phân của đa thức Narayana và
các đồng nhất thức.
(3) trình bày tính chất của một dãy số có liên quan mật thiết đến đa
thức Narayana.
Nội dung của luận văn có thể sử dụng như một tài liệu tham khảo cho các lớp học sinh giỏi.
28
Tài liệu tham khảo
[1] Chen W. Y. C., Li N. Y. and Shapiro L. (2007), “The butter- fly decomposition of plane trees”, Disc. Appl. Math. 155(17), pp. 2187–2201.
[2] Coker C. (2003), “Enumerating a class of lattice paths”, Disc. Math.
271, pp. 13–28.
[3] Corsani C., Merlini D. and Sprugnoli R. (1998), “Left-inversion of
combinatorial sums”, Disc. Math. 180 :1-3, pp. 107-122.
[4] Gallian J. A., Joseph A. (1990), Contemporary Abstract Algera,
Sixth edition. D. C. Heath and Company.
[5] Koshy T., Salmassi M. (2006), “Parity and primality of Catalan
numbers”, Coll. Math. J. 37, pp. 52-53.
[6] Lassale M. (2012), “Two integer sequences related to Catalan num-
bers”, J. Combin. Theory Ser. A 119(4), pp. 923-935.
[7] Macdonald I. G. (1995), Symmetric functions and Hall Polynomial.
Clarendon Press, second edition, Oxford.
[8] Mansour T., Sun Y. (2008), “Dyck paths and partial Bell polyno-
mials”, Australas. J. Combin. 42, pp. 285-297.
[9] Mansour T., Sun Y. (2009), “Identities involving Narayana polyno- mials and Catalan numbers”, Discrete Math. 309(12), pp. 4079-4088.
[10] Riordan J. (1968), Combinatorial Identities, New York : John Wiley
Sons, Inc.
[11] Roger R. (1907), “On the representation of certain series as conti-
nued fraction”, Proc. London. Math. Soc. 4, pp. 72-89.
29
[12] Sulanke R. A. (2002), “The Narayana distribution”, J. Stat. Plan.
Inf. 101, pp. 311-326.
[13] B. Sury (2009), “Generalized Catalan numbers : linear recursion and
divisibility”, J. Integer Seq. 12, Article 09.7.5.
[14] Wall H. S. (1948), Analytic Theory of Continued Fractions. D.Van
Nostrand Company,New Yord.
