Luận văn Thạc sĩ Toán học: Bài toán phân hoạch số nguyên dương

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

Thêm vào BST

Báo xấu

59
lượt xem 4
download

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

Bài toán biểu diễn số nguyên dương dạng tổng các số nguyên dương đã có lịch sử lâu đời. Leibniz là người đầu tiên nghiên cứu bài toán này, sau đó Euler, Sylvester, Hardy, Ramanujan, Andrews... là các nhà toán học có những đóng góp quan trọng. Đề tài nghiên cứu sẽ đi sâu hơn về vấn đề này.

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: Bài toán phân hoạch số nguyên dương

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC .................................................. ĐINH THỊ THU HUẾ BÀI TOÁN PHÂN HOẠCH SỐ NGUYÊN DƯƠNG LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2017
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC .................................................. ĐINH THỊ THU HUẾ BÀI TOÁN PHÂN HOẠCH SỐ NGUYÊN 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 - 2017
i Mục lục MỞ ĐẦU 1 1 Một số kết quả kinh điển về bài toán phân hoạch số nguyên dương 3 1.1 Lịch sử phát triển của bài toán phân hoạch số nguyên dương 3 1.2 Một số kết quả kinh điển . . . . . . . . . . . . . . . . . . . 11 1.2.1 Công thức gần đúng cho p(n) . . . . . . . . . . . . 11 1.2.2 Hàm sinh của hàm phân hoạch . . . . . . . . . . . 13 1.2.3 Đồng nhất thức Rogers–Ramanujan . . . . . . . . . 18 1.2.4 Tính chất đồng dư của p(n) . . . . . . . . . . . . . 22 1.2.5 Biểu diễn đồ thị của các phân hoạch và chứng minh Định lí số ngũ giác của Euler . . . . . . . . . . . . . 27 2 Một số lớp bài toán phân hoạch số nguyên khác nhau và các bài toán liên quan 31 2.1 Phân hoạch thành những phần phân biệt và ánh xạ đối hợp của Franklin . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.2 Phân hoạch thành những phần lẻ và song ánh Sylvester . . 34 2.3 Một số bài toán liên quan . . . . . . . . . . . . . . . . . . . 35 2.3.1 Một số bài toán chứng minh . . . . . . . . . . . . . 35 2.3.2 Bài toán chia kẹo của Euler . . . . . . . . . . . . . . 39 KẾT LUẬN 50 TÀI LIỆU THAM KHẢO 51
ii Danh mục các hình vẽ Hình 2.1:..........................................................................................33 Hình 2.2:..........................................................................................33 Hình 2.3:..........................................................................................35 Hình 2.4:..........................................................................................36
1 MỞ ĐẦU Bài toán biểu diễn số nguyên dương dạng tổng các số nguyên dương đã có lịch sử lâu đời. Leibniz là người đầu tiên nghiên cứu bài toán này, sau đó Euler, Sylvester, Hardy, Ramanujan, Andrews... là các nhà toán học có những đóng góp quan trọng. Bài toán nói trên xuất hiện trong nhiều vấn đề khác nhau của toán học và là đề tài nghiên cứu sôi nổi cho đến tận ngày hôm nay (Các công trình của Okounkov, Giải thưởng Fields 2006, có liên quan đến việc ứng dụng bài toán trên trong xác suất, hình học đại số, cơ học thống kê,...). Dưới sự hướng dẫn tận tình của GS.TSKH. Hà Huy Khoái, tác giả chọn đề tài:"Bài toán phân hoạch số nguyên dương". Luận văn có mục tiêu giới thiệu bài toán biểu diễn số nguyên dương dưới dạng tổng, từ lịch sử phát triển và những kết quả kinh điển, đến một số kết quả gần đây. Luận văn cũng trình bày một số bài toán liên quan đến bài toán nói trên. Với mục tiêu trên, tác giả tiến hành nghiên cứu hai chương: Chương 1. Một số kết quả kinh điển về bài toán phân hoạch số nguyên dương 1.1. Lịch sử phát triển của bài toán phân hoạch số nguyên dương 1.2. Một số kết quả kinh điển
2 Chương 2. Một số lớp bài toán phân hoạch số nguyên khác nhau và một số bài toán liên quan 2.1. Phân hoạch thành những phần phân biệt và ánh xạ đối hợp của Franklin 2.2. Phân hoạch thành những phần lẻ và song ánh Sylvester 2.3. Một số bài toán liên quan. Luận văn được hoàn thành dưới sự hướng dẫn, giúp đỡ tận tình của GS.TSKH. Hà Huy Khoái, tác giả xin bày tỏ lòng biết ơn và kính trọng sâu sắc đối với Giáo sư. Tác giả xin gửi lời cảm ơn chân thành đến Ban giám hiệu, Phòng sau đại học và Khoa Toán-Tin trường Đại học Khoa học - Đạị học Thái Nguyên đã tạo mọi điều kiện thuận lợi cho tác giả trong suốt quá trình học tập và nghiên cứu tại trường. Xin chân thành cảm ơn sự giúp đỡ của bạn bè, người thân trong thời gian qua. Mặc dù đã có nhiều cố gắng, song do thời gian và trình độ còn hạn chế nên bản luận văn khó tránh khỏi những thiếu sót nhất định. Tác giả rất mong nhận được ý kiến đóng góp của quý độc giả để bản luận văn này được hoàn thiện hơn. Tác giả xin chân thành cảm ơn! Thái Nguyên, tháng 06 năm 2017 Tác giả Đinh Thị Thu Huế
3 Chương 1 Một số kết quả kinh điển về bài toán phân hoạch số nguyên dương Mục đích của chương này là trình bày lịch sử phát triển và một số kết quả kinh điển về bài toán phân hoạch số nguyên dương. Tài liệu tham khảo chính của Chương là [3], [4] . 1.1 Lịch sử phát triển của bài toán phân hoạch số nguyên dương Phân hoạch lần đầu tiên xuất hiện trong bức thư tay của Leibnitz viết vào năm 1669 gửi cho John Bernoulli, ông hỏi Bernoulli liệu có kiểm tra nhanh được số cách viết một số nguyên dương đã cho thành tổng của hai hay nhiều số nguyên? Từ đây lý thuyết phân hoạch được hình thành và là một nhánh quan trọng của lý thuyết số. Khái niệm phân hoạch các số nguyên không âm cũng thuộc về toán học tổ hợp (xem [4]). Định nghĩa 1.1 (xem [4]). Một phép phân hoạch của số nguyên dương n là một dãy không tăng hữu hạn của các số nguyên dương λ1 > λ2 > . . . > λr sao cho ri=1 λi = n, λi được gọi là các phần hoặc các số hạng của phân P hoạch. Đôi khi phân hoạch (λ1 , λ2 , . . . , λr ) được kí hiệu bởi λ và ta viết là λ ` n hoặc | λ |= n.
4 Định nghĩa 1.2 (xem [4]). Hàm phân hoạch p(n) là số các phân hoạch của n. Khi xét phép phân hoạch của n có một số chú ý sau (xem [4]): Chú ý 1.1. Chúng ta thấy 0 có một phân hoạch, phân hoạch rỗng, nó không có phần tử nào. Ta quy ước p(0) = 1. Chú ý 1.2. Thường viết tắt phần lặp bằng cách sử dụng lũy thừa. Chú ý 1.3. Theo định nghĩa phân hoạch thứ tự không quan trọng. 4+3 và 3+4 đều là một phân hoạch của 7. Một tập hợp có thứ tự được gọi là một phép hợp thành. Do đó, 4+3 và 3+4 là hai phép hợp thành khác nhau của 7. Ví dụ 1.1. Có năm phân hoạch của số 4 là 4, 31, 22 , 212 , 14 . Có bảy phân hoạch của số 5 là 5, 41, 32, 312 , 22 1, 213 , 15 . Leibnitz quan sát có 3 phân hoạch của 3 (3, 21, 13 ), 5 phân hoạch của 4. Sau đó ông cũng quan sát được có 7 phân hoạch của 5 và 11 phân hoạch của 6. Điều này gợi ý, số phân hoạch của n bất kỳ luôn là một số nguyên tố. Tuy nhiên, điều này không đúng khi tính toán được 15 phân hoạch của 7. Như vậy ngay từ những bước khởi đầu, bài toán phân hoạch đã dẫn đến câu hỏi mở mà đến tận ngày hôm nay vẫn chưa có lời giải: tồn tại vô hạn hay hữu hạn n sao cho số phân hoạch n là một số nguyên tố? Bên cạnh đó là những câu hỏi về p(n) như: cấp tăng của nó như thế nào? Tính chẵn lẻ của nó? Liệu nó có những tính chất số học đặc biệt nào? Có cách nào để tính p(n) hiệu quả không?(xem [3]). Từ đây thiết lập những chủ đề khác nhau và lý thuyết phân hoạch được phát triển xa hơn bởi nhiều nhà Toán học vĩ đại, nổi bật trong số họ là Euler, Gauss, Jacobi, Cayley, Sylvester, Hardy, Ramanujan, Rademacher, Schur, Mac Mahon, Gupta, Gordon, Andrews, Stanley. . . Công việc nghiên cứu của Ramanujan cùng Hardy thực sự cách mạng hóa việc nghiên cứu về thuyết phân hoạch. Bởi những ứng dụng vĩ đại của nó trong các lĩnh vực khác nhau như xác suất thống kê, vật lý cơ học. . . lý thuyết phân hoạch trở thành lĩnh vực nghiên cứu sôi nổi của lý thuyết số.
5 Có thể thấy p(n) tăng rất nhanh theo n. Thậm chí, nếu một người nào đó có thể tập trung làm việc một cách hoàn hảo thì cũng phải mất 126000 năm để viết tất cả 3972999029388 phân hoạch của 200. Ramanujan đã tự hỏi mình một câu hỏi cơ bản: Chúng ta có thể tìm p(n) mà không cần viết tất cả các phân hoạch của n không?” Câu hỏi này đã được Hardy và Ramanujan trả lời vào năm 1918. Họ đã đưa ra công thức gần đúng cho p(n). Tuy tiên D.H.Lehmer nhận thấy chuỗi Hardy – Ramanujan phân kỳ. Năm 1937, H. Rademacher thay thế điều kiện để nhận được p(n) là chuỗi hội tụ. Hardy – Ramanujan – Rademacher lập ra công thức mở rộng cho p(n) nổi tiếng, đó là kết quả đáng ghi nhận nhất trong toán học. Nó cho thấy sự tương tác giữa một hàm số học p(n) và một số kỹ thuật tính toán. Nó không chỉ là công thức lý thuyết cho p(n) mà còn là công thức cho phép tính tương đối nhanh (xem [4]– Tr 6). Một số giá trị của p(n) n : 1 2 3 4 5 6 9 20 50 100 200 p(n) : 1 2 3 5 7 11 30 627 204226 190569292 3972999029388 Nhiều khi chúng ta chỉ cần quan tâm đến những bài toán không nhất thiết phải xét đến tất cả các phân hoạch của n mà chỉ các phân hoạch đặc biệt nào đó của n. Ví dụ 1.2. Trong số 22 phân hoạch của số 8, chỉ có sáu phân hoạch chứa các phần là số lẻ 71, 53, 513 , 32 12 , 315 , 18 và cũng có 6 phân hoạch trong đó các phần tử phân biệt 8, 71, 62, 53, 521, 431. Về vấn đề này đã được Euler bắt đầu nghiên cứu vào năm 1674. Ph.Naudé hỏi Euler về phân hoạch một số nguyên dương n thành m phần nhất định. Đặc biệt, Naudé đã hỏi ông có bao nhiêu phân hoạch của 50 thành 7 phần riêng biệt. Câu trả lời đúng là 522, điều này khó có khả năng thu được bằng cách viết ra tất cả các phân hoạch của 50 thành 7 phần. Để giải quyết vấn đề này Euler đã khám phá và giới thiệu hàm sinh của hàm phân hoạch, các đồng nhất thức, định lí số ngũ giác, đó là sự đổi mới quan trọng nhất trong toàn bộ nghiên cứu về phân hoạch. Hầu hết mọi phát hiện về phân hoạch đều nhờ vào sự bắt đầu của Euler (xem [3]).
6 Từ cuối thế kỉ XVIII cho tới nửa đầu thế kỉ XIX không xuất hiện nhiều bước tiến đáng ghi nhận trong nghiên cứu về phân hoạch. Tất nhiên điều tương tự không xảy ra với toán học nói chung. Đã có sự xuất hiện những nghiên cứu về lý thuyết biến phức và lý thuyết của hàm eliptic và chúng đã mang lại ảnh hưởng sâu sắc tới nghiên cứu về phân hoạch. Legendre, Gausse, Cauchy và những nhà toán học vĩ đại khác đã tìm ra được lời giải thích cho công trình của Euler. Trong một thế kỷ từ năm 1750 – 1850, trọng tâm chính của việc nghiên cứu là đưa ra công thức tường minh cho pm (n), số phân hoạch n thành các phần không lớn hơn m. P. Paoli, A. Dc Morgan, F.W. Herschsl, T. Kirkmar và H. Warburton, Cayley, Sylvester...đã nghiên cứu pm (n) với những giá trị nhỏ xác định của m và họ đưa ra được một số công thức nhất định. Tuy nhiên, Sylvester mới là nhà toán học tiếp theo đưa ra được cái nhìn thực sự mới cho vấn đề này(xem [3]– Tr 5). Sau khi xem xét một vài cách mà phân hoạch thực sự có thể được đưa ra dưới dạng hình học, ông khẳng định rằng phân hoạch 5 + 5 + 4 + 3 + 3 có thể được biểu diễn thuận tiện hơn nhiều dưới dạng: ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ Sylvester gọi cách biểu diễn này là biểu đồ Ferrers của phân hoạch, đặt tên theo nhà toán học N.M. Ferrers. Ông đã chú ý rằng ta có thể đếm số nút ở các cột thay vì các hàng. Lấy ví dụ như biểu đồ ở trên có thể cho ta phân hoạch 5 + 5 + 5 + 3 + 2. Hai phân hoạch từ cùng một biểu đồ như trên được gọi là liên hợp. Định nghĩa 1.3 (xem [3]). Phân hoạch n là tự liên hợp nếu liên hợp của nó trùng với chính nó.
7 Ví dụ 1.3. Phân hoạch 7+6+4+4+2+2+1 của 26 ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ Như vậy, Sylvester khẳng định một cách tiếp cận hoàn toàn mới đối với phân hoạch. Cách chứng minh của Fabian Franklin cho định lý số ngũ giác của Euler sẽ cho ta biết về giá trị của lối suy nghĩ mới này. Franklin từng là một học trò của Sylvester tại trường đại học John Hopkins và chứng minh của Franklin đã lột tả được sức mạnh trong ý tưởng của Sylvester. Hans Rademacher cho rằng nghiên cứu của Franklin là những thành tựu có ý nghĩa đầu tiên của toán học Mỹ. Nó có thể được xem như là điểm khởi đầu của một loạt những nghiên cứu sâu sắc về phân hoạch. Phân hoạch được nghiên cứu ở nhiều khía cạnh khác nhau. MacMahon đã nghiên cứu những dạng khác nhau của phân hoạch và ông là người đầu tiên nghiên cứu về phân hoạch phẳng. Định nghĩa 1.4 (xem [4]). Một phân hoạch phẳng π của n là một ma P trận các số dương, không tăng theo mỗi dòng, mỗi cột và ni,j = n. Mỗi ni,j là một bộ phận của π . n1,1 n1,2 n1,3 ... n2,1 n2,2 n2,3 ... n3,1 n3,2 n3,3 ... . . . ... . . . ... Ví dụ 1.4. Các phân hoạch phẳng của 3 1 1 1 1 , 1 1 , 1 , 2 1 , 2 , 3 1 1 1
8 Phân hoạch phẳng được gọi là đối xứng nếu ni,j = nj,i với mọi i, j . Ví dụ 1.5. Phân hoạch phẳng của 18 6 4 1 4 2 1 Nếu các phần của π giảm chặt theo mỗi hàng thì ta nói rằng π là nghiêm ngặt hàng. Nếu các phần của π là giảm chặt mỗi cột thì ta gọi π là nghiêm ngặt cột. Nếu π vừa nghiêm ngặt hàng, vừa nghiêm ngặt cột thì ta gọi π là nghiêm ngặt hàng và cột. Phân hoạch nghiêm ngặt cột cũng giống như bảng Young được sử dụng trong lý thuyết bất biến. Phân hoạch phẳng được ứng dụng trong phép biểu diễn lý thuyết nhóm đối xứng, hình học đại số và trong nhiều vấn đề tổ hợp. Phân hoạch phẳng cùng với nhiều nhất k dòng được gọi là phân hoạch k -dòng. Ký hiệu tk (n) là số phân hoạch k dòng của n. Phân hoạch phẳng là lĩnh vực được nghiên cứu tích cực. Tuy nhiên ở đây chúng ta chỉ nói đến đồng dư Ramanujan tk (n). F– Phân hoạch:(xem [4]) Một phân hoạch Frobenius suy rộng (một F – phân hoạch) của n là một ma trận 2 hàng các số nguyên ! a1 , a2 , . . . b1 , b2 , . . . trong đó, a1 > a2 > . . . > ar > 0, b1 > b2 > . . . > br > 0 sao cho n = r + ri=1 ai + ri=1 bi . P P Ví dụ 1.6. Cho n = 3, với giá trị tương ứng r = 1, 1, 1, 2, 2 và cho phép lặp tối đa 2 lần ở bất kì hàng nào thì các F – phân hoạch ! ! ! ! ! 2 0 1 1, 0 0, 0 , , , , 0 2 1 0, 0 1, 0 Chú ý : Các phân hoạch được gán cho Frobenius vì ông là người đầu tiên nghiên cứu chúng trong lý thuyết biểu diễn nhóm với các giả thiết a1 > a2 > . . . > ar > 0, b1 > b2 > . . . > br > 0.
9 φk (n) ký hiệu số các F– phân hoạch của n sao cho mỗi số hạng xuất hiện nhiều nhất k lần trong mỗi hàng. Một F – phân hoạch được gọi là một F-phân hoạch k-màu nếu trong mỗi hàng các phần là phân biệt, và lấy từ k – bản sao của các số nguyên không âm có thứ tự như sau 01 < 02 < . . . < 0k < 11 < 12 < . . . < 1k < 21 < 22 < . . . < 2k < ... Ký hiệu cφk (n) là số các phân hoạch k -màu của n. Ta sẽ đề cập ngắn gọn tính chất đồng dư Ramanujan của φk (n),cφk (n) ở phần sau. Euler đã nói về các đồng nhất thức trong phân hoạch, nhưng các kết quả của ông không thu được nhiều sự chú ý cho đến những năm đầu của thế kỉ 20, khi đồng nhất thức Rogers- Ramanujan trở nên nổi tiếng (xem [3],[4]). Nó được phát hiện đầu tiên bởi Rogers vào năm 1894 và bởi Ramanujan vào năm 1913. Sự phát hiện của Rogers được viết trong một bài báo nằm trong một cuốn Kỉ yếu của Hội Toán học Luân Đôn. Bài viết của ông đã bị lãng quên cùng thời gian. Về phần Ramanujan, ông không chứng minh được khám phá của mình nên đã gửi những đồng nhất đó tới S.H. Hardy, Hardy cũng không thể chứng minh chúng. Ông lại chuyển chúng cho Littlewood, MacMahon và Perron, và không ai có thể chứng minh được. Không ai nghĩ là chuyển chúng cho Rogers, vì vậy phát hiện của Ramanujan vẫn chưa được chứng minh. Mac Mahon đã nói không có lý do gì để nghi ngờ tính đúng đắn của nó, nhưng nó vẫn chưa được xác minh. Vào năm 1917, Ramanujan đã đọc được bài viết của Rogers trong một tờ báo cũ, niềm vui lớn với ông vì tìm được sự tương đồng. Ông đã viết thư trao đổi với Rogers. Năm 1919, Ramanujan xuất bản một bài báo trong đó có hai chứng minh (một của Rogers và một của Ramanujan) và một nhận xét của Hardy. Sau khi xuất bản, kết quả đó nổi tiếng với tên gọi đồng nhất Rogers- Ramanujan. Đồng nhất Rogers – Ramanujan là một trong những công thức đẹp nhất của toán học. Nghiên cứu về đồng nhất thức trong phân hoạch vẫn tiếp tục. Mười bốn năm sau, Hardy nhận xét về nghiên cứu của Lehmer, Alder và Rademacher: “Có thể thấy rằng không có đồng nhất nào tương ứng với modun cao hơn 5”. Kết quả này hóa ra là sai lầm. Năm 1963, B. Gordon đã thực hiện những bước đầu
10 tiên hướng tới sự khảo sát đầy đủ định lý kiểu này và đã đưa ra định lí Gordon. Định lý Gordon dẫn đến sự bùng nổ các kết quả. Năm 1982, G. Andrews đã đưa ra tương tự giải tích của định lí B. Gordon, D. Bressoud làm nên đột phá lớn về tổ hợp trong nghiên cứu về đồng nhất thức của phân hoạch. Những kết quả này được ứng dụng trong nhiều lĩnh vực khác nhau. G.Andrews và R. Askey đã chứng minh một mối liên hệ giữa đồng nhất Rogers – Ramanujan và đa thức trực giao. J. Lepowsky, A. Feingold, S. Milne và R. Wilson đã tìm thấy một liên hệ với đại số Lie, F.Dyson tìm thấy các ứng dụng của đồng nhất Rogers – Ramanujan trong vật lý hạt và R.J.Baxtes trong cơ học thống kê. Dyson lại đưa ra cách tiếp cận mới về phân hoạch, năm 1944 ông công bố một công trình trong Tạp chí khoa học Eureka của sinh viên khoa toán Cambridge, trong đó ông đưa ra khái niệm hạng của phân hoạch . Định nghĩa 1.5 (xem [5]–Tr5). Phân hoạch λ có a(λ), l(λ) lần lượt là phần lớn nhất và số các phần của λ. Khi đó r(λ) = a(λ) − l(λ) được gọi là hạng của λ. Ông phát biểu giả thuyết nói rằng hạng sẽ cho một cách diễn giải tổ hợp về các đồng nhất thức của Ramanujan. Khi vẫn còn là một sinh viên, Dyson không chứng minh được giả thuyết này. Năm 1948, Atkin và Swinnerton-Dyer đã chứng minh được giả thuyết và được công bố vài năm sau. Dyson chuyển đến Hoa Kì và đã công bố giả thuyết của ông dưới dạng một bài toán ngắn trong tờ báo Toán học Hoa Kì hàng tháng . Nathan Fine rất quan tâm đến bài toán và đưa ra ba định lý để liệt kê các phân hoạch xác định hạng. Những kết quả của ông có vẻ bí ẩn và hẳn còn giữ nguyên ở trạng thái đó nếu không có sự xuất hiện của cuốn sách "Basic hypergeometric series and applications” và bài báo của Dyson "A new symmetry of partitions". Không biết đến nghiên cứu của Fine, Dyson khám phá lại một trong những thành quả của Fine chưa được công bố, gọi nó là " phép đối xứng mới" và chứng minh nó bằng phương pháp tổ hợp. Sau đó ông suy ra điều kiện cho công thức và thu được một cách chứng
11 minh mới rất đơn giản cho định lý số ngũ giác của Euler. Thật đáng tiếc, ngoại trừ công trình của Andrews "Định lí phân hoạch của N.J. Fine", dường như không có ai nhận thấy thực ra ánh xạ Dyson, đôi khi gọi liên hợp của Dyson, có thể được dùng để chứng minh theo tổ hợp những kết quả của Fine. Nhưng ngay cả Andrews dường như cũng không biết rằng dùng ánh xạ của Dyson chứng minh được hai định lý khác của Fine. Đầu thế kỷ XX, Revet, Alfred Young trong một loạt bài viết về lý thuyết bất biến đã đưa ra các phân hoạch và các biến thể của chúng (bây giờ gọi là bảng Young) trong lý thuyết biểu diễn của nhóm đối xứng. Vào nửa cuối của thế kỷ XX, các ứng dụng của phân hoạch phát triển rất nhanh, T. W. B. Hughes đã phát triển ứng dụng (cả hai chiều) giữa đại số Lie và phân hoạch. J. Leponsky và những người khác cho thấy làm thế nào để hiểu và chứng minh đồng nhất Rogers – Ramanujan trong đại số Lie và một số ứng dụng của phân hoạch xuất hiện trong vật lý. Đặc biệt công trình của Rodrey Baxter cho thấy rằng đồng nhất Rogers – Ramanujan quyết định trong nghiên cứu hoạt động của dung dịch Heli trên một tấm than chì. Phân hoạch cùng ứng dụng của nó vẫn là vấn đề được nghiên cứu sôi nổi đến tận ngày nay. 1.2 Một số kết quả kinh điển 1.2.1 Công thức gần đúng cho p(n) Để trả lời cho câu hỏi của Ramanujan "Có cách nào để tính p(n) hiệu quả không?", một số nhà toán học đã đưa ra các công thức cho p(n). Cayley (năm 1855) và Sylvester (năm 1882) đã đưa ra một số công thức cho pk (n) với k nhỏ, ở đây pk (n) là số phân hoạch của n thành các phần không lớn hơn k (xem [3]–Tr13). Ví dụ: (n + 1) p2 (n) = [ ], (1.1) 2 (n + 3)2 p3 (n) = { }, (1.2) 12
12 trong đó [x] là số nguyên lớn nhất không vượt quá x, {x} là số nguyên gần x nhất. Một trong những bất ngờ lớn nhất trong lịch sử của nghiên cứu phân hoạch là năm 1918, Hardy và Ramanujan đã đưa ra công thức gần đúng cho p(n) (xem [4]): v (12)1/2 X p(n) = Ak (n)(un − k)exp(un /k) + O(n−1 ), (1.3) (24n − 1)un k=1 √ π 24n − 1 √ ở đây, un = , v = O n và 6 X Ak (n) = ωh,k e−2nhπi/k , 0≤h
13 1.2.2 Hàm sinh của hàm phân hoạch Leonhard Euler đã trả lời câu hỏi của Naudé có bao nhiêu phân hoạch của 50 thành 7 phần riêng biệt bằng cách đưa ra hàm sinh (xem [3]). Sử dụng ký hiệu hiện đại, chúng ta giả sử D(m, n) ký hiệu số phân hoạch n thành m phần thì X ∞ Y m n 1 2 3 D(m, n)z q = (1 + zq )(1 + zq )(1 + zq ) . . . = (1 + zq j ). m,n≥0 j=1 Đồng nhất thức này trở nên rõ ràng khi chúng ta nhân những thừa số bên phải với nhau. Số hạng tổng quát là: (zq i1 )(zq i2 ) . . . (zq ij ) = z j q i1 +i2 +...+ij . Chú ý rằng ∞ Y ∞ Y (1 + zq ) = (1 + zq) (1 + (zq)q j ). j j=1 j=1 Ta có phương trình hàm cho hàm sinh của D(m, n) X X D(m, n)z m q n = (1 + zq) D(m, n)z m q n+m . m,n≥0 m,n≥0 So sánh hệ số của z m q n cả hai vế ta thấy: D(m, n) = D(m, n − m) + D(m − 1, n − m). Phương trình cho phép tính toán dễ dàng các giá trị của D(m, n). Naudé cũng đã hỏi Euler: Hàm sinh của p(n) là gì? Số các phân hoạch của n là bao nhiêu? Để trả lời câu hỏi đó Euler đã áp dụng cùng một nguyên tắc trong tính toán D(m, n) rất hiệu quả, cụ thể ∞ X p(n)q n = (1 + q 1 + q 1+1 + q 1+1+1 + q 1+1+1+1 + . . .) n=0 × (1 + q 2 + q 2+2 + q 2+2+2 + q 2+2+2+2 + . . .) × (1 + q 3 + q 3+3 + q 3+3+3 + q 3+3+3+3 + . . .) . . .
14 ∞ Y = (1 + q n + q n+n + q n+n+n + q n+n+n+n + . . .) n=1 Y∞ = (1 + q n + q 2n + q 3n + q 4n + . . .) n=1 ∞ Y 1 = n . n=1 1 − q Hay ∞ X 1 p(n)q n = . (1.5) n=0 (q; q)∞ Ở đây, | q |≤ 1 và (q; q)n được định nghĩa bởi ∞ Y (1 − aq i ) (a; q)n = n+i ) , i=1 (1 − aq đối với hằng số a tuỳ ý. Quy ước p(0) = 1. Nếu n là số nguyên dương thì rõ ràng (a; q)n = (1 − a)(1 − aq)...(1 − aq n−1 ), và (a; q)∞ = (1 − a)(1 − aq)(1 − aq 2 ) . . . = lim ((a; q)n ). n→∞ Vào thời điểm này, Euler nhận ra rằng khai triển chuỗi luỹ thừa của Q∞ n i=1 (1 − q ) quan trọng đối với tính toán p(n). Ông khám phá ra bằng thực nghiệm ∞ Y (1 − q n ) = (1 − q − q 2 + q 5 + q 7 − q 12 − q 15 + q 22 + q 26 + . . .) n=1 ∞ X = (−1)n .q n(3n−1)/2 . n=−∞ Nhiều năm sau khám phá của mình, Euler đã thành công trong việc tự mình đưa ra chứng minh cho phát hiện này. Công thức này nổi tiếng với tên gọi định lý số ngũ giác của Eulers. Định lí 1.1. (Định lí số ngũ giác của Euler) Cho | q |< 1 ta có X∞ (q; q)∞ = (−1)s q s(3s−1)/2 . (1.6) s=−∞
15 Chúng ta sẽ tìm hiểu chứng minh định lí này ở phần sau. Kết hợp Định lí số ngũ giác của Euler và hàm sinh của p(n) ta có: ∞ X ∞ X n n(3n−1)/2 ( (−1) .q ) p(n)q n = 1. (1.7) n=−∞ n=0 So sánh hệ số của q N trong hai vế của đồng nhất thức cuối cùng này, Euler đã tìm ra phép truy hồi cho p(N ) : p(0) = 1, p(N ) − p(N − 1) − p(N − 2) + p(N − 5) + p(N − 7) − . . . = 0, N > 0. Không ai có thể tìm được một thuật toán hiệu quả hơn trong việc tính toán p(N ). Nó tính được đầy đủ các giá trị của p(n) khi n ≤ N với thời gian O(N 3/2 ). Quan hệ truy hồi này được sử dụng bởi P.A. MacMahon để tính toán p(n) với 1 ≤ n ≤ 200 và bởi H. Gupta để xác định p(n) với 201 ≤ n ≤ 300. Nếu muốn tính toán giá trị nào đó của p(n) trên máy tính, thì máy tính có lẽ là sẽ sử dụng : X p(N ) = (−1)k−1 .q k(3k±1)/2 p(n). k(3k±1)/2+n=N,0≤n, bản cập nhật ngày 15/4/2017. Nếu ta kí hiệu pm (n) là số phân hoạch của n thành các phần không lớn hơn m thì rõ ràng ∞ 1 X = pm (n)q n (q, q)m n=0 Định lí 1.2. Giả sử pm (n) ký hiệu số phân hoạch của n thành các phần không lớn hơn m , p(m, n) là số phân hoạch của n thành đúng m phần. Khi đó, pm (n) = p(m, n).
16 Chứng minh: Xét biểu đồ Ferrers của n, như trong hình dưới là biểu đồ Ferrers của 29 = 7+7+6+5+2+2 ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ Biểu đồ trên cho ta phân hoạch của p(6; 29). Thay vì đọc phân hoạch từ trên xuống dưới, ta đọc biểu đồ Ferrers từ trái sang phải. Như vậy, trong hình trên với phân hoạch này, cụ thể là 29 = 6 + 6 + 4 + 4 + 4 + 3 + 2, được đếm theo p6 (29). Mỗi phân hoạch như vậy được đếm theo p(m; n) liên kết duy nhất với phân hoạch đếm theo pm (n). Rõ ràng, điều này thiết lập một song ánh cho các phân hoạch đếm bằng p(m; n) với các phân hoạch đếm bằng pm (n). Do đó, ta có điều phải chứng minh. Định lí 1.3. Giả sử Q(n) ký hiệu số phân hoạch của n thành các phần phân biệt. Khi đó hàm phân hoạch cho Q(n) được cho bởi ∞ X Q(n)q n = (−q; q)∞ . (1.8) n=0 Chứng minh: Chú ý rằng (−q; q)∞ chỉ sinh ra hai số hạng đầu tiên của mỗi dãy trong vế phải của (1.5). Như vậy, trong mỗi phân hoạch của n, mỗi số nguyên không lớn hơn n có thể xuất hiện trong một phân hoạch cụ thể của n nhiều nhất một lần. Định lý được chứng minh. Định nghĩa 1.6. Giả sử po (n) ký hiệu số phân hoạch của n thành các phần lẻ và pe (n) ký hiệu số phân hoạch của n thành các phần chẵn . Nhận thấy rằng ∞ ∞ 1 X n 1 X 2 = p o (n)q và 2 2 = pe (n)q n . (1.9) (q, q )∞ n=0 (q , q )∞ n=0 Định lí 1.4. Với mỗi n ≥ 1 thì Q(n) = po (n). (1.10)