Máy Tính Hàm Phân Hoạch

Chào mừng bạn đến với Máy Tính Hàm Phân Hoạch, một công cụ khám phá đầy đủ tính năng cho một trong những đối tượng hấp dẫn nhất của toán học tổ hợp. Nhập bất kỳ số nguyên không âm \(n\) nào và công cụ này sẽ tính toán \(p(n)\) — số cách viết \(n\) dưới dạng tổng của các số nguyên dương không quan trọng thứ tự — cùng với số lượng phân hoạch thành các phần phân biệt \(q(n)\), số lượng phân hoạch thành các phần lẻ \(o(n)\), ước tính tiệm cận Hardy-Ramanujan, mọi đồng dư Ramanujan phù hợp và (đối với \(n\) nhỏ) từng phân hoạch đơn lẻ được hiển thị dưới dạng biểu đồ Young hoạt họa.

Hàm phân hoạch p(n) là gì?

Hàm phân hoạch \(p(n)\) đếm số cách viết \(n\) dưới dạng tổng của các số nguyên dương, không xét đến thứ tự. Hai tổng chỉ khác nhau về thứ tự của các số hạng được coi là cùng một phân hoạch. Ví dụ, các phân hoạch của 4 là:

• 4
• 3 + 1
• 2 + 2
• 2 + 1 + 1
• 1 + 1 + 1 + 1

Điều đó cho \(p(4) = 5\). Theo quy ước \(p(0) = 1\), đếm "phân hoạch rỗng". Một vài giá trị khác: \(p(1) = 1,\ p(5) = 7,\ p(10) = 42,\ p(50) = 204{,}226,\ p(100) = 190{,}569{,}292.\)

Hàm sinh

Leonhard Euler đã khám phá ra rằng hàm sinh cho \(p(n)\) có dạng tích cực kỳ gọn gàng:

Mỗi nhân tử \(1/(1 - x^k) = 1 + x^k + x^{2k} + \ldots\) đóng góp vào việc lựa chọn số lần phần \(k\) xuất hiện trong phân hoạch. Nhân các nhân tử lại với nhau sẽ tạo ra mọi phân hoạch đúng một lần.

Biểu đồ Young (Ferrers)

Một biểu đồ Young (còn được gọi là biểu đồ Ferrers) đại diện cho một phân hoạch một cách trực quan dưới dạng một mảng các ô vuông căn lề trái. Mỗi hàng tương ứng với một phần, và các hàng được liệt kê từ lớn nhất đến nhỏ nhất. Ví dụ, phân hoạch \(4 + 2 + 1\) của 7 trở thành:

Biểu đồ Young cho phép bạn "nhìn thấy" các đồng nhất thức phân hoạch. Phản chiếu một biểu đồ qua đường chéo chính của nó sẽ biến các hàng thành các cột, tương ứng với phân hoạch liên hợp. Máy tính này hiển thị biểu đồ Young cho mọi phân hoạch của \(n\) bất khi nào \(n \le 15\).

Định lý phân hoạch của Euler

Một trong những kết quả thanh lịch nhất của Euler phát biểu rằng:

Ví dụ, các phân hoạch của 7 thành các phần phân biệt là \(\{7\}, \{6+1\}, \{5+2\}, \{4+3\}, \{4+2+1\}\) — có năm phân hoạch. Các phân hoạch của 7 thành các phần lẻ là \(\{7\}, \{5+1+1\}, \{3+3+1\}, \{3+1+1+1+1\}, \{1+1+1+1+1+1+1\}\) — cũng có năm. Bảng tóm tắt của máy tính báo cáo cả \(q(n)\) và \(o(n)\) để bạn có thể xác minh đồng nhất thức này cho \(n\) đã chọn.

Tiệm cận Hardy-Ramanujan

Vào năm 1918, G.H. Hardy và Srinivasa Ramanujan đã chứng minh công thức đầu tiên nắm bắt được tốc độ tăng trưởng thực sự của \(p(n)\) cho \(n\) lớn:

Kết quả này nảy sinh từ phương pháp đường tròn Hardy-Ramanujan, tích phân hàm sinh xung quanh các điểm kỳ dị trên đường tròn đơn vị. Hans Rademacher đã tinh chỉnh nó vào năm 1937 thành một chuỗi hội tụ chính xác — một trong những công thức nổi tiếng nhất trong lý thuyết số giải tích.

Các đồng dư phân hoạch của Ramanujan

Trong khi nghiên cứu bảng các giá trị phân hoạch, Ramanujan đã nhận thấy ba mẫu chia hết đáng kinh ngạc:

Ví dụ, \(p(4)=5,\ p(9)=30,\ p(14)=135,\ p(19)=490,\ p(24)=1575\) đều chia hết cho 5. Máy tính sẽ tự động đánh dấu bất khi nào \(n\) bạn chọn nằm trong một trong các lớp này.

Cách Sử Dụng Máy Tính Này

1. Nhập một số nguyên không âm lên đến 500 vào hộp nhập liệu, hoặc nhấp vào một trong các ví dụ nhanh nổi tiếng (0, 4, 10, 42, 100, 200).
2. Nhấp vào "Tính toán phân hoạch". Công cụ sẽ tính toán \(p(n)\), \(q(n)\), \(o(n)\) và ước tính Hardy-Ramanujan.
3. Xem bảng kết quả nổi bật hiển thị \(p(n)\) dưới dạng số tiêu đề lớn, sau đó quét bảng tóm tắt cho các phần phân biệt, phần lẻ, ước tính tiệm cận và sai số phần trăm.
4. Kiểm tra biểu đồ Young — nếu \(n \le 15\), từng phân hoạch đơn lẻ sẽ được vẽ dưới dạng biểu đồ Young hoạt họa trong một lưới tương thích.
5. Khám phá biểu đồ tăng trưởng — vẽ \(p(k)\), \(q(k)\) và đường cong Hardy-Ramanujan cho \(k = 0, 1, \ldots, n\). Chuyển đổi giữa thang đo tuyến tính và logarit để thấy hình dạng tiệm cận.
6. Đọc bảng tăng trưởng — chế độ xem từng dòng của \(p(k), q(k), o(k)\) cho \(k\) nhỏ. Sử dụng nó để phát hiện lần xuất hiện đầu tiên của mỗi đồng dư Ramanujan.

Ví dụ cụ thể: Các phân hoạch của 5

Hãy cùng xem qua trường hợp \(n = 5\). Tất cả các phân hoạch là:

• \(5\)
• \(4 + 1\)
• \(3 + 2\)
• \(3 + 1 + 1\)
• \(2 + 2 + 1\)
• \(2 + 1 + 1 + 1\)
• \(1 + 1 + 1 + 1 + 1\)

Vì vậy \(p(5) = 7\). Các phân hoạch thành phần phân biệt: \(\{5\}, \{4+1\}, \{3+2\}\) — có ba phân hoạch, nên \(q(5) = 3\). Các phân hoạch thành phần lẻ: \(\{5\}, \{3+1+1\}, \{1+1+1+1+1\}\) — cũng có ba, nên \(o(5) = 3\). Định lý Euler được thỏa mãn. Cuối cùng, \(n = 5 \equiv 0 \pmod 5\) không có dạng \(5k+4\), nên đồng dư 5 không áp dụng; tuy nhiên, \(p(4) = 5\) thỏa mãn \(p(5k+4) \equiv 0 \pmod 5\).

Các giá trị kinh điển của p(n)

Lịch sử

• Thập niên 1750: Leonhard Euler nghiên cứu các phân hoạch và khám phá ra đồng nhất thức hàm sinh và định lý "phân biệt = lẻ".
• 1915: Thiếu tá Percy MacMahon xuất bản bảng giá trị \(p(n)\) cho \(n\) lên đến 200 — được tính toán bằng tay.
• 1918: Hardy và Ramanujan chứng minh công thức tiệm cận bằng phương pháp đường tròn.
• 1919: Ramanujan xuất bản các đồng dư nổi tiếng \(p(5k+4),\ p(7k+5),\ p(11k+6)\).
• 1937: Hans Rademacher tinh chỉnh Hardy-Ramanujan thành một chuỗi hội tụ chính xác.
• 2011: Ken Ono và Jan Bruinier chứng minh rằng \(p(n)\) có thể được biểu diễn dưới dạng tổng đại số hữu hạn tại mọi số nguyên dương.

Ứng dụng

• Toán học tổ hợp và lý thuyết biểu diễn — các phân hoạch đánh chỉ số cho các biểu diễn bất khả quy của nhóm đối xứng \(S_n\).
• Cơ học thống kê — số lượng phân hoạch xuất hiện trong entropy của khí lượng tử lý tưởng và trong các hàm phân hoạch của lý thuyết dây.
• Dạng modular — hàm sinh cho \(p(n)\) có liên quan chặt chẽ với hàm eta Dedekind.
• Khoa học máy tính — các điểm chuẩn liệt kê bài toán tổng tập con và lập trình nguyên thường xuyên sử dụng số lượng phân hoạch.

Câu Hỏi Thường Gặp

Hàm phân hoạch p(n) là gì?

\(p(n)\) đếm số cách biểu diễn \(n\) dưới dạng tổng của các số nguyên dương trong đó thứ tự không quan trọng. \(p(4) = 5\) vì 4 có thể được viết thành \(4\), \(3+1\), \(2+2\), \(2+1+1\), hoặc \(1+1+1+1\). Theo quy ước \(p(0) = 1\).

Biểu đồ Young hoặc Ferrers là gì?

Biểu đồ Young là một biểu diễn trực quan của một phân hoạch: mỗi phần trở thành một hàng các ô vuông căn lề trái, với các phần được liệt kê từ lớn nhất đến nhỏ nhất từ trên xuống dưới. Đối với \(4+2+1\), vẽ một hàng 4, một hàng 2 và một hàng 1. Máy tính này hiển thị biểu đồ Young cho mỗi phân hoạch khi \(n \le 15\).

Định lý phân hoạch của Euler nói gì?

Với mỗi số nguyên dương \(n\), số lượng phân hoạch của \(n\) thành các phần phân biệt bằng số lượng phân hoạch của \(n\) thành các phần lẻ. Với \(n = 5\): các phần phân biệt cho \(\{5\}, \{4+1\}, \{3+2\}\); các phần lẻ cho \(\{5\}, \{3+1+1\}, \{1+1+1+1+1\}\). Cả hai đều bằng 3.

Công thức tiệm cận Hardy-Ramanujan là gì?

Nó phát biểu rằng \(p(n) \sim \frac{1}{4n\sqrt{3}} \exp\!\left(\pi \sqrt{2n/3}\right)\) khi \(n \to \infty\). Đây là công thức đầu tiên mô tả tốc độ tăng trưởng chính xác của \(p(n)\), được G.H. Hardy và Srinivasa Ramanujan khám phá năm 1918.

Các đồng dư phân hoạch của Ramanujan là gì?

Ba mẫu chia hết đáng kinh ngạc: \(p(5k+4) \equiv 0 \pmod 5\), \(p(7k+5) \equiv 0 \pmod 7\), và \(p(11k+6) \equiv 0 \pmod{11}\). Ví dụ, \(p(4)=5, p(9)=30, p(14)=135\) đều chia hết cho 5.

p(n) tăng nhanh như thế nào?

p(n) tăng trưởng dưới mức lũy thừa nhưng nhanh hơn bất kỳ đa thức nào, đại khái như \(\exp(\pi \sqrt{2n/3})\). Để so sánh: \(p(10)=42\), \(p(50)=204{,}226\), \(p(100)=190{,}569{,}292\), và \(p(200) \approx 4 \times 10^{12}\). Sử dụng nút chuyển đổi thang đo logarit của biểu đồ để hình dung đường cong tăng trưởng này.

Tài Nguyên Bổ Sung

• Hàm phân hoạch - Wikipedia
• Bảng Young - Wikipedia
• Đồng dư của Ramanujan - Wikipedia
• OEIS A000041 - Số lượng phân hoạch của n