Tổ hợp liệt kê

Tổ hợp liệt kê là một phần của toán học tổ hợp nghiên cứu số cách mà các mẫu nhất định có thể được hình thành. Hai ví dụ về loại vấn đề này là đếm số tổ hợp và đếm số hoán vị. Nói chung, cho một tập hợp vô hạn các tập hữu hạn S_i được lập chỉ mục bằng các số tự nhiên, tổ hợp liệt kê tìm cách mô tả một hàm đếm số đối tượng trong S_n cho từng số n. Mặc dù đếm số lượng các phần tử trong một tập hợp là bài toán khá rộng, nhiều vấn đề phát sinh trong các ứng dụng có một mô tả tổ hợp tương đối đơn giản. Phương pháp 12 cách cung cấp một khuôn khổ thống nhất để đếm các hoán vị, tổ hợp và phân vùng.

Những hàm như vậy đơn giản nhất đều là các công thức đóng, nghĩa là có thể diễn đạt bằng một hỗn hợp các hàm sơ cấp như giai thừa, hàm mũ v.v... Chẳng hạn, như chỉ ra dưới đây, số lượng các cách sắp xếp của n lá bài là f(n) = n!. Bài toán tìm kiếm một công thức đóng được gọi là liệt kê đại số, và nó thường xuyên bao gồm việc tính toán kiểu đệ quy hoặc hàm chuỗi và dùng nó để đạt tới dạng hàm mong muốn.

Thông thường, một công thức khép kín phức tạp mang lại ít hiểu biết sâu sắc về hành vi của việc đếm khi số lượng vật thể đếm tăng lên. Trong những trường hợp này, một phép xấp xỉ tiệm cận đơn giản có thể thích hợp hơn. Một hàm $g(n)$ Là một xấp xỉ tiệm cận của $f(n)$ nếu $f(n)/g(n)\rightarrow 1$ khi $n\rightarrow \infty$. Trong trường hợp này chúng ta viết $f(n)\sim g(n).\,$

Xem thêm

• Bổ đề Burnside

Tham khảo

• Zeilberger, D., Enumerative and Algebraic Combinatorics
• Bjorner, A. and Stanley, R. P., A Combinatorial Miscellany
• Graham, R.L., Grötschel M., and Lovász L., eds. (1996). Handbook of Combinatorics, Volumes 1 and 2. Elsevier (North-Holland), Amsterdam, and MIT Press, Cambridge, Mass. ISBN 0-262-07169-X.
• Joseph, George Gheverghese (1994) [1991]. The Crest of the Peacock: Non-European Roots of Mathematics (ấn bản 2). London: Penguin Books. ISBN 0-14-012529-9.
• Loehr, Nicholas A. (2011). Bijective Combinatorics Lưu trữ tại Archive-It. CRC Press. ISBN 143984884X, ISBN 978-1439848845.
• Stanley, Richard P. (1997, 1999). Enumerative Combinatorics, Volumes 1 and 2. Cambridge University Press. ISBN 0-521-55309-1, ISBN 0-521-56069-1.
• Combinatorial Analysis – an article in Encyclopædia Britannica Eleventh Edition
• Riordan, John (1958). An Introduction to Combinatorial Analysis, Wiley & Sons, New York (republished).
• Riordan, John (1968). Combinatorial identities, Wiley & Sons, New York (republished).
• Wilf, Herbert S. (1994). Generatingfunctionology (ấn bản 2). Boston, MA: Academic Press. ISBN 0-12-751956-4. Zbl 0831.05001.