BÁO CÁO
BÀI TẬP LỚN
Trường Đại học Bách Khoa Hà Nội Viện Công nghệ thông tin và truyền thông
Môn Toán rời rạc
Nhóm nghiên cứu:
Kim Đình Sơn 20102089 Nguyễn Hữu Trung 20102767 Hoàng Lê Chung 20101172
Giảng viên hướng dẫn: TS Đỗ Phan Thuận
HÀ NỘI, 4/17/2012
HÀM SINH và ứng dụng
1
Mục lục
Chương 1 Tổng quan về hàm sinh... 2
1.1. Giới thiệu ... 2
1.2. Các phép biến đổi trên hàm sinh ... 2
1.3. Xây dựng hàm sinh ... 3
Chương 2 Các khái niệm mở rộng ... 6
2.1. Hàm sinh mũ ... 6
2.2. Hàm sinh đa biến ... 7
2.3. Hàm sinh xác suất ... 11
2.3.1. Khái niệm ... 11
2.3.2. Hàm sinh của tổng các biến ngẫu nhiên ... 12
Chương 3 Ứng dụng ... 13
3.1, Bài toán tính đếm ... 13
3.2. Bài toán tính tổng... 14
3.3. Tính số phép toán trung bình của thuật toán ... 15
3.4. Các ứng dụng khác ... 16
3.4.1. Bài toán đếm số cây khung ... 16
3.4.2. Hàm sinh chuỗi Dirichlet ... 16
3.4.3. Tính số các bảng dự phòng bởi các số nguyên không âm ( ) ... 17
Kết luận ... 18
Tài liệu tham khảo ... 19
2
∑
∑ ∑
⏟
∑
{ } { }
{ } ∑
∑ ∑
∑
∑ ∑ ∑ ∑ ∑
3 (
)
∑
∑ ∑ ∑
√
√ ∑ ( )
∑ ( ) ( ) ( )
∑
∑ ( )
∑
4
{ }
∏( )
∑
{ } | |
∑ |
{ }
∑ ∑
∑ ∑ { } ∑ ( )
{ }
{ }
∏( )
∏ ( )
∏( )
(∏( )
)
∑
5
∑ ∑
∑[ ]
∑
∑
∑ ∑ ( )
∑ (
) ∑
∑ ( ) ∑
( (
)) ((
) )
∑ ∑
∑
{ |
∑ ∑
∑ ∑ ∑
∑ ∑ ∑
∑ ∑
|
∑ ∑
|
∑
|
[(
) ]
6
{ | } { | }
∑ ∑ ∑ ∑
( )
( )
7
( )
∏
∑
∑
{ |
∑
{ |
[ ] [ ]
∑
{ }
8
∑
|
[ ]
{ } { }
( )
( )
∑
|
∑
|
[ ] [(
) ]
∑
∑
∑ ∑
∑ ∑
9 ∑
∑
∑
∑
∑
|
∑
∏
∑
∏ (
)
10 ∑
|
∑
|
(Multivariate Fuss-Catalan numbers)(một dạng tổng quát cho số
Catalan). Xác định bởi công thức:
( )
[ ]
∑
o
o
o ( )( )
[ ]
11
∑ ( ) ∑
∑
∑ ∑
[ ]
12
| |
∑
[ ]
[ ] [ ] [ ] [ ] [ ] ( )
∑
∏
13
( )
( ) ∑ ( )
( )
( ) ( )( ) ( )( )
{ }
{ }
14
( )
∑
∑
(
) ∑ ( ) ( )
-
∑ ( ) (
⌊ ⌋ )
( )
(⌊ ⌋) ( )
∑ ( ) (⌊ ⌋)
15
∑ ( ) ( )
( )
∑ ( ) (
⌊ ⌋ )
( )
Begin:
j:=1;m=:X[1];
for i:=2 to n do if x[i]>m then m:=x[i];
j:=i;
end if end for End
[ ]
[ ] { [ ] }
16 ∑
[ ]
[ ]
[ ] [ ]
[ ] [ ]
∑
∑
∑
∑
( ) ( ) ( ) ( )
( ) ∑
∑
[ ]
{ }
∑
↔ { } ↔ { }
↔ {∑ }
17
(∑
) ∑
∑
{ ∑
}
∑
[ ] ∑
∏ ∏
18
19
