Tiểu Luận Hàm sinh thường và ứng dụng

Mục lục
Lời nói đầu . 2
Danh sách nhóm
1. Đại cương về tổ hợp . 3
1.1 Các bài toán tổ hợp . 3
1.1.1 Cấu hình tổ hợp . 3
1.1.2 Các dạng toán tổ hợp . 3
1.2 Các cấu hình tổ hợp cơ bản 5
1.2.1 Hoán vị 5
1.2.2 Hoán vị lặp 5
1.2.3 Tổ hợp . 6
1.2.4 Tổ hợp lặp . 6
1.2.5 Chỉnh hợp 7
1.2.6 Chỉnh hợp lặp 7
1.2.7 Nhị thức Newton 8
2. Hàm sinh thường . 9
2.1 Định nghĩa hàm sinh thường .9
2.2 Định lý .9
3. Ứng dụng hàm sinh thường giải các bài toán truy hồi .12
3.1 Bài toán (số Fibonaci) 12
3.2 Ứng dụng hàm sinh giải các bài toán đếm điển hình .13
3.2.1 Ứng dụng hàm sinh giải bài toán chia kẹo Euler .13
3.2.2 Ví dụ .13
3.3 Ứng dụng hàm sinh giải công thức truy hồi tuyến tính 15
3.3.1 Công thức truy hồi 15
3.3.2 Công thức truy hồi tuyến tính hệ số hằng 15
3.3.3 Giải công thức truy hồi tuyến tính bằng hàm sinh .16
3.3.3.1 Giải công thức truy hồi tuyến tính thuần nhất hệ số hằng .16
3.3.3.2 Giải công thức truy hồi tuyến tính không thuần nhất hệ số hằng .17
Kết luận .19
Tài liệu tham khảo 20



Lời nói đầu

Vào TK XVII với hàng loạt công trình nghiên cứu của các nhà toán học xuất sắc như: Pascal, Fermat, Uuler, Leibnitz, dẫn đến lý thuyết tổ hợp được hình thành.
Các bài toán tổ hợp có đặc trưng bùng nổ tổ hợp với số cấu hình tổ hợp khổng lồ. Việc giải chúng đòi hỏi một khối lượng tính toán không lồ. Vì vậy trong thời gian dài, khi mà các ngành toán học như Phép tính vi phân, phép tính tích phân, phương trình vi phân, phát triển như vũ bảo, thì dường như nó nằm ngoài sự phát triển và ứng dụng của toán học. Và cho đến khi xuất hiện máy tính điện tử và toán học hữu hạn, nhiều vấn đề tổ hợp được giải quyết trên máy tính. Từ chỗ chỉ nghiên cứu các trò chơi, tổ hợp đã trở thành ngành toán học phát triển mạnh mẽ, có nhiều ứng dụng trong các lĩnh vực toán học và tin học
Hàm sinh là một trong những sáng tạo thần tình, bất ngờ, nhiều ứng dụng của toán rời rạc. Nói một cách nôm na, hàm sinh chuyển những bài toán về dãy số thành những bài toán về hàm số. Điều này là rất tuyệt vời vì chúng ta đã có trong tay cả một cỗ máy lớn để làm việc với các hàm số. Nhờ vào hàm sinh, chúng ta có thể áp dụng cỗ máy này vào các bài toán dãy số. Bằng cách này, chúng ta có thể sử dụng hàm sinh trong việc giải tất cả các dạng toán về phép đếm. Có cả một ngành toán học lớn nghiên cứu về hàm sinh, vì thế, trong bài này, chúng ta chỉ tìm hiểu những vấn đề căn bản nhất về chủ đề này.
Đề tài xin trình bày vấn đề sau: "Hàm sinh thường và ứng dụng"
Là một phương pháp hữu hiệu để giải quyết các bài toán tổ hợp phức tạp.
Đề tài được chia thành những nội dung chính sau:
1. Lời nói đầu.
2. Chương 1. Đai cương về tổ hợp.
3. Chương 2. Hàm sinh thường .
4. Chương 3. Ứng dụng hàm sinh thường giải các bài toán tổ hợp.
5. Kết luận.