Luận văn Thạc sĩ Toán học: Các tính chất của đa thức Narayana

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:30

Thêm vào BST

Báo xấu

15
lượt xem 2
download

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

Đ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.

Chủ đề:

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

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Các tính chất của đa thức Narayana

ĐẠ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 4 1.1 Định nghĩa và tính chất cơ bản . . . . . . . . . . . . . . 4 1.1.1 Một số khái niệm . . . . . . . . . . . . . . . . . 4 1.1.2 Một số tính chất cơ bản . . . . . . . . . . . . . . 6 1.2 Các ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 Các đồng nhất thức của đa thức Narayana 10 2.1 Công thức biểu diễn tích phân . . . . . . . . . . . . . . 10 2.2 Các đồng nhất thức . . . . . . . . . . . . . . . . . . . . 12 3 Một dãy số nguyên có liên quan đến đa thức Narayana 17 3.1 Định nghĩa dãy An . . . . . . . . . . . . . . . . . . . . 17 3.2 Tính chất của dãy An . . . . . . . . . . . . . . . . . . . 18 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 dụng được của các đ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 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 : ! 1 2n (2n)! Cn = = với n ≥ 0. (1.1) n+1 n (n + 1)!n! ! 2n Trong đó là tổ hợp chập n của 2n phần tử. n 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 : !! 1 n n N (0, 0) = 1 và N (n, k) = , với hai giá trị nguyên dương n, k. n k−1 k (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 n\k 1 2 3 4 5 6 7 1 1 2 1 1 3 1 3 1 4 1 6 6 1 5 1 10 20 10 1 6 1 15 50 50 15 1 7 1 21 105 175 105 21 1 Đ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 X Nn (q) = N (n, k)q k , với n>0 (1.3) k=1 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 : n 1 q 2 q + q2 3 q + 3q 2 + q3 4 q + 6q 2 + 6q 3 + q4 5 q + 10q 2 + 20q 3 + 10 q 4 + q 5 6 q + 15q 2 + 50q 3 + 50 q 4 + 15 q 5 +q 6 7 q + 21q 2 + 105q 3 + 175 q 4 + 105 q 5 +21 q 6 +q 7
6 Đị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 N 0 (q) = N0 (q) = 1 và với n > 0, ta có N n (q) = q n Nn (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. ! ! 1 n n Ta có N (n, n − k + 1) = n n−k n−k+1 ! ! 1 n n = = N (n, k). n n−k k Tính chất 2. Các số Narayana cũng có thể tính bởi công thức sau : ! ! 1 n n−1 N (n, k) = k k−1 k−1 Chứng minh. Ta có ! ! ! 1 n n−1 n 1 (n − 1)! = k k−1 k−1 k−1 k (k − 1)!(n − k)! ! n 1 n! = k−1 n k!(n − k)! ! ! 1 n n = n k−1 k = N (n, k).
7 Tính chất 3. Narayana thứ n của 1 bằng số Catalan thứ n n X Nn (1) = N (n, k) = Cn . k=1 Tính chất 4. ( 0 nếu n = 2r Nn (−1) = (−1)r+1 Cr nếu n = 2r + 1 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 ! ! 1 X n+1 2n − k Nn (q) = (q − 1)k . n + 1 k=0 k n n ! ! X n+k 1 2k = (q − 1)n−k . n−k k+1 k k=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 : ! X n−1 N n (q) = q m (q + 1)n−2m−1 Cm . m≥0 2m Công thức biểu diễn mới này đã được chứng minh trong [8]. 1.2 Các ví dụ 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 Chương này trình bày kết quả chính của bài báo [9]. 2.1 Công thức biểu diễn tích phân Đa thức Legendre Đa thức Legendre ký hiệu là Pn (x) [9] cho bởi công thức n ! ! k X n ! ! − x−1 k X n n+k x 1 n+k 2k Pn (x) = = , k k 2 n−k k 2 k=0 k=0 (2.1) Định lí 2.1. Đối với bất kỳ số nguyên n ≥ 1, ta có biểu diễn sau q Zq−1 Nn (q) = (q − 1)n+1 Pn (2x − 1)dx 0 1 2q Z = q(q − 1)n Pn ( x − 1)dx. q−1 0 Ở đó 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 ! ! X n−k 2n − 2k Pn (x) = 2−n (−1)k xn−2k , k n−k k=0 do đó ! ! n X n+k 2k Pn (2x − 1) = (x − 1)k . n−k k k=0 Rõ ràng là Nn (0) = 0 với mọi n ≥ 1. Ta có Z1 2q q(q − 1)n Pn ( x − 1)dx q−1 0 q qZ− 1 = (q − 1)n+1 Pn (2x − 1)dx 0 q n ! ! Zq−1 X n+k 2k = (q − 1)n+1 (x − 1)k dx n−k k k=0 0 n ! ! X n+k 2k 1 = (q − 1)n−k n−k k k+1 k=0 n ! ! X n + k 1 2k + (q − 1)n+1 (−1)k n−k k+1 k k=0 = Nn (q) − Nn (0)(1 − q)n+1 = Nn (q). Đị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 thức sau ! n X 2k + 1 2n + 1 Cn = Nk (q)(1 − q)n−k , (2.2) 2n + 1 n−k k=0 n ! n X n q 2 +1 C n2 = (−1)n−k Nk+1 (q)(1 + q)n−k , (2.3) k k=0 và ! n X n q n+2 Cn+1 = (−1)n−k Nk+1 (q 2 )(1 − q)2(n−k) , (2.4) k k=0 trong đó C n2 = 0 nếu n lẻ. Chúng ta sử dụng ba hệ thức nghịch đảo sau để chứng minh Định lý 1.1. Hệ thức nghịch đảo Legendre trong [10] n ! n ! X n+k X 2k + 1 2n + 1 An = Bk ⇐⇒ Bn = (−1)n−k Ak . n−k 2n + 1 n−k k=0 k=0 (2.5) Công thức nghịch đảo trái trong [3] [ n2 ] ! sn ! X n+p X sn + p An = Bk =⇒ Bn = (−1)sn−k Ak , (2.6) sk + p k+p k=0 k=0 trong đó, với trường hợp s = 1, p = 0 dẫn đến hệ thức nghịch đảo nhị thức ! ! n n X n X n An = Bk ⇐⇒ Bn = (−1)n−k Ak . (2.7) k k k=0 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ó n ! Nn (q) X n+k n = Ck (q − 1)−k , (q − 1) n−k k=0
13 và sử dụng (2.5), ta có biểu thức cho các số Catalan, n ! X 2k + 1 2n + 1 Cn = (−1)n−k Nk (q)(q − 1)n−k , k=0 2n + 1 n − k 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 ] ! X1 n n k−1 X n−1 q = Ck q k (1 + q)n−2k−1 . n k−1 k 2k k=0 Thay n bởi n + 1, ta nhận được n [2] ! Nn+1 (q) X n = Ck q k+1 (1 + q)−2k , (1 + q)n k=0 2k 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 ! X 2n q n+1 Cn = (−1)k Nk+1 (q)(1 + q)2n−k . k k=0 Ta xét tổng 2n+2 2n+1 ! X X 2n + 1 fn (q) = fi q i = (−1)k Nk+1 (q)(1 + q)2n+1−k . (2.8) i=1 k k=0 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 2n+1 ! ! X X 2n + 1 2n + 1 − k fm = (−1)k Nk+1,j j=0 k=0 k m−j ! 2n + 1 − k Chú ý rằng Nk+1,j là một đa thức của k có bậc m + j − 2, m−j mà không vượt quá 2n khi1 ≤ m ≤ n + 1. Từ công thức cơ bản n ! ( X n 0 nếu 0 ≤ r < n, (−1)k (x − k)r = k n! nếu r = n, k=0
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) = q 2n+3 fn (q −1 ) bởi vì q n+1 Nn (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 ! ! n−1 ! X 1 n n 2k−2 X n−1 q (1 + q)2n−2k = Ck+1 q k (1 + q)k . k=1 n k−1 k k k=0 Thay n bằng n + 1 ta nhận được n ! 2 q 2n+2 X n Nn+1 2 (1 + q) = Ck+1 q k+2 (1 + q)k , (1 + q) k k=0 và sử dụng (2.5), ta suy ra rằng n ! q2 X n q n+2 (1 + q)n Cn+1 = (−1)n−k Nk+1 2 (1 + q)2k+2 . k (1 + q) k=0 q Thay q bằng , sau khi rút gọn, ta có (2.4). q−1 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 ! X 4r + 3 2n + 1 (2n − 1)Cn = (−1)r 2n−2r−1 Cr . r=0 2n + 1 n − 2r − 1 Như vậy C2k ≡ 0mod 2 và C2k−1 ≡ Ck−1 mod 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 q n ở cả hai vế của (2.2), chúng ta có được đồng nhất thức
15 sau : ! n X 2k + 1 2n + 1 (−1)k = 0, (n ≥ 1). 2n + 1 n−k k=0 Đồ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 ! X 2n Cn = (−1)k Ck+1 22n−k . k k=0 • Chọn q = −1 trong (2.4) dẫn đến một đồng nhất thức đã biết [2] n ! X n Cn+1 = (−1)k Ck+1 4n−k . k k=0 p • Chọn q = (−1) trong (2.4) dẫn đến đồng nhất thức Touchard [2] n ! X n Cn+1 = Ck 2n−2k . 2k k=0 √ √ √ • Cho q = 2 trong (2.4). Bởi vì (1 − 2)n = (Pn + Pn−1 ) − Pn 2, 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 : 2n ! X 2n 2n+1 C2n+1 = (−1)k Nk+1 (2)P4n−2k−1 k k=0 2n+1 ! X 2n + 1 2n+1 C2n+2 = (−1)k Nk+1 (2)P4n−2k+2 k k=0 √ !n+1 √ √ 1− 5 Ln − Fn 5 • Cho q = 5 trong (2.4), theo các hệ thức = , 2 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 ! X 2n 5n+1 C2n+1 = (−1)k Nk+1 (5)L4n−2k−1 24n−2k−1 , k k=0 2n+1 ! X 2n + 1 5n+1 C2n+2 = (−1)k Nk+1 (5)F4n−2k−1 24n−2k−1 . k k=0
17 Chương 3 Một dãy số nguyên có liên quan đến đa thức Narayana Chương này trình bày kết quả chính của bài báo [6]. 3.1 Định nghĩa dãy An Ta biết rằng, đa thức (z + 1)N n (z) − N n+1 (z) = (1 − z)z n−1 + . . . có thể biểu diễn một cách duy nhất theo các đa thức z m N n−2m+1 (z), bậc n − 1. Do đó ta có thể định nghĩa dãy số thực Am (n) bởi ! X n−1 (z + 1)N n (z) − N n+1 (z) = (−z)m Am (n)N n−2m+1 (z). m≥1 2m − 1 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 : ! X n−1 − z k (z + 1)n−2k Ck . 2k − 1 k≥0 Tương tự, vế phải trở thành ! ! X n−1 n − 2m (−1)m z m+n (z + 1)n−2m−2r Am (n)Cr m≥1,r≥0 2m − 1 2r
18 So sánh các hệ số của z k (z + 1)n−2k ta nhận được ! ! ! n−1 X n − 1 n − 2m −Ck = (−1)m Am (n)Cr , 2k − 1 2m − 1 2r m+r=k và do đó ! r X 2r − 1 Cr = Aj (n)Cr−j j=1 2j − 1 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 ! X 2n − 1 (−1)n−1 An = Cn + (−1)j Aj Cn−j , n ≥ 2. j=1 2j − 1 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. 3.2 Tính chất của dãy An Đị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 X Cn X 1 C(z) = zn = zn n≥0 (2n)! n≥0 n!(n + 1)! và X Am A(z) = (−1)m−1 z m−1 . m≥1 (2m − 1)! Ta có d A(z)C(z) = 2 C(z). dz
19 k Q Cho x là một số thực dương, ta kí hiệu (x)k = (x + i − 1) và xét đa i=1 thức X 1 H(z) = zn. n≥0 n!(x)n H 0 (z) Từ trang 23 trong [7], ta biết rằng cũng là một đa thức. Tính H(z) chất của đa thức này được cho trong bổ đề sau, H 0 (z) Bổ đề 3.2. Xét đa thức P (z) = . Ta có các hệ số của P (−z) đều H(z) dương. Chứng minh. Ta có X 1 zn H(z) = = 0 F1 (x + 1; z). n≥0 (x)n n! n! Ở đó 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ó d 1 0 F1 (x; z) = 0 F1 (x + 1; z). dz x Như vậy 0 F1 (x + 1; z) P (z) = . x 0 F1 (x; z) 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 0 F1 (x + 1; z) 1 = z x0 F1 (x; z) x+ z (x + 1) + z (x + 2) + (x + 3) + . . . 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 ! X k k1 + k2 − 1 (1 + f1 z)−k1 = f1 2 (−z)k2 k2 k2 ≥0