Luận văn Thạc sĩ: Bài toán Phân hoạch Số nguyên Dương - Nghiên cứu bởi Đinh Thị Thu Huế

Luận văn thạc sĩ trình bày chi tiết bài toán phân hoạch số nguyên dương, bao gồm các thuật toán và ứng dụng thực tế. Nghiên cứu sâu về lý thuyết và phương pháp

• Tác giả: Đinh Thị Thu Huế
• Người hướng dẫn: GS. Hà Huy Khoái
• Trường học: Trường Đại học Khoa học, Đại học Thái Nguyên
• Chuyên ngành: Phương pháp Toán sơ cấp
• Đề tài: Bài toán phân hoạch số nguyên dương
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2017
• Địa điểm: Thái Nguyên

Tóm tắt

I. Tổng quan về bài toán phân hoạch số nguyên dương

Bài toán phân hoạch số nguyên dương nghiên cứu cách biểu diễn một số nguyên dương dưới dạng tổng của các số nguyên dương nhỏ hơn hoặc bằng nó. Đây là lĩnh vực toán học có lịch sử lâu đời, khởi nguồn từ nghiên cứu của Leibniz vào thế kỷ 17. Các nhà toán học nổi tiếng như Euler, Sylvester, Hardy và Ramanujan đã đóng góp quan trọng cho lý thuyết này. Bài toán không chỉ quan trọng trong toán học thuần túy mà còn có ứng dụng trong vật lý hạt, cơ học thống kê và hình học đại số. Các công trình nghiên cứu hiện đại của Okounkov (Giải thưởng Fields 2006) tiếp tục mở rộng ứng dụng của lý thuyết phân hoạch trong nhiều lĩnh vực khoa học khác nhau. Phân hoạch số nguyên dương vẫn là đề tài nghiên cứu sôi nổi nhờ tầm quan trọng lý thuyết và ứng dụng rộng rãi.

1.1. Lịch sử phát triển của bài toán phân hoạch

Leibniz được coi là người đầu tiên nghiên cứu hệ thống bài toán phân hoạch vào năm 1669. Đến thế kỷ 18, Euler đã thiết lập nền tảng lý thuyết vững chắc cho lĩnh vực này thông qua công thức tổng quát p(n) - tổng số phân hoạch của n. Vào thế kỷ 19, Sylvester và Ramanujan đã phát triển các phương pháp mới, trong đó Ramanujan khám phá ra các đồng dư thức quan trọng. Thế kỷ 20 chứng kiến sự đóng góp của Hardy, Littlewood và Andrews trong việc phát triển hàm sinh và lý thuyết modular. Những nghiên cứu này đã đặt nền móng cho các ứng dụng hiện đại trong vật lý toán học.

1.2. Kết quả kinh điển trong lý thuyết phân hoạch

Các kết quả kinh điển bao gồm công thức gần đúng cho p(n) của Hardy-Ramanujan, hàm sinh của Euler, và các đồng nhất thức Rogers–Ramanujan. Định lý số ngũ giác của Euler cung cấp mối liên hệ sâu sắc giữa các phân hoạch. Ramanujan cũng phát hiện ra các đồng dư thức quan trọng như p(5m+4) ≡ 0 (mod 5). Những thành tựu này không chỉ giải quyết các vấn đề lý thuyết mà còn mở đường cho nghiên cứu hiện đại trong lĩnh vực này.

II. Phân tích các vấn đề chính trong phân hoạch số nguyên

Phân hoạch số nguyên dương đối mặt với nhiều thách thức lý thuyết và ứng dụng. Việc xác định chính xác số lượng phân hoạch p(n) cho n lớn vẫn là bài toán khó do tính chất tăng trưởng nhanh chóng của hàm này. Các vấn đề liên quan đến tính chất đồng dư, phân hoạch thành các phần riêng biệt hoặc lẻ đòi hỏi các kỹ thuật toán học phức tạp. Ngoài ra, bài toán chia kẹo của Euler và các biến thể khác đặt ra những thách thức trong việc áp dụng lý thuyết vào thực tế. Những vấn đề này không chỉ thuần túy lý thuyết mà còn có ý nghĩa trong giảng dạy toán học và nghiên cứu ứng dụng.

2.1. Phân hoạch thành các phần phân biệt

Phân hoạch thành các phần phân biệt nghiên cứu cách biểu diễn số dưới dạng tổng của các số khác nhau. Franklin đã phát triển ánh xạ đối hợp quan trọng cho loại phân hoạch này. Kết quả này liên quan mật thiết đến lý thuyết đồ thị và tổ hợp. Các ứng dụng bao gồm mã hóa, mật mã học và tối ưu hóa. Nghiên cứu này cũng cung cấp nền tảng cho các vấn đề chia tài sản công bằng trong kinh tế học.

2.2. Phân hoạch thành các phần lẻ

Phân hoạch thành các phần lẻ tập trung vào biểu diễn số dưới dạng tổng của các số lẻ. Sylvester đã phát triển song ánh quan trọng cho loại phân hoạch này. Kết quả này có mối liên hệ chặt chẽ với lý thuyết số và đại số. Các ứng dụng bao gồm phân tích chuỗi thời gian, xử lý tín hiệu và lý thuyết đồ thị. Nghiên cứu này cũng đóng vai trò quan trọng trong phát triển các thuật toán tối ưu hóa.

III. Phương pháp giải quyết bài toán phân hoạch

Giải quyết bài toán phân hoạch đòi hỏi sự kết hợp giữa lý thuyết tổ hợp, đại số và giải tích. Các phương pháp chính bao gồm sử dụng hàm sinh, lý thuyết modular, và ánh xạ đối hợp. Kỹ thuật biến đổi số thông qua phép thế biến đổi là công cụ quan trọng trong giải quyết các bài toán cụ thể. Nguyên lý bù trừ kết hợp với lý thuyết tập hợp cung cấp giải pháp cho các bài toán phức tạp. Những phương pháp này không chỉ giải quyết các vấn đề lý thuyết mà còn có ứng dụng trong lập trình và khoa học máy tính.

3.1. Phương pháp hàm sinh

Hàm sinh là công cụ mạnh mẽ trong lý thuyết phân hoạch, cho phép biểu diễn các dãy số dưới dạng chuỗi lũy thừa. Phương pháp này chuyển đổi các bài toán tổ hợp thành các bài toán đại số dễ xử lý hơn. Các ứng dụng bao gồm giải quyết các bài toán đếm phức tạp, phân tích chuỗi thời gian, và phát triển thuật toán. Kết quả quan trọng bao gồm các định lý về biểu diễn phân hoạch thông qua hàm sinh.

3.2. Kỹ thuật biến đổi số

Biến đổi số thông qua phép thế biến đổi (như yi = xi - k) là kỹ thuật quan trọng trong giải quyết các bài toán phân hoạch. Phương pháp này chuyển đổi các bài toán có ràng buộc thành các bài toán đơn giản hơn. Kỹ thuật này đặc biệt hữu ích trong giải quyết các bài toán tối ưu hóa và lập trình. Các ứng dụng bao gồm giải quyết các bài toán chia tài sản, phân phối nguồn lực, và tối ưu hóa hệ thống.

IV. Kết luận và ứng dụng thực tiễn của phân hoạch

Lý thuyết phân hoạch số nguyên dương đã phát triển vượt bậc từ các nghiên cứu ban đầu đến các ứng dụng hiện đại. Những đóng góp của các nhà toán học hàng đầu đã tạo nền tảng vững chắc cho lĩnh vực này. Các ứng dụng hiện nay bao gồm vật lý lý thuyết, khoa học máy tính, kinh tế học và sinh học. Nghiên cứu tương lai hứa hẹn những đột phá mới nhờ sự kết hợp giữa toán học thuần túy và ứng dụng. Việc giảng dạy lý thuyết phân hoạch đóng vai trò quan trọng trong phát triển tư duy toán học và khoa học.

4.1. Đóng góp lý thuyết chính

Các đóng góp chính bao gồm việc thiết lập các công thức tường minh, chứng minh các định lý quan trọng, và phát triển các phương pháp giải quyết bài toán. Những thành tựu này không chỉ mở rộng hiểu biết lý thuyết mà còn cung cấp công cụ cho nghiên cứu ứng dụng. Các kết quả quan trọng bao gồm các công thức gần đúng, các đồng nhất thức, và các phương pháp chứng minh mới.

4.2. Triển vọng ứng dụng tương lai

Các ứng dụng tương lai bao gồm phát triển các thuật toán tối ưu hóa trong khoa học máy tính, phân tích dữ liệu lớn, và trí tuệ nhân tạo. Lý thuyết phân hoạch hứa hẹn đóng vai trò quan trọng trong giải quyết các bài toán phức tạp trong vật lý lý thuyết. Các ứng dụng trong kinh tế học bao gồm mô hình hóa tài chính, quản lý rủi ro, và tối ưu hóa sản xuất. Sự phát triển của máy tính lượng tử mở ra những khả năng mới cho nghiên cứu phân hoạch.

Trích đoạn nội dung tài liệu

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 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]). 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 P 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 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. 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. 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. Thường viết tắt phần lặp bằng cách sử dụng lũy thừa.

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.

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).Lehmer nhận thấy chuỗi Hardy – Ramanujan phân kỳ. 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.

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.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. 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. Ô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. 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ó. 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. 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 π. 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.

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 ,. > br > 0 sao cho P P n = r + ri=1 ai + ri=1 bi. 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 > .