Luận văn Thạc sĩ Toán học: Phép biến đổi các dãy số nguyên và ứng dụng

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

Thêm vào BST

Báo xấu

23
lượt xem 5
download

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

Ngoài các phần Mở đầu, Kết luận, luận văn chia thành hai chương như sau: Chương 1 - Số Catalan và nhóm Riordan. Chương 2 - Phép biến đổi dãy số nguyên, phân số liên tục và phương trình Pell suy rộng. Mời các bạn tham khả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: Phép biến đổi các dãy số nguyên và ứng dụng

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC TRẦN THỊ THU THỦY PHÉP BIẾN ĐỔI CÁC DÃY SỐ NGUYÊN VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2015
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC TRẦN THỊ THU THỦY PHÉP BIẾN ĐỔI CÁC DÃY SỐ NGUYÊN VÀ ỨNG DỤNG 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: GS.TSKH. HÀ HUY KHOÁI Thái Nguyên - 2015
iii Mục lục Lời cảm ơn 1 Mở đầu 2 1 Số Catalan và nhóm Riordan 3 1.1 Số Catalan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.1 Định nghĩa hàm sinh . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Nhóm Riordan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2 Phép biến đổi dãy số nguyên, liên phân số 8 X n 2.1 Phép biến đổi nhị thức bn = (nk ) rn−k ak . . . . . . . . . . . . . . . . . 8 k=0 n b2c X 2.2 Phép biến đổi bn = n−k rn−2k ak . . . . . . . . . . . . . . . . . . . . 12 k k=0 n X 2.3 Phép biến đổi bn = n+k ak . . . . . . . . . . . . . . . . . . . . . . . 15 2k k=0 n X 2.4 Phép biến đổi bn = (n2k ) ak . . . . . . . . . . . . . . . . . . . . . . . . 22 k=0 n X 2.5 Phép biến đổi bn = n−k ak . . . . . . . . . . . . . . . . . . . . . . . 24 2k k=0 n X 2.6 Phép biến đổi bn = n+k ak . . . . . . . . . . . . . . . . . . . . . . . 27 3k k=0 2.7 Liên phân số hai chiều và tam giác số . . . . . . . . . . . . . . . . . . . . 29 bn 2 c X 2.8 Phép biến đổi bn = n−k an−2k . . . . . . . . . . . . . . . . . . 30 n−2k k r k=0 2.9 Phép dựng hình Deleham . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Kết luận và Đề nghị 42 Tài liệu tham khảo 43
1 Lời cảm ơn Trước hết, tôi muốn gửi những lời biết ơn sâu sắc tới người hướng dẫn khoa học của mình, GS.TSKH. Hà Huy Khoái, người đã hết lòng giúp đỡ, động viên và chỉ bảo tôi trong quá trình học tập và luận văn này. Tôi muốn gửi lời cảm ơn đến Trường Đại học Khoa học - Đại học Thái Nguyên vì luôn tạo điều kiện thuận lợi dành cho tôi trong suốt thời gian học tập tại Trường. Tôi xin bày tỏ lòng biết ơn đến Ban Giám hiệu Trường Trung học phổ thông Hồng Bàng (Thành phố Hải Phòng) đã luôn tạo điều kiện tốt để tôi hoàn thành luận văn này. Cuối cùng tôi xin gửi những tình cảm đặc biệt nhất đến đại gia đình tôi, những người luôn động viên và chia sẻ những khó khăn trong quá trình hoàn thành luận văn.
2 Mở đầu Nhiều dãy cổ điển có hàm sinh được biểu diễn thành liên phân số. Nhiều dãy quan trọng khác nảy sinh từ việc áp dụng các phép biến đổi vào những dãy như thế có biểu diễn liên phân số đã biết. Do đó nếu ta có thể biểu diễn kết quả của phép biến đổi ở dạng liên phân số, ta có thể suy ra biểu diễn liên phân số của dãy mới. Tất cả các phép biến đổi mà tôi quan tâm đến là phép biến đổi sẽ được miêu tả bằng mảng Riordan (thông thường), hay mảng Riordan mở rộng. Ngoài các phần Mở đầu, Kết luận, luận văn chia thành hai chương như sau: • Chương 1. Số Catalan và nhóm Riordan. • Chương 2. Phép biến đổi dãy số nguyên, phân số liên tục và phương trình Pell suy rộng. Thái Nguyên, ngày 26 tháng 03 năm 2015 Trần Thị Thu Thủy Học viên Cao học Toán Lớp B, khóa 06/2013-06/2015 Chuyên ngành Phương pháp Toán sơ cấp Trường Đại học Khoa học - Đại học Thái Nguyên Email: tranthuyhb1978@gmail.com
3 Chương 1 Số Catalan và nhóm Riordan Các dãy số được nhắc đến trong luận văn này thường được ký hiệu là Annnnnn. Đó là số thứ tự của dãy trong Online Encyclopedia of Integer Sequences [4]. 1.1 Số Catalan 1.1.1 Định nghĩa hàm sinh Định nghĩa 1.1. Cho dãy số a0 , a1 , . . . , an , . . . Chuỗi hình thức A(x) = a0 + a1 x + a2 x2 + . . . + an xn + . . . gọi là hàm sinh của dãy (an ). Ta gọi đó là chuỗi hình thức vì ta không xét đến tính hội tụ hay tính giá trị của chuỗi mà ta chỉ xem đó như là một cách viết thuận tiện. Định nghĩa 1.2. Số Catalan là số được xác định một cách truy hồi như sau: c0 = 1, cn = c0 cn−1 + c1 cn−2 + . . . + cn−1 c0 , với n = 1, 2, 3, ... Số Catalan có nhiều định nghĩa tổ hợp khác nhau, chẳng hạn số Catalan là số các cách nối 2n điểm trên đường tròn bằng n dây cung không cắt nhau, là số cây nhị phân có gốc gồm n + 1 lá, là số đường đi ngắn nhất trên lưới nguyên từ điểm (0, 0) đến điểm (n, n) không vượt qua đường thẳng y = x... Ví dụ 1.1 (Số Catalan). Số Catalan có số hạng tổng quát   1 2n cn = n+1 n
4 có hàm sinh √ 1− 1 − 4x C(x) = . 2x Thật vậy, ta có c0 = c1 = 1. Xét dãy C(x) là hàm sinh của dãy (cn ). Khi đó C(x) = c0 + c1 x + c2 x2 + . . . + cn xn + . . . Ta có C(x)C(x) = c20 + (c1 c0 + c0 c1 )x + . . . +(cn c0 + cn−1 c1 + . . . + c0 cn )xn + . . . = c1 + c2 x + c3 x2 + . . . + cn xn + . . . Suy ra x2 C 2 (x) = x(c1 + c2 x + c3 x2 + . . . + cn xn + . . .) = x(C(x) − c0 ) = xC(x) − x. Điều này tương đương với [xC(x)]2 − xC(x) + x = 0. Giải phương trình này đối với xC(x) ta được √ 1 ± 1 − 4x xC(x) = . 2 Ta có √ 1 1 − 4x = (1 − 4x) 2 4 1 42 x2 1 · 3 · 5 · · · (2n − 3) 4n n = 1− x− 2 − ... − x − ... 2 2 2! 2n n! √ Suy ra hệ số của xk trong khai triển thành chuỗi lũy thừa của 1 − 4x bằng 1 · 3 · 5 · · · (2k − 3) · 2k − < 0, k!
5 suy ra xC(x) không thể bằng √ 1+ 1 − 4x 2 vì các hệ số của xk trong xC(x) là các số nguyên dương. Do đó √ 1 − 1 − 4x xC(x) = . 2 Vậy 2n · 1 · 3 · · · (2n − 1) cn = (n + 1)! n 2 · 1 · 2 · 3 · 4 · · · (2n − 1) · 2n = (n + 1)!2 · 4 · 6 · · · 2n n 2 (2n)! 1 = = Cn . (n + 1)!n!2 n n + 1 2n Khi đó, ta có thể được biểu diễn thành 1 C(x) = x , 1− x 1− 1 − ··· hay bằng 1 C(x) = . x2 1−x− x2 1 − 2x − x2 1 − 2x − 1 − ··· Ta sẽ ký hiệu C(x) là hàm sinh của số Catalan và ký hiệu cn là số Catalan thứ n trong toàn bộ luận văn.   2n 1 Tương tự, hàm sinh của hệ số nhị thức trung tâm   là √ , có thể được n 1 − 4x biểu diễn thành 1 1 √ = 1 − 4x 2x 1− x 1− x 1− 1 − ···
6 hoặc thành 1 1 √ = . 1 − 4x 2x2 1 − 2x − x2 1 − 2x − x2 1 − 2x − 1 − ··· Cho P là một phát biểu, ta viết [P] = 1 nếu P đúng, và [P] = 0 nếu P sai. Chú ý rằng nếu ta có dãy a0 , a1 , a2 , . . . thì dãy thoáng của dãy này được định nghĩa là a0 , 0, a1 , 0, a2 , 0, a3 , 0, . . . với các số 0 xen kẽ. Nếu (an ) có hàm sinh g(x), thì dãy thoáng có hàm sinh g(x2 ). 1.2 Nhóm Riordan Nhóm Riordan là một tập vô hạn các ma trận tam giác dưới có các phần tử là số nguyên, trong đó mỗi ma trận được định nghĩa bằng một cặp hàm sinh g(x) = 1 + g1 x + g2 x2 + . . . và f (x) = f1 x + f2 x2 + . . . với f1 6= 0. Ma trận liên kết là ma trận có cột thứ j được sinh bởi g(x)f (x)j (cột đầu tiên được đánh chỉ số bằng 0). Do vậy phần tử thứ i của cột thứ j là Ti,j = [x]j g(x)f (x)j trong đó toán tử [xn ] cho ra hệ số của xn trong chuỗi lũy thừa được áp dụng vào. Ma trận tương ứng với bộ g, f được ký hiệu bằng (g, f ) hoặc R(g, f ). Luật nhóm được cho bởi (g, f ) ∗ (h, l) = (g(h ◦ f ), l ◦ f ). Phần tử đơn vị của luật này là I = (1, x) và nghịch đảo của (g, f ) là (g, f )−1 = (1/(g ◦ f ), f ) với f là nghịch đảo hợp thành của f. Xn Mảng Riordan có dạng (g(x), x), với g(x) = ak xk là hàm sinh của dãy an , k=0 được gọi là dãy mảng của dãy an . Số hạng tổng quát của nó là Tn,k = [xn ]g(x)xk = [xn−k ]g(x) = an−k .
7 Các mảng có dạng như trên tạo thành một nhóm con của nhóm Riordan, được gọi là nhóm Appell. Nếu M là ma trận (g, f ), và a = (a0 , a1 , . . .)T là một dãy số nguyên có hàm sinh thông thường A(x), thì dãy M a có hàm sinh thông thường g(x)A(f (x)). Điều này suy ra từ nếu M = (Tn,k )n,k≥0 ta có n X ∞ X Tn,k ak = [xn ]g(x)f (x)k ak k=0 k=0 ∞ X n = [x ]g(x) f (x)k ak k=0 = [xn ]g(x)A(f (x)). Do đó ma trận (vô hạn) (g, f ) có thể được coi là tác động trên vành số nguyên ZN với phép nhân, trong đó một dãy được xem như một vecto cột (vô hạn). Chúng ta có thể mở rộng tác động trên vành chuỗi lũy thừa Z[[x]] bằng (g, f ) : A(x) −→ (g, f ) · A(x) = g(x)A(f (x)). Ví dụ 1.2. Ma trận nhị thức B là số hạng 1−x1 x của nhóm Riordan. Nó có số , 1−x   n hạng tổng quát  . Tổng quát hơn, Br là số hạng 1−rx 1 x của nhóm Riordan , 1−rx k   n với số hạng tổng quát   rn−k . Có thể chứng minh được rằng nghịch đảo B−r của k B là r 1 x , 1 + rx 1 + rx Nếu f1 = 0 ta gọi ma trận là mảng Riordan “mở rộng”. Ma trận như vậy không khả nghịch.
8 Chương 2 Phép biến đổi dãy số nguyên, liên phân số n X 2.1 Phép biến đổi nhị thức bn = (nk) r n−k ak k=0 Một phép biển đổi dãy số nguyên phổ biến là phép biến đổi nhị thức, biến dãy với số hạng tổng quát an thành dãy có số hạng tổng quát bn định nghĩa bởi   n X n bn =   ak . k=0 k Tổng quát hơn, với r ∈ Z, ta có thể định nghĩa “phép biến đổi nhị thức thử r” của an là dãy có số hạng tổng quát   n X n bn = rn−k   ak . k=0 k Từ lý thuyết của mảng Riordan suy ra phép biến đổi này có thể được biểu diễn bởi ma trận 1 x , . 1 − rx 1 − rx Ta nhắc lại nếu g(x) là hàm sinh của dãy an , thì hàm sinh của dãy bn là 1 x 1 x , · g(x) = . 1 − rx 1 − rx 1 − rx 1 − rx
9 Áp dụng điều này vào biểu diễn liên phân số bên trên, ta thu được biểu diễn hàm sinh của phép biến đổi nhị thức thứ r của số Catalan như sau. Đầu tiên 1 x 1 1 , · C(x) = x 1 − rx 1 − rx 1 − rx 1−rx 1− x 1−rx 1− x 1−rx 1− 1 − ··· 1 = x 1 − rx − x 1−rx 1− x 1−rx 1− 1 − ··· 1 = x 1 − rx − x 1− x 1 − rx − x 1− x 1 − rx − 1 − ··· tiếp theo, 1 x 1 1 , · C(x) = 1 − rx 1 − rx 1 − rx x2 x (1−rx)2 1− 1−rx − x2 x (1−rx)2 1 − 2 1−rx − x2 x (1−rx)2 1 − 2 1−rx − 1 − ··· 1 = x2 1−rx 1 − rx − x − x2 x (1−rx)2 1 − 2 1−rx − x2 x (1−rx)2 1 − 2 1−rx − 1 − ··· 1 = x2 1 − rx − x − x2 1 − rx − 2x − x2 1 − rx − 2x − 1 − ··· Tổng quát hoá ví dụ này, ta thu được hai mệnh đề sau.
10 Mệnh đề 2.1. Giả sử an là dãy có hàm sinh g(x) biểu diễn dưới dạng 1 g(x) = α1 x . 1− α2 x 1− 1 − ··· Khi đó phép biến đổi nhị thức thứ r của an có hàm sinh biểu diễn dưới dạng 1 α1 x 1 − rx − α2 x 1− α3 x 1 − rx − α4 x 1− α5 x 1 − rx − 1 − ··· Mệnh đề 2.2. Giả sử an là dãy có hàm sinh g(x) biểu diễn dưới dạng 1 g(x) = . β1 x2 1 − α1 x − β2 x2 1 − α2 x − 1 − ··· Khi đó phép biến đổi nhị thức thứ r của an có hàm sinh biểu diễn dưới dạng 1 . β1 x2 1 − rx − α1 x − β2 x2 1 − rx − α2 x − β3 x2 1 − rx − α3 x − 1 − rx − · · · Ta chú ý biểu diễn cuối cùng có thể được viết lại thành 1 . β1 x2 1 − (α1 + r)x − β2 x2 1 − (α2 + r)x − β3 x2 1 − (α3 + r)x − 1 − rx − · · · Do đó dạng của liên phân số trong trường hợp này không thay đổi: chỉ hệ số của x trong mỗi trường hợp tăng thêm (hay giảm đi). Có thể chứng minh thông qua kỹ thuật nghịch đảo chuỗi rằng: 1 x 1 x , · , 1 − αx − βx2 1 − αx − βx2 1 − rx 1 − rx
11 1 x = , . 1 − (α + r)x − βx2 1 − (α + r)x − βx2   2n Ví dụ 2.1. Hệ số tam thức trung tâm. Hệ số nhị thức trung tâm   có hàm sinh n biểu diễn dưới dạng 1 . 2x 1− x 1− x 1− 1 − ··· Do  đóhệ số tam thức trung tâm, là nghịch đảo phép biến đổi nhị thức (đầu tiên) của 2n   có hàm sinh biểu diễn dưới dạng n 1 . 2x 1+x− x 1− x 1+x− x 1− x 1− x 1+x− 1 − ··· Ví dụ 2.2. Số Motzkin. Số Motzkin Mn được đưa ra bởi biến đổi nhị thức của dãy số Catalan thoáng 1, 0, 1, 0, 2, 0, 5, . . . , có hàm sinh C(x2 ). Vì 1 C(x2 ) = x2 1− x2 1− 1 − ··· nên số Motzkin có hàm sinh biểu diễn dưới dạng 1 M (x) = . x2 1−x− x2 1−x− x2 1−x− 1 − ··· Ví dụ 2.3. Hệ số tam thức trung tâm. Hệ số tam thức trung tâm cũng có thể được biểu diễn bằng phép biến đổi nhị thức của hệ số nhị thức trung tâm thoáng. Cách biểu
12 diễn này có hàm sinh là 1 1 √ = 1 − 4x2 2x2 1− x2 1− x2 1− 1 − ··· và do đó hệ số tam thức nhị phân trung tâm có hàm sinh là 1 . 2x2 1−x− x2 1−x− x2 1−x− 1 − ··· n b2c X 2.2 Phép biến đổi bn = n−k k r n−2k ak k=0 Ma trận có số hạng tổng quát   h n i n−k k≤b c   rn−2k 2 k có thể được biểu diễn bằng ma trận Riordan mở rộng 1 x2 , . 1 − rx 1 − rx Điều này suy ra từ số hạng tổng quát của 1 x2 , 1 − rx 1 − rx có dạng 1 x2k n [x ] k = [xn−2k ](1 − rx)−k−1 1 − rx (1 − rx)   ∞ X −k − 1 = [xn−2k ]   (−1)j rj xj j=0 j
13   ∞ X n+k = [xn−2k ]   rj xj j=0 j   n−k = [n − 2k ≥ 0]   rn−2k . n − 2k Do đó ta có Mệnh đề 2.3. Cho an là dãy số có hàm sinh biểu diễn dưới dạng 1 g(x) = α1 x . 1− α2 x 1− 1 − ··· Khi đó dãy bn với số hạng tổng quát   b n2 c X n−k bn =   rn−2k ak k=0 k có hàm sinh là 1 . α1 x2 1 − rx − α2 x2 1− α3 x2 1 − rx − α4 x2 1− 1 − ··· Chứng minh. Hàm sinh của dãy chuyển đổi có dạng 1 x2 1 1 , · g(x) = 1 − rx 1 − rx 1−x x2 α1 1−rx 1− x2 α2 1−rx 1− 1 − ··· 1 = α1 x2 1 − rx − x2 α2 1−rx 1− 1 − ··· 1 = α1 x2 1 − rx − α2 x2 1− α3 x2 1 − rx − α4 x2 1− 1 − rx − · · ·
14 Ví dụ 2.4. Số đường Motzkin có độ dài n không có bước mức ở mức lẻ. Dãy có số hạng tổng quát   n b2c Xn−k an =   ck k=0 k có hàm sinh là 1 . x2 1−x− x2 1− x2 1−x− x2 1− 1 − ··· Mệnh đề 2.4. Cho an là dãy có hàm sinh g(x) được biểu diễn dưới dạng 1 g(x) = . β1 x2 1 − α1 x − β2 x2 1 − α2 x − 1 − ··· Khi đó hàm sinh của dãy n   b2c X n−k bn =   rn−2k ak k=0 k có biểu diễn là 1 . β1 x4 1 − rx − α1 x2 − β2 x4 1 − rx − α2 x2 − 1 − ··· Chứng minh. Ta có 1 x2 1 1 , · g(x) = 4 1 − rx 1 − rx 1−x x β1 (1−rx) 2 x2 1 − α1 1−rx − 4 x β2 (1−rx) 2 x2 1 − α2 1−rx − 1 − ··· 1 = 4 x β1 1−rx 1 − rx − α1 x2 − 4 x β2 (1−rx)2 x2 1 − α2 1−rx − 1 − ···
15 1 = . β1 x4 1 − rx − α1 x2 − β2 x4 1 − rx − α2 x2 − 1 − ··· Ví dụ 2.5. Số cây được sắp thứ tự có n cạnh và không có nhánh có độ dài 1. Số này là A026418, bắt đầu bằng 1, 0, 1, 1, 2, 3, 6, 11, 22, . . . Dãy bắt đầu bằng 1, 1, 2, 3, 6, . . . có số hạng tổng quát n   b2c X n−k   rn−2k Mk k=0 k và do dó có hàm sinh là 1 . x4 1 − x − x2 − x4 1 − x − x2 − 1 − ··· n X 2.3 Phép biến đổi bn = n+k 2k ak k=0 Phép biến đổi mà ánh xạ dãy có số hạng tổng quát an thành dãy có số hạng tổng quát   n X n+k bn =   ak k=0 2k có thể được biểu diễn bằng ma trận Riordan 1 x , . 1 − x (1 − x)2 Do đó ta có mệnh đề sau. Mệnh đề 2.5. Cho an là một dãy số với hàm sinh g(x) được biểu diễn dưới dạng 1 g(x) = α1 x . 1− α2 x 1− 1 − ···
16 Khi đó dãy số với số hạng tổng quát bn , cho dưới dạng   n X n+k bn =   ak k=0 2k có biểu diễn của hàm sinh là 1 x 1 , · g(x) = α1 x . 1 − x (1 − x)2 1−x− α2 x 1−x− 1 − x − ··· Chứng minh. Ta có 1 x 1 1 , · g(x) = x 1 − x (1 − x)2 1−x α1 (1−x) 2 1− x α2 (1−x)2 1− 1 − ··· 1 = x α1 1−x 1−x− x α2 (1−x) 2 1− 1 − ··· 1 α1 x . 1−x− α2 x 1−x− 1 − x − ··· Ví dụ 2.6. Số Schr¨oder lớn. Số Schr¨oder lớn Sn A006318 được định nghĩa bằng   n X n+k Sn =   ck . k=0 2k Do đó chúng có hàm sinh biểu diễn bằng 1 g(x) = x . 1−x− x 1−x− x 1−x− 1 − x − ··· Ví dụ 2.7. Số Delannoy trung tâm. Số Delannoy trung tâm dn A001850 được định nghĩa bằng    n X n+k 2k dn =   . k=0 2k k
17 Do đó chúng có biểu diễn của hàm sinh là 1 . 2x 1−x− x 1−x− x 1−x− 1 − x − ··· Tổng quát hơn, ta có thể khảo sát tác động của mảng Riordan 1 x , 1 − rx (1 − rx)2 với r ∈ Z. Ta thu được Mệnh đề 2.6. Cho an là dãy số có hàm sinh g(x) được biểu diễn dưới dạng 1 g(x) = α1 x . 1− α2 x 1− 1 − ··· Khi đó dãy số bn với hàm sinh được cho bởi 1 x g 1 − rx (1 − rx)2 là khai triển của 1 α1 x . 1 − rx − α2 x 1 − rx − α3 x 1 − rx − 1 − rx − · · · Trong trường hợp này,   n X n+k bn =   rn−k ak k=0 2k là số hạng tổng quát của dãy biến đổi. Ví dụ 2.8. Trường hợp r = −1. Trường hợp này tương đương với mảng Riordan 1 x , . 1 − rx (1 − rx)2 Cụ thể bây giờ ta có   n X n+k   (−1)n−k ck = 0n = δ0n , k=0 2k