Thiết kế tổ hợp

Lý thuyết thiết kế tổ hợp là một phần của toán học tổ hợp quan tâm đến sự tồn tại, xây dựng và tính chất của các hệ thống tập hợp hữu hạn có sự sắp xếp thỏa mãn các khái niệm tổng quát về sự cân bằng và/hoặc đối xứng. Những khái niệm này không được làm chính xác để cho một phạm vi rộng các đối tượng có thể được coi là dưới cùng một định nghĩa. Đôi khi điều này có thể liên quan đến các kích thước số của các nút giao đặt như trong các thiết kế khối, trong khi ở những thời điểm khác nó có thể liên quan đến việc bố trí không gian các mục trong một mảng như trong các ô vuông sudoku.

Lý thuyết thiết kế tổ hợp có thể được áp dụng cho lĩnh vực thiết kế thí nghiệm. Một số lý thuyết cơ bản của thiết kế tổ hợp có nguồn gốc từ các tác phẩm của nhà thống kê học Ronald Fisher về thiết kế thí nghiệm sinh học. Các ứng dụng hiện đại cũng được tìm thấy trong vô số lĩnh vực bao gồm; hình học hữu hạn, lập kế hoạch giải đấu, xổ số, toán sinh học, thiết kế và phân tích thuật toán, mạng máy tính, kiểm tra nhóm và mật mã học.^[1]

Ví dụ

Với một số n người nhất định, có thể gán họ vào các tập hợp sao cho mỗi người thuộc về ít nhất một tập hợp, mỗi cặp 2 người ở trong cùng đúng một tập hợp với nhau, mỗi cặp 2 tập hợp có chính xác một người chung và không có tập hợp nào chứa tất cả mọi người, tất cả trừ một người, hoặc chính xác chỉ một người? Câu trả lời phụ thuộc vào n.

Bài toán này chỉ có lời giải nếu n có dạng q² + q + 1. Để chứng minh rằng một giải pháp tồn tại nếu q là một số mũ của một số nguyên tố thì khó hơn. Người ta cho rằng đây là những giải pháp duy nhất. Người ta đã chứng minh thêm rằng nếu một giải pháp tồn tại cho q đồng dư 1 hoặc 2 mod 4, vậy thì q là một tổng của hai số chính phương. Kết quả cuối cùng này, định lý Bruck-Ryser, được chứng minh bằng sự kết hợp các phương pháp xây dựng dựa trên các trường hữu hạn và áp dụng các dạng thức bậc hai.