Hàm sinh thông thường và hàm sinh mũ

Hàm sinh thông thường mã hóa các dãy cho việc đếm không nhãn, trong khi hàm sinh mũ xử lý các cấu trúc có nhãn, và cả hai đều chuyển đổi các cấu trúc tổ hợp thành đại số.

Definition

Hàm sinh thông thường của một dãy là chuỗi lũy thừa với dãy đó làm hệ số; hàm sinh mũ chia mỗi hệ số cho một giai thừa, dạng phù hợp để đếm các đối tượng có nhãn.

Scope

Chủ đề này giới thiệu hai loại hàm sinh chính, khuôn khổ chuỗi lũy thừa hình thức, và phương pháp ký hiệu ánh xạ các cấu trúc tổ hợp – hợp rời, tích, dãy, tập hợp và chu trình – trực tiếp thành các phép toán trên chuỗi. Nó phát triển các công thức tích phân biệt giữa cài đặt thông thường và mũ.

Core questions

• Khi nào nên sử dụng hàm sinh thông thường so với hàm sinh mũ?
• Các phép toán tổ hợp tương ứng với các phép toán đại số trên chuỗi như thế nào?
• Tại sao phép nhân các hàm sinh mũ lại đếm các phép hợp có nhãn?
• Phương pháp ký hiệu tự động hóa việc suy ra các công thức đếm như thế nào?

Key concepts

• Hàm sinh thông thường
• Hàm sinh mũ
• Chuỗi lũy thừa hình thức
• Tích chập và quy tắc tích
• Phương pháp ký hiệu
• Cấu trúc có nhãn so với không nhãn

Key theories

Phương pháp ký hiệu

Phương pháp ký hiệu của Flajolet và Sedgewick cung cấp một từ điển có hệ thống dịch các cấu trúc tổ hợp trên các lớp đối tượng thành các phép toán trên các hàm sinh của chúng, do đó các công thức đếm có thể được đọc từ các mô tả cấu trúc.

Quy tắc tích cho hàm sinh

Tích của hai hàm sinh thông thường liệt kê các cặp có thứ tự theo tổng kích thước, trong khi tích của các hàm sinh mũ liệt kê các phép hợp có nhãn, sự phân biệt này chi phối việc sử dụng dạng nào.

Clinical relevance

Phương pháp ký hiệu tự động hóa việc liệt kê và phân tích trường hợp trung bình của các cấu trúc dữ liệu và thuật toán, và các hàm sinh mũ là công cụ tự nhiên để đếm các cây có nhãn, hoán vị và phân hoạch tập hợp phát sinh trong khoa học máy tính.

History

Sự tương ứng có hệ thống giữa các cấu trúc tổ hợp và các phép toán hàm sinh, được Euler và Polya báo trước, đã được Flajolet và Sedgewick phát triển thành phương pháp ký hiệu hình thức.

Key figures

• Philippe Flajolet
• Robert Sedgewick
• Richard P. Stanley

Seminal works

• flajolet2009
• stanley2011

Frequently asked questions

Khi nào thì hàm sinh mũ được ưu tiên?

Khi các đối tượng được đếm mang các nhãn có thể phân biệt được, chẳng hạn như cây có nhãn hoặc hoán vị, trọng số giai thừa của các hàm sinh mũ làm cho tích của chúng đếm chính xác.

Biến trong hàm sinh có ý nghĩa gì không?

Trong cài đặt hình thức, nó là một phần giữ chỗ đánh dấu kích thước; chỉ khi các phương pháp phân tích được áp dụng thì nó mới được coi là một biến phức với giá trị số.