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.

Tham khảo

1. Stinson 2003, pg.1

Sách tham khảo

• Assmus, E.F.; Key, J.D. (1992), Designs and Their Codes, Cambridge: Cambridge University Press, ISBN 0-521-41361-3
• Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried (1986), Design Theory, Cambridge: Cambridge University Press. 2nd ed. (1999) ISBN 978-0-521-44432-3.
• R. C. Bose, "A Note on Fisher's Inequality for Balanced Incomplete Block Designs", Annals of Mathematical Statistics, 1949, pages 619–620.
• Caliński, Tadeusz; Kageyama, Sanpei (2003). Block designs: A Randomization approach, Volume II: Design. Lecture Notes in Statistics. 170. New York: Springer-Verlag. ISBN 0-387-95470-8.
• Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (ấn bản thứ 2), Boca Raton: Chapman & Hall/ CRC, ISBN 1-58488-506-8
• R. A. Fisher, "An examination of the different possible solutions of a problem in incomplete blocks", Annals of Eugenics, volume 10, 1940, pages 52–75.
• Hall, Jr., Marshall (1986), Combinatorial Theory (ấn bản thứ 2), New York: Wiley-Interscience, ISBN 0-471-09138-3
• Hughes, D.R.; Piper, E.C. (1985), Design theory, Cambridge: Cambridge University Press, ISBN 0-521-25754-9
• Lander, E. S. (1983), Symmetric Designs: An Algebraic Approach, Cambridge: Cambridge University Press
• Lindner, C.C.; Rodger, C.A. (1997), Design Theory, Boca Raton: CRC Press, ISBN 0-8493-3986-3
• Raghavarao, Damaraju (1988). Constructions and Combinatorial Problems in Design of Experiments . New York: Dover.
• Raghavarao, Damaraju and Padgett, L.V. (2005). Block Designs: Analysis, Combinatorics and Applications. World Scientific.
• Ryser, Herbert John (1963), “Chapter 8: Combinatorial Designs”, Combinatorial Mathematics (Carus Monograph #14), Mathematical Association of America
• S. S. Shrikhande, and Vasanti N. Bhat-Nayak, Non-isomorphic solutions of some balanced incomplete block designs I – Journal of Combinatorial Theory, 1970
• Stinson, Douglas R. (2003), Combinatorial Designs: Constructions and Analysis, New York: Springer, ISBN 0-387-95487-2
• Street, Anne Penfold; Street, Deborah J. (1987). Combinatorics of Experimental Design. Oxford U. P. [Clarendon]. tr. 400+xiv. ISBN 0-19-853256-3.
• van Lint, J.H., and R.M. Wilson (1992), A Course in Combinatorics. Cambridge, Eng.: Cambridge University Press.