Thay vì đưa ra một loạt định nghĩa — khá dễ kiếm trên internet nhưng bạn có thể sẽ cảm thấy hơi khó hiểu khi mới tiếp xúc — tôi nghĩ sẽ thú vị hơn nếu chúng ta cùng nhìn nhận lí thuyết phạm trù (category theory) trong bức tranh lớn hơn của toán học. Lí thuyết này khác biệt so với các nhánh toán học khác. Thay vì là một lĩnh vực ngang hàng với các ngành khác, nó giống như một “gen chung” kết nối chúng lại ngay từ gốc rễ.
Các đa thức đối xứng (symmetric polinomials) đóng vai trò quan trọng trong việc hiểu mối quan hệ giữa các nghiệm (root) của các phương trình đa thức và các hệ số (coefficient) của chúng. Trong bài viết này, chúng ta sẽ khám phá sâu hơn về mối liên hệ này, từ định nghĩa cơ bản đến các ứng dụng thực tiễn.
Đa thức đối xứng với các biến $x_1, x_2, \ldots, x_n$ là một đa thức không thay đổi dưới bất kì phép hoán vị (permutation) nào của các biến. Cụ thể, với bất kì phép hoán vị $\sigma$ nào của các chỉ số ${1, 2, \ldots, n}$:
Chúng ta cần chuyển bài toán quy hoạch tuyến tính từ dạng tổng quát (general form) sang dạng chuẩn (standard form). Tức là:
Trong đó, (1),(2) và (3) là các yêu cầu bắt buộc. (4) và (5) không bắt buộc phải đảm bảo trong dạng chuẩn, nhưng đó sẽ là điều kiện bắt buộc khi giải bài toán tối ưu bằng phương pháp đơn hình về sau.
$$\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_r$$$$ n = \lambda_1 + \dots + \lambda_r .$$Tham khảo chủ yếu từ https://docs.oscar-system.org/stable/Combinatorics/EnumerativeCombinatorics/partitions/#partition
Các $\lambda_i$ được gọi là các phần tử (part) của phân hoạch và $r$ được gọi là độ dài (length). Tham khảo thêm tại Ful97 và Knu11, Mục 7.2.1.4.
Một phân hoạch có thể được mã hóa (encoded) dưới dạng một mảng (array) với các phần tử (element) là $\lambda_i$.
OSCAR cung cấp kiểu tham số (parametric type) Partition{T} và đây là một kiểu con (subtype) của AbstractVector{T}.
Ở đây, T có thể là bất kì kiểu con nào của IntegerUnion.
Hiệu suất không bị hảnh hưởng khi sử dụng kiểu riêng cho phân hoạch thay vì chỉ sử dụng mảng.
Kiểu tham số này cho phép tăng hiệu suất bằng cách sử dụng các kiểu số nguyên nhỏ hơn.
